Beyond Stability: Improved Efficiency Guarantees for α-Stable Matchings

1 Introduction

Matching theory studies how to assign agents to each other based on their preferences in a way that satisfies certain desirable properties. One of the most extensively studied problems in this field is the stable marriage problem [Gale and Shapley, 1962; Gusfield and Irving, 1989; Knuth, 1997; Roth and Sotomayor, 1990], which involves two sets of agents L and R of size n ≥ 1 each, where each agent ranks all members of the opposite set in a strict order of preference. A matching is said to be stable if there is no pair of agents who would both prefer to be matched with each other over their current matches. Stable matchings have been a cornerstone of market design with wide-ranging applications in assigning students to schools, medical graduates to residency programs, employees to projects, or students to courses and seminars.

In this work, we study a more general variant of the classical stable matching problem, where agents have cardinal preferences over the members of the opposite group, rather than ordinal ones. Such cardinal preferences do not only capture who is preferred over whom, but also quantify by how much. Additionally, we consider cardinal preferences that can encode indifferences and incompatibilities among the agents. Each agent's cardinal preferences are defined by numerical values (called valuations) specifying how much the agent would like to be matched to another agent. More specifically, we use vij to denote the (positive) valuation that an agent i ∈ L assigns to j ∈ R, and wji to denote the (positive) valuation that agent j ∈ R assigns to i ∈ L. This variant of the stable matching problem is also known as the stable matching problem with cardinal preferences, ties allowed, and incomplete preference lists (or, SMCTI for short). Stable matchings are guaranteed to exist for SMCTI (see, e.g., [Gusfield and Irving, 1989]).

We are interested in the tradeoff between stability and the social welfare efficiency. Given a matching M, the social welfare refers to the total valuations of all matched pairs, i.e., SW(M) = ∑(i,j)∈M (vij + wji). A stable matching M is said to be γ-efficient with γ ∈ (0, 1] if it recovers a γ-fraction of the optimal social welfare (i.e., the maximum social welfare over all matchings). Ideally, we would like to ensure that a stable matching provides a strong efficiency guarantee. However, imposing stability inevitably leads to a significant loss in social welfare efficiency (see the example below). As it turns out, this loss depends on the degree of asymmetry in the agents' valuations. We capture this by introducing an asymmetry parameter µ ∈ (0, 1]: the valuations are µbounded if vij/wji ∈ [µ, 1/µ] for every pair (i, j) with vij > 0 and wji > 0. Note that the valuations are symmetric for µ = 1, and become increasingly asymmetric as µ decreases.

Consider the example in Figure 1 and note that the valuations are µ-bounded. It is easy to verify that, for ϵ > 0, the instance has a unique stable matching M = {(i2, j1)}. On the other hand, the social welfare optimal matching is M ∗ = {(i1, j1), (i2, j2)}. In terms of social welfare, we have SW(M) = 1 + ϵ and SW(M ∗ ) = (µ+1)/µ. Thus, the efficiency of the (unique) stable matching is (1+ϵ)µ/(µ+1). As a consequence, for this instance we cannot guarantee that any stable matching recovers (strictly) more than a fraction of µ/(µ+1) of the optimal social welfare. In particular, the efficiency of a stable matching becomes unbounded as µ approaches 0, or, said differently, as the valuations become increasingly asymmetric. In fact, this tradeoff has been observed before by Anshelevich et al. [2013] for the two limiting cases µ = 1 and µ → 0; but, here, we get a smooth interpolation for any µ between these extreme points-which we show is tight also (see our contributions below).

A further drawback of the classical notion of stability is that it assumes agents will always deviate, even if the respective gain is vanishingly small. This is an overly strong assumption in settings where agents may be reluctant to deviate. As an example, consider the situation of deciding on money transfers between different accounts, where a commission discourages moves unless the gain justifies the expense. Another example are housing markets, where the decision to move to a better home must also account for the financial and personal costs of relocating. In this context, an approach that has been pursued in the literature is to relax the stability notion by incorporating a fixed, additive switching cost [Anshelevich et al., 2013]. While an additive switching cost may be appropriate in some scenarios, in others a cost that scales proportionally with the valuations may be more realistic.

In this work, we build on a relaxed stability notion, termed α-stability, introduced by Anshelevich et al. [2013]. The key idea is to model agents as willing to deviate only when the improvement is sufficiently large, with the required threshold being determined by a parameter α. Formally, a matching M is α-stable with α ∈ (0, 1] if there is no pair (i, j) such that viM(i) < αvij and wjM(j) < αwji, where M(i) and M(j) denote the matches of i and j under M, respectively. As α decreases, agents require a larger improvement to switch, making the stability condition less restrictive.

As mentioned above, α-stability was first introduced in [Anshelevich et al., 2013], where they restrict attention to the case of symmetric valuations (i.e., µ = 1). To the best of our knowledge, we are the first to study the more complex case of asymmetric valuations that are µ-bounded. The idea of studying relaxation of fundamental solution concepts has also been explored in adjacent fields, such as approximate Nash equilibria by Daskalakis et al. [2009] and relaxed fairness notions such as envy-freeness up to one good (EF1) by Budish [2011].

1.1 Our Contributions

We study how the relaxed notion of α-stability influences social welfare efficiency under asymmetric (µ-bounded) valuations, which we term the stability-efficiency tradeoff.

Our main results are as follows:

1. Characterization of Stability-Efficiency Tradoff: We provide a complete characterization of the stabilityefficiency tradeoff (Section 3); see Figure 2 for an illustration. We prove that any α-stable matching is at least (α · µ/(µ+1))-efficient (Proposition 2). Thus, the worstcase efficiency of α-stable matchings becomes worse as α decreases. On the other hand, we prove an upper bound of 1/α · µ/(µ+1) on the best-case efficiency of α-stable matchings. In particular, for smaller values of α, α-stable matchings can achieve a (significantly) better efficiency guarantee than stable matchings, with the magnitude of improvement depending on the ratio µ/(µ+1). Also, for α ≤ µ/(µ+1), any optimal matching is α-stable, implying that α-stable matchings can be 1-efficient. At the same time, our result shows that it is impossible to surpass the bound of min(1, 1/α · µ/(µ+1)). This provides a complete characterization of the stability-efficiency tradeoff for α-stable matchings under µ-bounded valuations; previously, only the case µ = 1 was understood [Anshelevich et al., 2013].
2. Computing α-Stable Matchings: We present a polynomial-time algorithm, termed α-Boosting, that computes an α-stable matching achieving the best-possible worst-case efficiency guarantee (Section 4, Theorem 1). For α ≤ µ/(µ+1), the algorithm simply returns a social welfare optimal matching, which is α-stable and achieves a 1-approximation. For α > µ/(µ+1), α-Boosting uses a more sophisticated approach inspired by [Colini-Baldeschi et al., 2024]: it first computes a social welfare optimal matching, inflates the values of its edges by a factor 1/α, and then applies the Gale-Shapley algorithm to the modified instance. Remarkably, we can show that this algorithm has an approximation guarantee of 1/α · µ/(µ+1), which

is best possible.

1. Hardness of Optimal α-Stable Matchings: We consider the problem of computing an α-stable matching of maximum social welfare (Section 5). We derive two integer linear programming formulations that characterize the set of α-stable matchings. For the stable matching problem with strict preference orders, Vande Vate [1989] and Rothblum [1992] showed that the corresponding linear programming relaxations are integral. However, such a result seems elusive for α-SMCTI. We prove that for any α ∈ (n-1/n, 1), deciding whether an instance of αSMCTI admits an α-stable matching achieving at least a given social welfare is NP-complete (Theorem 2). In particular, this implies that computing an optimal αstable matching is NP-hard for this range of α.

1.2 RelatedWork

The stable matching problem was first introduced by Gale and Shapley [1962], together with an algorithm that computes a stable matching which is optimal in terms of social welfare for the proposing side. Their model assumes that (i) preference lists are complete, and (ii) there are no ties in the preferences. Gale and Sotomayor [1985] considered the case of incomplete preferences and studied how changing the length on an agent's preference list affects their welfare in the final matching.

Later work has explored generalizations of the problem that drop both of the assumptions described above. Iwama et al. [1999] showed that when both assumptions are removed, the problem of determining whether a (perfect) stable matching exists is NP-hard. When only (ii) is dropped, Manlove et al. [2002] proved that finding an optimal stable matching is NP-hard, and Erdil and Ergin [2017] showed that the matching resulting from the Gale-Shapley algorithm may not be optimal for either side. More recently, Haas [2021] proposed heuristic methods to improve the social welfare of these matchings when ties occur.

A different way to generalize the stable marriage problem is to consider weighted preferences. Anshelevich et al. [2013] do this and define the (multiplicative) notion of α-stability, which we consider in this paper. They consider three scenarios: vertex-labeled graphs, symmetric edge-labeled graphs, and asymmetric edge-labeled graphs. 1 In the latter case, they showed that the social welfare of an α-stable matching can be arbitrarily worse than that of an optimal matching, but did not explore this setting further. For symmetric edge-labeled graphs, however, they proved that there always exists an αstable matching with social welfare at least 1/2α times that of an optimal matching. 2 They also provided an algorithm that finds such a matching in O(n2 ) time.

α-Stability was also analyzed in the context of fractional matchings by Caragiannis et al. [2021]. They propose a polynomial time algorithm that computes an α-stable fractional matching which guarantees an α-approximation. They also prove that the problem of finding an optimal α-stable fractional matching is hard to approximate. Different notions of stability have also been considered in the literature (e.g., [Chen et al., 2021; Echenique et al., 2025; Lin et al., 2024; Pini et al., 2013; Troyan et al., 2020]).

1 Our µ parameter interpolates between symmetric edge-labeled (µ = 1) and asymmetric edge-labeled graphs (µ → 0).

2 Note that in Anshelevich et al. [2013], the approximation ratios are presented inversely compared to our notation.

The linear programming approach to the stable matching problem has been widely studied. Vande Vate [1989] was the first to show that the polytope defined by the stable matching constraints has integral extreme points, thereby proving that an optimal stable matching can be found in polynomial time. Rothblum [1992] later expanded on these results and offered simplified proofs. However, they do not easily generalize to the α-stability setting. On the other hand, Manlove et al. [2002] considered a series of harder variants of the problem, which they showed to be NP-hard.

Finally, the stable marriage problem can be seen as a special case of the Generalized Assignment Problem for unit sizes and capacities. Colini-Baldeschi et al. [2024] study different variants of this problem when one group is strategic in a learning-augmented environment. In particular, they introduce a mechanism, called Boost, which increases the values of edges in the predicted matching such that these edges are more likely to be matched during a modified run of the GaleShapley algorithm. Our α-Boosting algorithm builds upon this procedure.

2 Preliminaries

StableMatchingwithCardinal Preferences. An instance of the stable matching problem with cardinal preferences is defined as follows: We are given two sets L and R, each consisting of n agents. 3 We use i and j to refer to agents from the sets L and R, respectively. Each agent has cardinal preferences (allowing for indifferences and incompatibilities) over the agents in the other set. More specifically, each agent i ∈ L has a non-negative valuation vij for every j ∈ R, and each agent j ∈ R has a non-negative valuation wji for every i ∈ L. The valuations of an agent comprise their preference list. The interpretation of the valuations (vij) for agent i ∈ L is as follows: agent i prefers to be matched to j1 rather than j2 if vij1 > vij2 , i is indifferent between j1 and j2 if vij1 = vij2 , and i does not want to be matched to j if vij = 0. The interpretation of the valuations (wji) for an agent j ∈ R follows analogously. We define (i, j) as a pair if i ∈ L and j ∈ R. We say that (i, j) is a compatible pair if vij ̸= 0 and wji ̸= 0. The preference graph PG(L ∪ R, (vij), (wji)) (or simply PG, when clear from context) is the bipartite graph that represents these relational preferences: the vertex set is L ∪ R, the edge set consists of all compatible pairs, i.e., E(PG) = {(i, j) ∈ L × R : vij ̸= 0 and wji ̸= 0}, and each edge (i, j) ∈ E(PG) is associated with two (positive) weights vij and wji. We assume w.l.o.g. that the preference graph PG is non-empty.

α-Stable Matchings. Given a preference graph PG, a matching MPG (or simply M, when clear from context) for PG is a set of edges such that each vertex is incident to at most one edge. Unless specified otherwise, a matching refers to a non-empty matching. We will abuse notation and also denote by M the mapping L ∪ R → L ∪ R ∪ ∅ such that M(i) = j and M(j) = i whenever (i, j) ∈ M. Otherwise, if there is no j ∈ R such that (i, j) ∈ M, we set M(i) = ∅, in which case we will say that i is lonely under M and define viM(i) = 0. For j ∈ R, M(j) = ∅ and wjM(j) are defined similarly. We use Mat(PG) to refer to the set of matchings for PG. A matching M is said to be (inclusion-wise) maximal if there is no edge e ∈ E(PG) \M such that M ∪ {e} is also a matching. A matching is said to be stable if no pair strictly prefers each other to their current matches if any, or to being lonely. 4 In this paper we consider a relaxed stability notion, called α-stability (see also [Anshelevich et al., 2013]).

3 It is w.l.o.g. that |L| = |R|, i.e., an instance with |L| > |R| can be reduced to an instance with |L| = |R′ | by adding agents to R and defining that ∀j ∈ R′ \ R it holds that vij = wji = 0, ∀i ∈ L.

Definition 1 (α-Stability). Let M be a matching for a preference graph PG, and let α ∈ (0, 1]. A pair (i, j) ∈ E(PG) is α-blocking if viM(i) < αvij and wjM(j) < αwji. M is α-stable if there is no α-blocking pair. 5

Note that the original stability notion is equivalent to 1stability. By definition, an α-stable matching M is also α′ - stable for every α′ ≤ α. In particular, a stable matching is α-stable for every α ∈ (0, 1]. This observation also implies that, for any preference graph PG, an α-stable matching is guaranteed to exist for every α ∈ (0, 1] as a stable matching always exists (see [Gusfield and Irving, 1989]). Observe that any α-stable matching must be (inclusion-wise) maximal.

Benchmark. We are interested in how the quality of αstable matchings changes depending on α. To this end, we define the social welfare of a matching M as SW(M) = ∑(i,j)∈M (vij +wji). That is, the social welfare SW(M) accounts for the sum of the valuations of all pairs in the matching M. Given a preference graph PG, an optimal matching is a matching of maximum social welfare and will be denoted by M ∗ , i.e., M ∗ ∈ Mat(PG) and SW(M ∗ ) ≥ SW(M) for every matching M ∈ Mat(PG). Throughout this work, we use the optimal social welfare as a benchmark when evaluating the quality of a matching.

Definition 2 (γ-Efficiency). Let M be a matching and M ∗ be an optimal matching for a preference graph PG. M is said to be γ-efficient with γ ∈ (0, 1] if SW(M) = γSW(M ∗ ).

µ-Bounded Valuations. As it turns out, the efficiency of α-stable matchings does not only depend on the stability parameter α, but also on the "degree of asymmetry" of the underlying valuations. The following notion formalizes this. Given a preference graph PG, the valuations of the agents are µ-bounded with µ ∈ (0, 1] if µwji ≤ vij ≤ wji/µ for all (i, j) ∈ E(PG). Intuitively, for µ = 1 the valuations are symmetric (i.e., vij = wji for all (i, j) ∈ E(PG)), and they become increasingly asymmetric as µ decreases.

Computing α-Stable Matchings. We refer to our stable matching problem introduced above as α-SMCTI for short, which stands for α-Stable Matching with Cardinal preferences, Ties allowed, and Incomplete preference lists. An instance of α-SMCTI is given by a preference graph PG and the parameter α. Given the preference graph PG, we let µ refer to the (largest) µ parameter for which the valuations are µ-bounded (as defined above). We are interested in deriving algorithms that compute α-stable matchings with good efficiency guarantees. In this context, a ρ-approximation algorithm with ρ ∈ (0, 1] is an algorithm that, for any given instance of α-SMCTI, computes in polynomial time an αstable matching M for PG that is at least ρ-efficient, i.e., SW(M) ≥ ρSW(M ∗ ); ρ is also called the approximation guarantee. We also consider the problem of computing an optimal α-stable matching, i.e., an α-stable matching of maximum social welfare among all α-stable matchings.

4 This is sometimes referred to as weak stability.

5 We impose α > 0 as every matching is trivially 0-stable.

3 Stability-Efficiency Tradeoff

Given an instance of α-SMCTI, our ultimate goal is to compute an α-stable matching with a good (large) efficiency. We begin by analyzing the worst-case and best-case efficiency guarantees achievable by α-stable matchings.

Proposition 1. Consider an instance of α-SMCTI with preference graph PG and µ-bounded valuations. Then

• (a) if α ∈ (0, µ µ+1 ], there is always a 1-efficient α-stable matching, and
• (b) if α ∈ ( µ µ+1 , 1], then for every δ > 0 there exists a preference graph PG such that there is no ( 1α · µ µ+1 +δ)- efficient α-stable matching.

Proof. Let α ∈ (0, µ µ+1 ]. We will show that any optimal matching is α-stable. Towards a contradiction, let M ∗ be an optimal matching that is not α-stable for some α ∈ (0, µ µ+1 ]. Then there exists an α-blocking pair (i, j), i.e., viM∗ (i) < αvij and wjM∗ (j) < αwji. As the valuations are µ-bounded we obtain

And as α · µ+1 µ ≤ 1, adding the above equations leads to

Thematching ˆM :=M ∗ \{(i,M ∗ (i)), (M ∗ (j), j)}∪{(i, j)} therefore satisfies SW( ˆM) > SW(M ∗ ), contradicting optimality of M ∗ . Observe that the argument also holds if either i or j is lonely under M ∗ , as (1) remains true, and if i and j are both lonely under M ∗ then this immediately contradicts optimality of M ∗ .

Now let α ∈ ( µ µ+1 , 1]. For each value of δ > 0, we will construct a preference graph such that there is no ( 1α · µ µ+1 + δ)-efficient α-stable matching. Consider the instance shown in Figure 1, where ϵ = 1α - 1 + ϵ′ for some 0 < ϵ′ < (1 + 1µ )δ such that ϵ ∈ ( 1α - 1, 1µ ). 6 The only α-stable matching is given by M = {(i2, j1)}, while the optimal matching is M ∗ = {(i1, j1), (i2, j2)}, leading to 7

6 This interval is well defined as 1α -1 < 1µ since α > µ µ+1 .

Proposition 2. Given an instance of α-SMCTI with preference graph PG and µ-bounded valuations, any α-stable matching is at least (α · µ µ+1 )-efficient.

Proof. Let M be an α-stable matching, and fix an optimal matching M ∗ . Due to α-stability, for every (i, j) ∈ M ∗ , it holds that viM(i) ≥ αvij or wjM(j) ≥ αwji. Thus we can writeM ∗ = E1∪E2, where E1 := {(i, j) ∈M ∗ : viM(i) ≥ αvij} and E2 := {(i, j) ∈ M ∗ : wjM(j) ≥ αwji}. In particular,

Consider the first summation in (2). It holds that wji ≤ 1µ vij ≤ 1 αµ viM(i), as the valuations are µ-bounded and by definition of E1. Therefore,

We can upper bound the second summation in (2) analogously, and therefore upper bound (2) by SW(M ∗ ) ≤ 1α (1+ 1µ )SW(M), proving the claim.

Note that when α = 1, the bounds in Propositions 1 and 2 coincide. Also note that by relaxing the stability requirement to α-stability, the lower bound on the efficiency guarantee decreases whereas the upper bound on the efficiency guarantee increases. We refer to Figure 2 for an illustration of these bounds.

4 Computing α-Stable Matchings

Our aim for this section is to design an algorithm which, given any instance of α-SMCTI with µ-bounded valuations, achieves an approximation guarantee of 1 whenever α ≤ µ/µ+1, and of 1/α · µ/µ+1 otherwise. Note that in light of Proposition 2, this is best possible. We start by introducing our algorithm, called α-Boosting, which builds upon [Gale and Shapley, 1962] and [Colini-Baldeschi et al., 2024].

α-Boosting Algorithm. Given a preference graph PG and a parameter α ∈ (0, 1] as input, α-Boosting first computes an optimal matching M ∗ for PG. If M ∗ is α-stable, then M ∗ is returned. Otherwise, α-Boosting defines an instance PGα with the same underlying bipartite graph as PG and valuations (v′ij , w′ji ) with

7 Note that SW(M ∗ ) > 0, as E(PG) ̸= ∅.

and w′ji defined analogously. It then returns the matching M that is obtained by running the version of the Gale-Shapley algorithm that handles incomplete preferences (see [Gusfield and Irving, 1989]) on PGα, with ties broken arbitrarily. 8

Denote m = |E(PG)|. Since an optimal matching for PG can be computed in time O(m1+o(1) ) [Chen et al., 2025], PGα can be constructed in time O(m), and the Gale-Shapley algorithm on PGα runs in time O(mlogn), the complexity of α-Boosting is O(mlogn). In the special case of µ = 1, an algorithm with runtime of O(n2 ) has already been proposed by Anshelevich et al. [2013]. However, it is not trivial whether this algorithm can be generalized for µ ∈ (0, 1).

Note that M is a matching for PG if and only if it is a matching for PGα. Throughout this section, we will specify the preference graph (PG or PGα) in the subscript when relevant, and omit it otherwise. The main result of this section is the following theorem:

Theorem 1. Let α ∈ (0, 1]. Then, for any instance of α-SMCTI, α-Boosting returns an α-stable matching and achieves an approximation guarantee of f(α, µ) with

which is best possible.

Proof. Consider an instance PG of α-SMCTI. If α ≤ µ µ+1 , then α-Boosting returns M ∗ of PG which is α-stable (Proposition 1), thus achieving an approximation guarantee of 1 in this case. Therefore, assume that α > µ µ+1 and let M be the matching returned by α-Boosting. We start by showing that M is α-stable. Let (i, j) be a pair which is not in M. We distinguish two cases:

1. If i did not propose to j during the execution of theGaleShapley algorithm, then we must have that v′iM(i) ≥ v′ij . By definition, it holds that 1α viM(i) ≥ v′iM(i) ≥ v′ij ≥ vij, so in particular, viM(i) ≥ αvij. Therefore, (i, j) cannot be α-blocking.
2. Otherwise, i proposed to j but j rejected i, so it must hold that w′jM(j) ≥ w′ji . Again by definition, it holds that 1α wjM(j) ≥ w′jM(j) ≥ w′ji ≥ wji, so wjM(i) ≥ αwji and (i, j) cannot be α-blocking.

Next, we establish the approximation guarantee by fixing an optimal matching M ∗ for PG and constructing a mapping g : M ∗ → M. The main idea is that f maps each edge in the optimal matching either to itself or to an adjacent edge of comparable value.

Let (i, j) ∈ M ∗ . If (i, j) ∈ M, we set g(i, j) = (i, j). Otherwise, v′iM(i) ≥ v′ij or w′jM(j) ≥ w′ji . If the first condition holds, we set g(i, j) = (i,M(i)). Since (i,M(i)) /∈

8 The Gale-Shapley algorithm operates on ordinal preferences, but any set of cardinal preferences can be uniquely converted into this form.

M ∗ , it follows that viM(i) = v′iM(i) ≥ v′ij = 1α vij, and combining with the definition of µ-bounded valuations leads to

If only the second condition holds, we set g(i, j) = (M(j), j), which yields an analogous bound. Now, if (i, j) ∈ M and (i, j) /∈ M ∗ , it could be that two edges (i, j ′ ) ∈ M ∗ and (i′ , j) ∈ M ∗ are mapped to (i, j). In this case we have that αvij ≥ vij ′ and αwji ≥ wji′ , so

Since 1 > 1α · µ µ+1 , µα > 1α · µ µ+1 and edges in M ∗ are mapped to adjacent edges in M or itself (if in M), we obtain

proving that α-Boosting is f(α, µ)-approximate as in (4). Furthermore, this is best possible by Proposition 1.

5 Hardness of Optimal α-Stable Matchings

As shown in the previous section, α-Boosting always returns an α-stable matching that recovers at least 1/α · µ/(µ+1) of the optimal social welfare. However, it need not be an optimal α-stable matching. In this section, we consider the problem of finding an optimal α-stable matching.

Integer Linear Program of α-SMCTI. Given a matching M for a preference graph PG(L∪R, (vij), (wji)), we define its assignment matrix as x(M) = (xij)i∈L,j∈R, where xij = 1 if the pair (i, j) ∈ M, and xij = 0 otherwise. The set of all matchings can be described by the following system of inequalities:∑j∈R xij ≤ 1 ∀i ∈ L (5)

Below, we show that the α-stability property can be described by two different linear constraints.

Proposition 3. Let M be a matching for PG(L ∪ R, (vij), (wji)) and let α ∈ (0, 1]. Then, M is α-stable if and only if x(M) satisfies

Proof. Towards a contradiction, suppose that M is an αstable matching and there exists (i, j) ∈ E(PG) such that (8) does not hold. In this case it must be that both summations in

(8) are equal to 0, and so viM(i) < αvij and wjM(j) < αwji. This implies that (i, j) is an α-blocking pair which contradicts that M is α-stable. For the other direction note that if (8) is satisfied for a matchingM, this implies that there is no α-blocking pair (i, j) ∈ E(PG) as (i, j) would otherwise not satisfy (8), implying that M is α-stable.

Proposition 4. Let M be a matching for PG(L ∪ R, (vij), (wji)) and let α ∈ (0, 1]. Then, M is α-stable if and only if x(M) satisfies

Proof. Let M be an α-stable matching, and suppose that for a certain (i, j) ∈ E(PG) we have that ∑k:αwji>wjk xkj = 1. This means that j is paired with an agent they find less desirable than i by a factor of α. Since M is α-stable, we must have viM(i) ≥ αvij. In particular, ∑l:vil≥αvij xil = 1. This settles one direction. For the other direction, we proceed by contrapositive. Suppose that M is not α-stable, and let (i, j) be an α-blocking pair, so viM(i) < αvij and wjM(j) < αwji. The first implies that M(i) /∈ {l : vil ≥ αvij}, and therefore ∑l:vil≥αvij xil = 0. The second implies that M(j) ∈ {k : αwji > wjk}, so ∑k:αwji>wjk xkj = 1 and (9) does not hold for (i, j) which concludes the proof.

Using Propositions 3 and 4, we can describe the set of all α-stable matchings via constraints (5)-(7), together with either (8) or (9). Thus, computing an α-stable matching is equivalent to solving the integer program that maximizes the objective ∑(i,j)∈E(PG) (vij + wji)xij subject to these constraints. The crux, however, is that integer programs are not known to be solvable in polynomial time.

Notably, for the special case of stable matchings (i.e., α = 1) with strict preference orders, Rothblum [1992] and Vande Vate [1989] showed that the extreme points of the polytope defined by (5), (6) and

together with (8) or (9), are integral. 9 Consequently, in this case, solving the corresponding linear program (which can be done in polynomial time) yields an integral optimal solution. That is, for α = 1 we can find an optimal α-stable matching by solving the respective linear program. This naturally raises the question of whether the same holds for α < 1. We answer this question in the negative by showing that the problem is NP-hard, even when α is arbitrarily close to 1.

To prove our hardness results, we consider certain special cases of our α-SMCTI problem. We denote these more restrictive variants by omitting the respective letters from the acronym. In particular, SMCT (SMT) refers to the stable matching variant with cardinal (ordinal) preferences, ties allowed, and complete preference lists. Given a weak order relation ⪰i for i ∈ L, we write j1 ⪰i j2 to indicate that i (weakly) prefers j1 over j2; the relation ⪰j for j ∈ R is defined analogously.

9 In these papers, preference lists are given as order relations, but the generalization to cardinal preferences is almost immediate.

Given an instance I of SMT and (i, j) ∈ L × R, we define the cost cij of agent i for j as the position j occupies in i's preference list (the cost cji of agent j for i is defined analogously). Agents in the same tie group share the same cost, which will be equal to the number of agents ranked strictly above them plus one. We define the weight of M as w(M) := ∑u∈L∪R cuM(u), where cuM(u) = ∞ whenever u is lonely under M. We say that a matching is egalitarian if its weight is minimum among all stable matchings of I.

Let EGALITARIAN-SMT-OPT denote the optimization problem of finding an egalitarian stable matching given an instance of SMT. Manlove et al. [2002] proved that EGALITARIAN-SMT-OPT is hard to approximate. In particular, this means that the following decision problem is also NP-hard:

MIN-COST-SMT: Given an instance of SMT and K ∈ R+, is there a stable matching M such that w(M) ≤ K?

The decision problem we are interested in here is:

MAX-WEIGHT-α-SMCT: Given an instance of α-SMCT and ω ∈ R+, is there an α-stable matching M such that SW(M) ≥ ω?

Theorem 2. Given α ∈ ( n-1 n , 1), MAX-WEIGHT-α-SMCT is NP-complete.

Proof. It can easily be verified that MAX-WEIGHT-α-SMCT is in NP. Let α ∈ ( n-1 n , 1). We define a polynomial-time reduction from SMT to α-SMCT.

Given an instance I of SMT, let Pi = {j i1 , . . . , j in } denote the preference list of i, which potentially includes ties. Let PG be an instance of α-SMCT with the same underlying graph as I. For each (i, j) ∈ L ×R, we define the cardinal preferences as vij = -cij + n + 1 and wji = -cji + n + 1. Note that as the costs are in the range [1, n], so are the valuations by construction.

It trivially holds that M is a matching for PG if and only if M is a matching for I. We will prove that a matching M is α-stable for PG if and only if M is stable for I by showing that a pair (i, j) is α-blocking for PG if and only if it is blocking for I. Note that one direction holds by construction: take (i, j) to be α-blocking for PG, i.e. viM(i) < αvij < vij and wjM(j) < αwji < wji. This can only be the case if cij < ciM(i) and cji < cjM(j), so (i, j) is blocking for I. For the other direction, suppose that (i, j) is blocking for I, i.e. cij < ciM(i) and cji < cjM(j). This implies that M(i) and j belong to different tie groups in i's preference list, and i and M(j) belong to different tie groups in j's. We want to show that viM(i) < αvij and wjM(j) < αwji, thus it is enough to show that the valuation of an element in a tie group times α is greater than the valuation of any element in a following tie group. The most restrictive case happens when each tie group contains exactly one agent, in which case the largest ratio arises between the first and second agent in the preference list. More formally, let 2 ≤ x ≤ n, then viM(i) vij ≤ x-1 x ≤ n-1 n < α, which indeed gives viM(i) < αvij. The case of wjM(j) < αwji follows analogously.

Take K ∈ (1, 2n(n + 1)), and set ω = 2n(n + 1) - K. We now show that there exists an α-stable matching M for PG with SW(M) ≥ ω if and only if there exists a stable matching M ′ for I with w(M ′ ) ≤ K. Suppose that M is an α-stable matching for PG with SW(M) ≥ ω. It holds that

where the last equality is due to M being perfect (since preference orders are complete). Thus, w(M) ≤ 2n(n+1)-ω = K. In particular, M is a stable matching for I with w(M) ≤ K. Analogously, suppose that M is a stable matching for I with w(M) ≤K. It holds that

and so SW(M) ≥ 2n(n + 1) - K = ω. Thus M is an α-stable matching for PG with SW(M) ≥ ω.

Note that we prove that MAX-WEIGHT-α-SMCT is NPcomplete for α ∈ ( n-1 n , 1). As mentioned above, the problem is solvable in polynomial time when α = 1, and when α ≤ µ µ+1 by Theorem 1. This reveals an interesting threshold phenomenon. Note that µ is determined by the valuations defined in the reduction and can be as small as 1/n; the proof can be adapted to larger values of µ < 1 by altering the way the valuations are defined. Clearly, Theorem 2 implies NP-hardness for more general optimization versions such as α-SMCTI.

6 Conclusion and FutureWork

We study the interplay between stability and social welfare in two-sided matching markets with cardinal preferences, ties, and incomplete preference lists. By adopting the relaxed notion of α-stability, we provide a complete characterization of the stability-efficiency tradeoff under asymmetric valuations and show that relaxing stability can substantially improve achievable efficiency guarantees. We derive a polynomialtime algorithm that computes an α-stable matching attaining the best possible efficiency guarantee. Finally, our hardness results show that computing optimal α-stable matchings becomes intractable even under slight relaxations of stability, i.e., for α < 1.

Our work leaves several interesting questions for future research. A natural direction is to further refine the complexity landscape of α-stable matchings. In particular, it would be interesting to determine whether computing an optimal α-stable matching is NP-hard for all α ∈ (µ/µ+1, 1), and to understand the approximability of optimal α-stable matchings within this range. Depending on these hardness results, a natural next step is to leverage predictions to guide the computation of near-optimal α-stable matchings; notably, our algorithm already draws inspiration from this paradigm. Other promising directions include extending the framework to many-to-one matching markets and exploring hybrid notions of stability that incorporate different behavioral assumptions.