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 [1]–[4], which involves two sets of agents \(L\) and \(R\) of size \(n \ge 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 \(v_{ij}\) to denote the (positive) valuation that an agent \(i \in L\) assigns to \(j \in R\), and \(w_{ji}\) to denote the (positive) valuation that agent \(j \in R\) assigns to \(i \in 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., [2]).

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) = \sum_{(i,j) \in M} (v_{ij} + w_{ji})\). A stable matching \(M\) is said to be \(\gamma\)-efficient with \(\gamma \in (0,1]\) if it recovers a \(\gamma\)-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 \(\mu \in (0,1]\): the valuations are \(\mu\)-bounded if \(\frac{v_{ij}}{w_{ji}} \in [\mu, \frac{1}{\mu}]\) for every pair \((i,j)\) with \(v_{ij} > 0\) and \(w_{ji} > 0\). Note that the valuations are symmetric for \(\mu = 1\), and become increasingly asymmetric as \(\mu\) decreases.

Consider the example in Figure 1 and note that the valuations are \(\mu\)-bounded. It is easy to verify that, for \(\epsilon > 0\), the instance has a unique stable matching \(M = \{(i_2, j_1)\}\). On the other hand, the social welfare optimal matching is \(M^* = \{(i_1, j_1), (i_2, j_2)\}\). In terms of social welfare, we have \(SW(M) = 1+\epsilon\) and \(SW(M^*) = \frac{(\mu+1)}{\mu}\). Thus, the efficiency of the (unique) stable matching is \(\frac{(1+\epsilon)\mu}{(\mu+1)}\). As a consequence, for this instance we cannot guarantee that any stable matching recovers (strictly) more than a fraction of \(\frac{\mu}{(\mu+1)}\) of the optimal social welfare. In particular, the efficiency of a stable matching becomes unbounded as \(\mu\) approaches \(0\), or, said differently, as the valuations become increasingly asymmetric. In fact, this tradeoff has been observed before by [5] for the two limiting cases \(\mu = 1\) and \(\mu \rightarrow 0\); but, here, we get a smooth interpolation for any \(\mu\) 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 [5]. 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 \(\alpha\)-stability, introduced by [5]. 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 \(\alpha\). Formally, a matching \(M\) is \(\alpha\)-stable with \(\alpha \in (0,1]\) if there is no pair \((i,j)\) such that \(v_{iM(i)}<\alpha v_{ij}\) and \(w_{jM(j)}<\alpha w_{ji}\), where \(M(i)\) and \(M(j)\) denote the matches of \(i\) and \(j\) under \(M\), respectively. As \(\alpha\) decreases, agents require a larger improvement to switch, making the stability condition less restrictive.

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

1.1 Our Contributions↩︎

We study how the relaxed notion of \(\alpha\)-stability influences social welfare efficiency under asymmetric (\(\mu\)-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 stability–efficiency tradeoff (Section 3); see Figure 2 for an illustration. We prove that any \(\alpha\)-stable matching is at least \((\alpha \cdot \frac{\mu}{(\mu+1)})\)-efficient (Proposition 2). Thus, the worst-case efficiency of \(\alpha\)-stable matchings becomes worse as \(\alpha\) decreases. On the other hand, we prove an upper bound of \(\frac{1}{\alpha}\cdot \frac{\mu}{(\mu+1)}\) on the best-case efficiency of \(\alpha\)-stable matchings. In particular, for smaller values of \(\alpha\), \(\alpha\)-stable matchings can achieve a (significantly) better efficiency guarantee than stable matchings, with the magnitude of improvement depending on the ratio \(\frac{\mu}{(\mu+1)}\). Also, for \(\alpha \le \frac{\mu}{(\mu+1)}\), any optimal matching is \(\alpha\)-stable, implying that \(\alpha\)-stable matchings can be \(1\)-efficient. At the same time, our result shows that it is impossible to surpass the bound of \(\min(1, \frac{1}{\alpha}\cdot \frac{\mu}{(\mu+1)})\). This provides a complete characterization of the stability–efficiency tradeoff for \(\alpha\)-stable matchings under \(\mu\)-bounded valuations; previously, only the case \(\mu = 1\) was understood [5].

2. Computing \(\alpha\)-Stable Matchings: We present a polynomial-time algorithm, termed \(\alpha\)-Boosting, that computes an \(\alpha\)-stable matching achieving the best-possible worst-case efficiency guarantee (Section 4, Theorem 1). For \(\alpha \leq \frac{\mu}{(\mu + 1)}\), the algorithm simply returns a social welfare optimal matching, which is \(\alpha\)-stable and achieves a 1-approximation. For \(\alpha > \frac{\mu}{(\mu + 1)}\), \(\alpha\)-Boosting uses a more sophisticated approach inspired by [8]: it first computes a social welfare optimal matching, inflates the values of its edges by a factor \(\frac{1}{\alpha}\), and then applies the Gale–Shapley algorithm to the modified instance. Remarkably, we can show that this algorithm has an approximation guarantee of \(\frac{1}{\alpha} \cdot \frac{\mu}{(\mu+1)}\), which is best possible.

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

1.2 Related Work↩︎

The stable matching problem was first introduced by [1], 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. [11] 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. [12] 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, [13] proved that finding an optimal stable matching is NP-hard, and [14] showed that the matching resulting from the Gale–Shapley algorithm may not be optimal for either side. More recently, [15] 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. [5] do this and define the (multiplicative) notion of \(\alpha\)-stability, which we consider in this paper. They consider three scenarios: vertex-labeled graphs, symmetric edge-labeled graphs, and asymmetric edge-labeled graphs.³ In the latter case, they showed that the social welfare of an \(\alpha\)-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 \(\alpha\)-stable matching with social welfare at least \(\frac{1}{2\alpha}\) times that of an optimal matching.⁴ They also provided an algorithm that finds such a matching in \(O(n^2)\) time.

\(\alpha\)-Stability was also analyzed in the context of fractional matchings by [16]. They propose a polynomial time algorithm that computes an \(\alpha\)-stable fractional matching which guarantees an \(\alpha\)-approximation. They also prove that the problem of finding an optimal \(\alpha\)-stable fractional matching is hard to approximate. Different notions of stability have also been considered in the literature (e.g., [17]–[21]).

The linear programming approach to the stable matching problem has been widely studied. [9] 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. [10] later expanded on these results and offered simplified proofs. However, they do not easily generalize to the \(\alpha\)-stability setting. On the other hand, [13] 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. [8] 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 Gale–Shapley algorithm. Our \(\alpha\)-Boosting algorithm builds upon this procedure.

2 Preliminaries↩︎

2.0.0.1 Stable Matching with Cardinal 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.⁵ 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 \in L\) has a non-negative valuation \(v_{ij}\) for every \(j \in R\), and each agent \(j \in R\) has a non-negative valuation \(w_{ji}\) for every \(i \in L\). The valuations of an agent comprise their preference list. The interpretation of the valuations \((v_{ij})\) for agent \(i \in L\) is as follows: agent \(i\) prefers to be matched to \(j_1\) rather than \(j_2\) if \(v_{ij_1} > v_{ij_2}\), \(i\) is indifferent between \(j_1\) and \(j_2\) if \(v_{ij_1} = v_{ij_2}\), and \(i\) does not want to be matched to \(j\) if \(v_{ij} = 0\). The interpretation of the valuations \((w_{ji})\) for an agent \(j \in R\) follows analogously. We define \((i,j)\) as a pair if \(i \in L\) and \(j \in R\). We say that \((i,j)\) is a compatible pair if \(v_{ij}\neq 0\) and \(w_{ji}\neq 0\). The preference graph \(\mathop{\mathrm{PG}}(L\cup R, (v_{ij}), (w_{ji}))\) (or simply \(\mathop{\mathrm{PG}}\), when clear from context) is the bipartite graph that represents these relational preferences: the vertex set is \(L\cup R\), the edge set consists of all compatible pairs, i.e., \(E(\mathop{\mathrm{PG}}) =\{(i,j)\in L\times R:v_{ij}\neq 0 \text{ and } w_{ji}\neq 0\},\) and each edge \((i,j) \in E(\mathop{\mathrm{PG}})\) is associated with two (positive) weights \(v_{ij}\) and \(w_{ji}\). We assume w.l.o.g. that the preference graph \(\mathop{\mathrm{PG}}\) is non-empty.

2.0.0.2 \(\alpha\)-Stable Matchings. 

Given a preference graph \(\mathop{\mathrm{PG}}\), a matching \(M_{\mathop{\mathrm{PG}}}\) (or simply \(M\), when clear from context) for \(\mathop{\mathrm{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\cup R \rightarrow L \cup R \cup \emptyset\) such that \(M(i)=j\) and \(M(j)=i\) whenever \((i,j)\in M\). Otherwise, if there is no \(j \in R\) such that \((i,j) \in M\), we set \(M(i)= \emptyset\), in which case we will say that \(i\) is lonely under \(M\) and define \(v_{iM(i)}=0\). For \(j \in R\), \(M(j)=\emptyset\) and \(w_{j M(j)}\) are defined similarly. We use \(\text{Mat}(\mathop{\mathrm{PG}})\) to refer to the set of matchings for \(\mathop{\mathrm{PG}}\). A matching \(M\) is said to be (inclusion-wise) maximal if there is no edge \(e\in E(\mathop{\mathrm{PG}}) \setminus M\) such that \(M\cup \{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.⁶ In this paper we consider a relaxed stability notion, called \(\alpha\)-stability (see also [5]).

Note that the original stability notion is equivalent to \(1\)-stability. By definition, an \(\alpha\)-stable matching \(M\) is also \(\alpha'\)-stable for every \(\alpha' \le \alpha\). In particular, a stable matching is \(\alpha\)-stable for every \(\alpha\in(0,1]\). This observation also implies that, for any preference graph \(\mathop{\mathrm{PG}}\), an \(\alpha\)-stable matching is guaranteed to exist for every \(\alpha \in (0, 1]\) as a stable matching always exists (see [2]). Observe that any \(\alpha\)-stable matching must be (inclusion-wise) maximal.

2.0.0.3 Benchmark. 

We are interested in how the quality of \(\alpha\)-stable matchings changes depending on \(\alpha\). To this end, we define the social welfare of a matching \(M\) as \(SW(M)=\sum_{(i,j)\in M}(v_{ij}+w_{ji})\). 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 \(\mathop{\mathrm{PG}}\), an optimal matching is a matching of maximum social welfare and will be denoted by \(M^*\), i.e., \(M^*\in \text{Mat}(\mathop{\mathrm{PG}})\) and \(SW(M^*) \ge SW(M)\) for every matching \(M\in \text{Mat}(\mathop{\mathrm{PG}})\). Throughout this work, we use the optimal social welfare as a benchmark when evaluating the quality of a matching.

2.0.0.4 \(\mu\)-Bounded Valuations. 

As it turns out, the efficiency of \(\alpha\)-stable matchings does not only depend on the stability parameter \(\alpha\), but also on the “degree of asymmetry” of the underlying valuations. The following notion formalizes this. Given a preference graph \(\mathop{\mathrm{PG}}\), the valuations of the agents are \(\mu\)-bounded with \(\mu \in (0,1]\) if \(\mu w_{ji}\leq v_{ij}\leq w_{ji}/\mu\) for all \((i,j)\in E(\mathop{\mathrm{PG}})\). Intuitively, for \(\mu = 1\) the valuations are symmetric (i.e., \(v_{ij} = w_{ji}\) for all \((i,j) \in E(\mathop{\mathrm{PG}})\)), and they become increasingly asymmetric as \(\mu\) decreases.

2.0.0.5 Computing \(\alpha\)-Stable Matchings. 

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

3 Stability–Efficiency Tradeoff↩︎

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

Note that when \(\alpha = 1\), the bounds in Propositions 1 and 2 coincide. Also note that by relaxing the stability requirement to \(\alpha\)-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 \(\alpha\)-Stable Matchings↩︎

Our aim for this section is to design an algorithm which, given any instance of \(\alpha\)-SMCTI with \(\mu\)-bounded valuations, achieves an approximation guarantee of 1 whenever \(\alpha\leq \frac{\mu}{\mu+1}\), and of \(\frac{1}{\alpha}\cdot \frac{\mu}{\mu+1}\) otherwise. Note that in light of Proposition 2, this is best possible. We start by introducing our algorithm, called \(\alpha\)-Boosting, which builds upon [1] and [8].

4.0.0.1 \(\alpha\)-Boosting Algorithm.

Given a preference graph \(\mathop{\mathrm{PG}}\) and a parameter \(\alpha \in (0,1]\) as input, \(\alpha\)-Boosting first computes an optimal matching \(M^*\) for \(\mathop{\mathrm{PG}}\). If \(M^*\) is \(\alpha\)-stable, then \(M^*\) is returned. Otherwise, \(\alpha\)-Boosting defines an instance \(\mathop{\mathrm{PG}}^{\alpha}\) with the same underlying bipartite graph as \(\mathop{\mathrm{PG}}\) and valuations \((v'_{ij}, w'_{ji})\) with \[v'_{ij}=\begin{cases} \frac{1}{\alpha} v_{ij}, & \text{if }(i,j)\in M^*, \\ v_{ij}, & \text{otherwise,} \end{cases}\] 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 [2]) on \(\mathop{\mathrm{PG}}^{\alpha}\), with ties broken arbitrarily.¹⁰

Denote \(m = |E(\mathop{\mathrm{PG}})|\). Since an optimal matching for \(\mathop{\mathrm{PG}}\) can be computed in time \(O(m^{1+o(1)})\) [22], \(\mathop{\mathrm{PG}}^{\alpha}\) can be constructed in time \(O(m)\), and the Gale-Shapley algorithm on \(\mathop{\mathrm{PG}}^{\alpha}\) runs in time \(O(m \log n)\), the complexity of \(\alpha\)-Boosting is \(O(m \log n)\). In the special case of \(\mu = 1\), an algorithm with runtime of \(O(n^2)\) has already been proposed by [5]. However, it is not trivial whether this algorithm can be generalized for \(\mu \in (0,1)\).

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

5 Hardness of Optimal \(\alpha\)-Stable Matchings↩︎

As shown in the previous section, \(\alpha\)-Boosting always returns an \(\alpha\)-stable matching that recovers at least \(\frac{1}{\alpha}\cdot \frac{\mu}{(\mu+1)}\) of the optimal social welfare. However, it need not be an optimal \(\alpha\)-stable matching. In this section, we consider the problem of finding an optimal \(\alpha\)-stable matching.

5.0.0.1 Integer Linear Program of \(\alpha\)-SMCTI.

Given a matching \(M\) for a preference graph \(\mathop{\mathrm{PG}}(L\cup R, (v_{ij}), (w_{ji}))\), we define its assignment matrix as \(x(M)=(x_{ij})_{i\in L, j\in R}\), where \(x_{ij}=1\) if the pair \((i,j)\in M\), and \(x_{ij}=0\) otherwise. The set of all matchings can be described by the following system of inequalities: \[\begin{align} \textstyle\sum_{j\in R}x_{ij}&\leq 1 \qquad\;\;\; \forall i\in L \tag{4} \\ \textstyle\sum_{i\in L}x_{ij}&\leq 1 \qquad\;\;\; \forall j\in R \tag{5}\\ x_{ij}& \in \{0, 1\} \quad \forall (i,j)\in E(\mathop{\mathrm{PG}}).\tag{6} \end{align}\]

Below, we show that the \(\alpha\)-stability property can be described by two different linear constraints.

Using Propositions 3 and 4, we can describe the set of all \(\alpha\)-stable matchings via constraints (4 )–(6 ), together with either (?? ) or (?? ). Thus, computing an \(\alpha\)-stable matching is equivalent to solving the integer program that maximizes the objective \(\sum_{(i,j) \in E(\mathop{\mathrm{PG}})} (v_{ij}+ w_{ji}) x_{ij}\) 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., \(\alpha = 1\)) with strict preference orders, [10] and [9] showed that the extreme points of the polytope defined by 4 , 5 and \[x_{ij} \ge 0 \quad \forall (i,j)\in E(\mathop{\mathrm{PG}}),\label{eq:relaxation}\tag{7}\] together with (?? ) or (?? ), are integral.¹¹ Consequently, in this case, solving the corresponding linear program (which can be done in polynomial time) yields an integral optimal solution. That is, for \(\alpha = 1\) we can find an optimal \(\alpha\)-stable matching by solving the respective linear program. This naturally raises the question of whether the same holds for \(\alpha < 1\). We answer this question in the negative by showing that the problem is NP-hard, even when \(\alpha\) is arbitrarily close to 1.

To prove our hardness results, we consider certain special cases of our \(\alpha\)-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 \(\succeq_i\) for \(i \in L\), we write \(j_1 \succeq_i j_2\) to indicate that \(i\) (weakly) prefers \(j_1\) over \(j_2\); the relation \(\succeq_j\) for \(j \in R\) is defined analogously.

Given an instance \(I\) of SMT and \((i,j)\in L\times R\), we define the cost \(c_{ij}\) of agent \(i\) for \(j\) as the position \(j\) occupies in \(i\)’s preference list (the cost \(c_{ji}\) 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):=\sum_{u\in L\cup R}c_{uM(u)}\), where \(c_{uM(u)}=\infty\) 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. [13] 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\in \mathbb{R}^+\), is there a stable matching \(M\) such that \(w(M)\leq K\)?

The decision problem we are interested in here is:

Max-Weight-\(\alpha\)-SMCT: Given an instance of \(\alpha\)-SMCT and \(\omega\in \mathbb{R}^+\), is there an \(\alpha\)-stable matching \(M\) such that \(SW(M) \geq \omega\)?

Note that we prove that Max-Weight-\(\alpha\)-SMCT is NP-complete for \(\alpha \in (\frac{n-1}{n},1)\). As mentioned above, the problem is solvable in polynomial time when \(\alpha = 1\), and when \(\alpha \le \frac{\mu}{\mu+1}\) by Theorem 1. This reveals an interesting threshold phenomenon. Note that \(\mu\) is determined by the valuations defined in the reduction and can be as small as \(\frac{1}{n}\); the proof can be adapted to larger values of \(\mu < 1\) by altering the way the valuations are defined. Clearly, Theorem 2 implies NP-hardness for more general optimization versions such as \(\alpha\)-SMCTI.

6 Conclusion and Future Work↩︎

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 \(\alpha\)-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 polynomial-time algorithm that computes an \(\alpha\)-stable matching attaining the best possible efficiency guarantee. Finally, our hardness results show that computing optimal \(\alpha\)-stable matchings becomes intractable even under slight relaxations of stability, i.e., for \(\alpha < 1\).

Our work leaves several interesting questions for future research. A natural direction is to further refine the complexity landscape of \(\alpha\)-stable matchings. In particular, it would be interesting to determine whether computing an optimal \(\alpha\)-stable matching is NP-hard for all \(\alpha \in \bigl(\frac{\mu}{\mu+1}, 1\bigr)\), and to understand the approximability of optimal \(\alpha\)-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 \(\alpha\)-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.

References↩︎

---

1. Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands↩︎

2. Centrum Wiskunde & Informatica (CWI) and University of Amsterdam, The Netherlands↩︎

3. Our \(\mu\) parameter interpolates between symmetric edge-labeled (\(\mu=1\)) and asymmetric edge-labeled graphs (\(\mu\rightarrow 0\)).↩︎

4. Note that in [5], the approximation ratios are presented inversely compared to our notation.↩︎

5. 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 \(\forall j \in R' \setminus R\) it holds that \(v_{ij} = w_{ji} = 0\), \(\forall i \in L\).↩︎

6. This is sometimes referred to as weak stability.↩︎

7. We impose \(\alpha > 0\) as every matching is trivially \(0\)-stable.↩︎

8. This interval is well defined as \(\frac{1}{\alpha}-1<\frac{1}{\mu}\) since \(\alpha>\frac{\mu}{\mu+1}\).↩︎

9. Note that \(SW(M^*) > 0\), as \(E(\mathop{\mathrm{PG}}) \neq \emptyset\).↩︎

10. The Gale–Shapley algorithm operates on ordinal preferences, but any set of cardinal preferences can be uniquely converted into this form.↩︎

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