Stable matching problem
The stable matching problem, also known as the stable marriage problem, is a fundamental problem in combinatorial optimization and game theory that involves pairing equal-sized sets of agents from two distinct sides—such as men and women, students and colleges, or doctors and hospitals—according to their strict preference rankings, such that the resulting matching is stable: no agent prefers to remain unmatched, and no pair of agents from opposite sides both prefer each other to their assigned partners.[1] This concept was first formalized by economists David Gale and Lloyd Shapley in their 1962 paper "College Admissions and the Stability of Marriage," where they proved that a stable matching always exists for any set of preferences and introduced the deferred acceptance algorithm to compute it efficiently.[2]
The deferred acceptance algorithm operates iteratively: agents on one side (the "proposers") offer to their most preferred available partners on the other side (the "acceptors"), who tentatively accept the best offer received so far and reject the rest; rejected proposers then offer to their next preferences, and the process continues until no further proposals are made, yielding a stable outcome in polynomial time.[1] Key properties include that the algorithm produces a proposer-optimal stable matching—meaning it is the best possible stable outcome for the proposing side, though pessimal for the other—and that the set of all stable matchings forms a lattice under a natural partial order, allowing for the identification of optimal and pessimal stable matchings for each side.[1] These guarantees hold under the assumption of complete, strict preferences without ties, though extensions address incomplete lists, ties, and one-sided preferences.[2]
Beyond theory, the stable matching framework has profoundly influenced market design and mechanism design, with the Gale-Shapley algorithm adapted for real-world two-sided matching markets to promote stability and fairness.[2] Notable applications include the National Resident Matching Program (NRMP) in the United States, which since the 1950s has used a variant to assign over 43,000 medical residents to hospitals annually (as of 2025), preventing unstable "explosions" of renegotiations; school choice systems in cities like New York (implemented in 2003, reducing assignments to unpreferred schools by 90%) and Boston (2005), where student-proposing versions improved student outcomes by assigning more students to preferred schools; and kidney exchange programs employing related top-trading-cycles mechanisms inspired by stable matching principles.[1][2][3] The practical success of these systems contributed to the 2012 Nobel Prize in Economics awarded to Shapley and Alvin Roth for their foundational and applied work on stable allocations.[2]
Introduction
Definition and Motivation
The stable matching problem, commonly illustrated through the stable marriage problem, concerns pairing two distinct sets of equal size—such as men and women—where each individual in one set has an ordinal preference ranking over all members of the other set, with the goal of producing a complete matching that avoids any mutually preferred deviations.[4] This formulation seeks pairings where stability is achieved by ensuring no individual would benefit from switching partners with someone else who shares that preference.[2]
The motivation arises from real-world scenarios like arranging marriages or assigning students to colleges, where preferences must be respected to prevent dissatisfaction or "instability" in the outcomes; without stability, pairs might form outside the arrangement if both parties deem it preferable.[4] For instance, consider four men (A, B, C, D) and four women (W, X, Y, Z), each with their own rankings: suppose A ranks W first and Y last, while W ranks A low but prefers him over her assigned partner. An arbitrary matching pairing A with Y and W with, say, C could be unstable if A and W both prefer each other to their current partners, forming what is known as a blocking pair—a man-woman duo not matched together but who mutually rank one another higher than their assigned matches.[5] In contrast, a stable matching eliminates all such blocking pairs, ensuring the arrangement withstands no such challenges.[4]
Originating as a mathematical model for economic allocation problems like college admissions, the stable matching framework has broader applications in social and resource pairing contexts, where ordinal preferences guide equitable outcomes.[2] The problem admits a solution via the Gale-Shapley algorithm, which systematically constructs a stable matching.[4]
Historical Background
The stable matching problem emerged from practical challenges in economic and organizational contexts during the mid-20th century, particularly in response to chaotic markets for medical residencies in the United States. By the late 1940s, competition among hospitals for interns and medical students for desirable positions had led to increasingly early offers, reneging on commitments, and market instability, prompting the creation of the National Resident Matching Program (NRMP) in 1952 as a centralized clearinghouse to produce orderly pairings.[2] The NRMP employed a version of the deferred acceptance procedure from its early years to achieve stable assignments.[6] This initiative highlighted the need for stable assignment mechanisms in two-sided markets, drawing from broader economic theory on cooperative games and resource allocation developed in the 1950s, including Lloyd Shapley's foundational work on the core concept in cooperative game theory.[2]
The problem was formally introduced in 1962 by mathematicians David Gale and Lloyd Shapley in their seminal paper "College Admissions and the Stability of Marriage," published in The American Mathematical Monthly.[7] Motivated by real-world issues like college admissions and resident matching, Gale and Shapley defined the stable matching framework and provided the first constructive proof of the existence of stable outcomes through what became known as the deferred acceptance algorithm (also called the Gale-Shapley algorithm).[4] Their work bridged pure mathematics with applied economics, demonstrating that stable matchings always exist under specified preference structures, without relying on prices or other market-clearing devices.[6]
By the 1970s, the stable matching problem gained traction in operations research and computer science, with researchers adapting and implementing algorithms for practical applications such as university admissions. Notably, D. G. McVitie and L. B. Wilson published work in 1970 extending the framework to handle unequal set sizes and applying it to university admissions, which facilitated efficient software implementations.[8][9] In 1971, they developed computational procedures for finding all stable matchings.[10] Their work, including applications to asymmetric matching scenarios, marked a shift toward algorithmic efficiency and broader adoption in computational settings.[9]
A major milestone came in 2012, when the Nobel Memorial Prize in Economic Sciences was awarded to Alvin E. Roth and Lloyd S. Shapley for their contributions to the theory of stable allocations and the practice of market design.[6] Roth's empirical and design-oriented extensions of Gale and Shapley's ideas, including redesigns of the NRMP and kidney exchange programs, demonstrated the problem's enduring impact on real-world matching markets.[2]
Bipartite Matching Setup
The stable matching problem, also known as the stable marriage problem, is formally modeled using a complete bipartite graph G = (M \cup W, E), where M and W are disjoint sets each of size n representing two distinct groups of agents, such as men and women in the classic marriage context.[11] In the basic model, the edge set E consists of all possible pairs between M and W, reflecting the assumption of complete preferences where any agent from one set can potentially match with any from the other.[11] This bipartite structure captures the one-to-one pairing constraint inherent to the problem, ensuring no intra-set matches occur.
In the basic model with equal set sizes and complete preferences, a matching \mu is a perfect matching defined as a bijection from M to W, assigning each man m \in M to exactly one woman \mu(m) \in W, and vice versa.[11] This setup generalizes to other applications, like college admissions (with capacity constraints, as in the hospital-resident problem), but the core bipartite framework remains, though extensions may allow partial or many-to-one matchings.
Central to the model are the agents' strict ordinal preferences: for each man m \in M, there is a total order \succ_m over W, indicating his ranking of women from most to least preferred.[11] Similarly, each woman w \in W has a total order \succ_w over M.[11] These preferences are assumed to be complete, meaning every agent ranks all members of the opposite set, and strict, with no ties allowed in the rankings. This framework enables the evaluation of matchings for stability, where no unpaired pair both prefers each other over their assigned partners.
Preference Lists
In the stable matching problem, each agent on one side of the bipartite graph provides a preference list consisting of a strict ordering of potential partners on the other side, from most preferred to least preferred.[4] For instance, for a man m, the list ranks all women w_1, w_2, \dots, w_n such that m prefers w_i to w_j if w_i appears before w_j in the list.[4] Women provide analogous lists ranking the men.[4]
The model employs ordinal rankings, where only the relative order of preferences matters; cardinal utilities or numerical scores representing preference intensities are irrelevant and not required.[2] This ordinal approach simplifies the representation while capturing the essential comparative judgments needed for stability analysis.[2]
In extensions of the basic model (such as variants with unacceptable partners), preference lists may be incomplete, meaning an agent omits partners deemed unacceptable; in such cases, the bipartite graph includes only edges corresponding to acceptable pairs.[12] This can lead to partial rather than perfect matchings, where some agents remain unmatched if no acceptable options are available, influencing the feasibility of pairings.[4]
To illustrate the basic model with complete preferences, consider a small instance with three men (m_1, m_2, m_3) and three women (w_1, w_2, w_3), where the preference lists are as follows:
Men's Preference Lists:
| Man | Ranking |
|---|
| m_1 | w_1 > w_2 > w_3 |
| m_2 | w_2 > w_3 > w_1 |
| m_3 | w_3 > w_1 > w_2 |
| Woman | Ranking |
|---|
| w_1 | m_2 > m_3 > m_1 |
| w_2 | m_3 > m_1 > m_2 |
| w_3 | m_1 > m_2 > m_3 |
Stability and Properties
Definition of Stable Matching
In the stable matching problem, a matching \mu between two disjoint sets of agents, such as men M and women W with |M| = |W| = n, is a bijection \mu: M \cup W \to M \cup W such that \mu(m) \in W for m \in M, \mu(w) \in M for w \in W, and \mu(\mu(m)) = m. Each agent has a strict preference ordering over the members of the opposite set, represented as complete, strict rankings without ties. A matching \mu is defined to be stable if there exists no blocking pair—that is, no pair (m, w) with m \in M, w \in W, m \neq \mu(w), and w \neq \mu(m) such that w \succ_m \mu(m) (man m prefers woman w to his matched partner \mu(m)) and m \succ_w \mu(w) (woman w prefers man m to her matched partner \mu(w)). Formally, \mu is stable if \neg \exists (m, w) \in M \times W such that w \succ_m \mu(m) \land m \succ_w \mu(w).
To illustrate, consider a small instance with two men \{m_1, m_2\} and two women \{w_1, w_2\}, where the preference lists are as follows: m_1 prefers w_1 > w_2, m_2 prefers w_2 > w_1, w_1 prefers m_1 > m_2, and w_2 prefers m_2 > m_1. The matching \mu = \{(m_1, w_2), (m_2, w_1)\} is unstable because (m_1, w_1) forms a blocking pair: m_1 prefers w_1 over w_2 (w_1 \succ_{m_1} w_2) and w_1 prefers m_1 over m_2 (m_1 \succ_{w_1} m_2). In contrast, the matching \mu' = \{(m_1, w_1), (m_2, w_2)\} has no such blocking pair and is thus stable, as no agent prefers an alternative pairing that is mutually desired.
By definition, every matching in the problem is either stable or unstable. If a matching \mu is unstable, then at least one blocking pair must exist, as instability is precisely the presence of such a pair where both agents would deviate to improve their outcomes simultaneously. This dichotomy ensures the stability condition partitions all possible matchings into those that are stable (no incentives for pairwise deviation) and those that are not.
Existence and Uniqueness
In the stable marriage problem, where there are equal numbers of men and women, each with complete and strict preference lists, the Gale-Shapley theorem guarantees the existence of at least one stable matching.[4] This result holds for any such preference profile, ensuring that a matching free of blocking pairs always exists.[4] The theorem provides a constructive proof through the deferred acceptance algorithm, which terminates with a stable matching.[4]
Stable matchings are not always unique; multiple stable matchings can exist for the same preference lists. A stable matching is unique if and only if the man-optimal stable matching coincides with the woman-optimal stable matching, where the man-optimal (respectively, woman-optimal) matching is the one obtained by running the deferred acceptance algorithm with men (respectively, women) proposing.[13]
To illustrate multiplicity, consider a small instance with two men (m_1, m_2) and two women (w_1, w_2), with the following strict preferences:
- m_1: w_1 \succ w_2
- m_2: w_2 \succ w_1
- w_1: m_2 \succ m_1
- w_2: m_1 \succ m_2
The matching \mu_1 = \{(m_1, w_2), (m_2, w_1)\} is stable, as no blocking pair exists: m_1 and w_1 do not block because w_1 prefers her partner m_2 to m_1, and m_2 and w_2 do not block because m_2 prefers w_2 to his partner w_1 but w_2 prefers her partner m_1 to m_2. Similarly, the matching \mu_2 = \{(m_1, w_1), (m_2, w_2)\} is stable, as w_1 and m_2 do not block because m_2 prefers his partner w_2 to w_1, and w_2 and m_1 do not block because m_1 prefers his partner w_1 to w_2.[13] Here, \mu_1 is woman-optimal and \mu_2 is man-optimal, confirming non-uniqueness.[13]
The number of distinct stable matchings in an instance can vary significantly, reaching up to \Theta(c^n) for some constant c > 1 (with known bounds around $3.55^n),[14] though the average number over random preference profiles is much smaller, on the order of \Theta(\sqrt{n}).[15]
Algorithms
Gale-Shapley Algorithm
The Gale-Shapley algorithm, also known as the deferred acceptance algorithm, is a proposal-based procedure for finding a stable matching in the bipartite stable marriage problem, where there are equal numbers of men and women, each with strict preference lists over the opposite side. In this process, one side (typically the men, acting as proposers) iteratively proposes to their most preferred acceptable partners on the other side (the women, acting as acceptors), who respond by tentatively accepting or rejecting based on their own preferences. The algorithm alternates between these proposal and acceptance/rejection phases until no further proposals are possible, ensuring a complete matching without immediate commitments that could lead to instability.
The algorithm begins with all individuals unmatched. In each iteration, every unmatched man who still has acceptable women he has not yet proposed to selects his most preferred such woman and proposes to her. Each woman, upon receiving one or more proposals, tentatively accepts the one from her most preferred proposer among those received in the current round (or holds her previous tentative acceptance if better) and rejects all others. Rejected proposals free the proposing men to continue in the next iteration, while tentatively accepted men become provisionally matched but remain subject to potential displacement if a better proposal arrives later. This deferred acceptance mechanism prevents premature commitments and allows the process to explore the preference structure systematically.
The procedure can be formalized in the following pseudocode, assuming sets M of n men and W of n women, with preference lists P_m for each man m \in M and P_w for each woman w \in W:
Initialize all individuals as free (unmatched).
While there exists a free man m who has not proposed to every woman in P_m:
Let w be the highest-ranked woman in P_m to whom m has not yet proposed.
If w is free:
Tentatively match m and w; mark m as matched.
Else if w prefers m to her current tentative match m':
Tentatively match m and w; free m'.
Else:
Reject m's proposal.
End while.
The final tentative matches form the stable matching.
Initialize all individuals as free (unmatched).
While there exists a free man m who has not proposed to every woman in P_m:
Let w be the highest-ranked woman in P_m to whom m has not yet proposed.
If w is free:
Tentatively match m and w; mark m as matched.
Else if w prefers m to her current tentative match m':
Tentatively match m and w; free m'.
Else:
Reject m's proposal.
End while.
The final tentative matches form the stable matching.
This pseudocode captures the iterative nature, where proposals proceed down each man's list until exhaustion or acceptance.
The algorithm always terminates after a finite number of steps, specifically in at most n^2 proposals, since each of the n men can propose to each of the n women at most once, and no man proposes to the same woman twice. Upon termination, the resulting matching is stable, as any potential blocking pair would contradict the proposal and rejection history.
Optimality and Complexity
The Gale-Shapley algorithm, when executed with men as proposers, yields the man-optimal stable matching. In this outcome, every man is paired with the most preferred woman possible among all stable matchings, where "possible" means the woman to whom he is matched in at least one stable matching.[4] This matching is simultaneously woman-pessimal, meaning every woman receives her least preferred partner among all stable matchings.[16]
To establish man-optimality, consider a proof by contradiction. Suppose there exists another stable matching M' in which some man m is paired with a woman w' whom he ranks below his partner w in the Gale-Shapley matching M. Since m proposed to women in decreasing order of preference and was ultimately matched to w, he must have proposed to w' earlier (as m prefers w' to w) and been rejected by w'. At the time of rejection, w' held a proposal from some man m' whom she preferred to m. In M', m' is paired with some woman w'', but since m' had not yet proposed to w'' when proposing to w', m' prefers w' to w''. Thus, m' and w' form a blocking pair in M', contradicting its stability. This argument shows no such M' exists, confirming M is man-optimal.[17]
The algorithm's time complexity is O(n^2), achieved through an implementation where each of the n men proposes to up to n women, with constant-time operations for maintaining proposal lists and preferences via preprocessing (e.g., ranking arrays). No asymptotically faster general algorithm is known for finding a stable matching under standard computational models with arbitrary preference lists.[17]
Key Theorems and Results
Rural Hospitals Theorem
The Rural Hospitals Theorem states that, in the hospital-residents problem with strict preferences, the number of positions filled at each hospital is the same in every stable matching, and moreover, any hospital that does not fill all of its positions in one stable matching receives precisely the same number of residents and the exact same set of residents in every stable matching.[18] This result generalizes key properties from the one-to-one bipartite stable matching model to the many-to-one setting, where hospitals have capacities greater than one.
The proof intuition relies on the definition of stability: suppose a hospital H is underfilled in some stable matching \mu, meaning it has fewer residents than its capacity. In any other stable matching \mu', if H were assigned a different set of residents or more residents, this would imply the existence of a blocking pair involving a resident who prefers H to their assignment in \mu, but since H is underfilled in \mu, no such resident exists who both prefers an open position at H and is not already matched there without violating stability elsewhere; thus, the assignment to underfilled hospitals remains invariant across all stable matchings. Unfilled positions at such hospitals cannot participate in blocking pairs, as they are available, so any potential deviation would contradict the stability of the original matching, fixing the assignments for these hospitals while allowing variation only among fully filled ones.
To illustrate, consider a small instance with three hospitals having capacities 1, 1, and 2, respectively, and five residents. In this setup, the total capacity is four positions, but due to preference structures where the larger hospital is less preferred overall, it ends up underfilled (assigned only one resident) in every stable matching, and that single resident is the same across all such matchings; meanwhile, the two smaller (full) hospitals receive varying residents depending on the specific stable matching, but always fill their single positions.[11] This demonstrates how the theorem identifies fixed outcomes for underfilled hospitals despite multiple stable matchings existing.
The theorem has significant implications for market design in centralized matching systems, such as the National Resident Matching Program, revealing that underfilling at certain hospitals (often rural or less desirable ones) is a structural feature of the preference profile rather than an artifact of a particular algorithm or stable matching choice. In particular, if shortages exist—meaning the total number of acceptable positions exceeds the number of residents seeking matches—no resident-optimal stable matching can match all residents, as the set of unmatched residents is identical across all stable matchings, underscoring the need for mechanisms beyond stability to address imbalances.
Lattice Structure of Stable Matchings
The set of all stable matchings in the stable marriage problem forms a distributive lattice under a natural partial order known as the rotation poset. This partial order, denoted by ≥_m for the men's perspective, is defined such that a stable matching M dominates another stable matching M' (M ≥_m M') if, for every man, his partner in M is at least as preferable as his partner in M' according to his preference list, with strict preference for at least one man. Symmetrically, the order ≥_w for women is the dual, where M ≥_w M' if every woman is at least as well off in M as in M'. Under these orders, the lattice structure ensures that for any two stable matchings M_1 and M_2, there exist unique supremum (join, M_1 ∨ M_2) and infimum (meet, M_1 ∧ M_2) elements, computed by taking, for each man (or woman), the better partner across the two matchings while preserving stability.[19]
In this lattice, the man-optimal stable matching—obtained via the man-proposing Gale-Shapley algorithm—serves as the unique maximum element, where every man receives his best possible stable partner, and consequently, every woman receives her worst possible stable partner. Dually, the woman-optimal stable matching is the unique minimum element, maximizing outcomes for women at the expense of men. This duality implies that the lattice is symmetric when men's and women's roles are swapped, and the height of the lattice (the longest chain between maximum and minimum) is at most n-1 for n participants per side, reflecting the minimal number of steps needed to traverse from one optimum to the other.
Central to the lattice's structure are rotations, which characterize the edges connecting adjacent stable matchings. A rotation is a cycle of even length in the symmetric difference between two stable matchings, consisting of alternating matched and unmatched edges under the men's (or women's) order, such that applying the rotation improves the partners for all men (or women) in the cycle while worsening them for the opposite side, and the resulting matching remains stable. Formally, if M and M' differ by a rotation ρ, then M' = M Δ ρ, where Δ denotes symmetric difference, and ρ forms a simple cycle where each man in the cycle prefers his new partner in M' to his current one in M. Rotations are symmetric differences that are minimal and do not introduce blocking pairs, enabling a poset on the set of all possible rotations (with O(n^2) elements), where one rotation dominates another if it implies the latter in the lattice.[20]
A key structural theorem establishes that the lattice of stable matchings is fully connected via rotations: starting from the man-optimal matching, every other stable matching can be reached by a sequence of rotations, each descending the lattice by improving women's outcomes at men's expense. The set of all stable matchings corresponds one-to-one with the closed subsets (down-sets) of the rotation poset, where a closed subset S of rotations generates the stable matching obtained by applying all rotations in S to the man-optimal matching. This correspondence allows for efficient enumeration of all stable matchings in O(n^2) space and time polynomial in the number of matchings, as the poset has a compact representation via its transitive closure. Moreover, the lattice's distributive property ensures it is ranked and atomic, with rotations providing a Hasse diagram for the covering relations.[19][20]
Applications and Extensions
Real-World Applications
The stable matching problem has been instrumental in market design, particularly through Alvin Roth's contributions to redesigning the National Resident Matching Program (NRMP), which has paired medical residents with hospitals since the 1950s using a deferred acceptance algorithm akin to Gale-Shapley. In the 1980s, Roth analyzed the NRMP's original mechanism and identified its equivalence to the Gale-Shapley deferred acceptance algorithm, leading to refinements that ensured stability and applicant optimality. By 1998, the NRMP adopted a revised version of this algorithm, developed with Elliott Peranson, which has since matched approximately 38,000 physicians annually while accommodating complexities like couples and preliminary matches, demonstrating the algorithm's robustness in large-scale labor markets.[2][21][22]
In education, stable matching principles underpin school choice systems in major U.S. cities, where the Gale-Shapley deferred acceptance algorithm assigns students to schools based on preferences and capacities. New York City implemented this mechanism in 2003 for its high school admissions, serving approximately 72,000 students yearly and improving stability by eliminating incentives for strategic misrepresentation compared to prior systems. Similarly, Boston Public Schools transitioned to the deferred acceptance algorithm in 2005, replacing an immediate acceptance mechanism that had encouraged gaming; this change enhanced fairness and efficiency, with empirical studies showing higher student satisfaction and fewer unmatched applicants. These adoptions highlight how stable matchings resolve conflicts in priority-based assignments, ensuring no blocking pairs exist between students and schools.[23][24][25]
Kidney exchange programs leverage variants of stable matching to facilitate paired donations, addressing incompatibilities between donors and recipients through cycles and chains that maximize compatible transplants. Pioneered by Roth, Sönmez, and Ünver in 2004, these algorithms model exchanges as bipartite matching problems with compatibility constraints, using deferred acceptance to find stable outcomes that avoid unstable pairs and prioritize high-value matches. Implemented in networks like the New England Program for Kidney Sharing and the national Kidney Paired Donation Program, this approach has enabled thousands of transplants; for instance, paired kidney donations reached 1,114 annually by 2021, with cumulative totals exceeding 10,000 since the programs' inception, significantly reducing wait times on the deceased donor list.[26][27]
In economics, stable matching connects to auction theory, particularly in sponsored search advertising where advertisers bid for ad slots based on query relevance. Bhalgat et al. (2008) extended Gale-Shapley to this domain, framing auctions as stable matchings between advertisers and keywords to ensure envy-free allocations and truthful bidding. This framework has influenced mechanisms at platforms like Google, where stable outcomes balance advertiser value and platform revenue.[28]
Variants and Generalizations
One prominent generalization of the stable matching problem accommodates unequal market sizes through many-to-one matchings, where agents on one side (e.g., colleges) can be assigned multiple partners up to a specified capacity, while agents on the other side (e.g., students) receive at most one. This extension, often modeled as the college admissions problem, preserves the core stability notion: no unmatched or tentatively matched agent pair prefers each other over their current assignments. The deferred acceptance algorithm generalizes straightforwardly by allowing the capacity-constrained side to provisionally accept multiple proposals, rejecting only when exceeding limits or preferring alternatives, ensuring a stable outcome in polynomial time.[4][1]
Another key variant incorporates ties in preferences and incomplete lists, termed the stable marriage problem with ties and incomplete lists (SMTI), where agents may rank some partners equally and omit others from their lists entirely, reflecting real-world scenarios with indifferent or unknown options. Stability here requires no blocking pair where both agents weakly prefer each other (or one strictly prefers) over their current matches, with weak and super-strong variants distinguishing tie-breaking rules. Polynomial-time algorithms exist to compute a stable matching, extending deferred acceptance by handling ties through tentative rankings and incompletenesses by allowing unmatched agents; however, optimizing for maximum cardinality or other criteria like sex-equality becomes NP-complete.[29][30]
The classic framework inherently relies on non-transferable utilities, emphasizing ordinal stability based solely on preference rankings without monetary transfers or cardinal payoffs between agents. This ordinal focus ensures stability against deviations by pairs who mutually rank each other higher than their assigned partners, distinguishing it from transferable utility models where side payments could alter outcomes. Such non-transferable assumptions underpin the existence guarantees and algorithmic efficiency in bipartite settings.[4]
Computational generalizations extend the problem to weighted or dynamic environments. In the weighted stable matching problem, edges carry numerical weights representing cardinal utilities, and the objective is to find a stable matching maximizing total weight; this is NP-hard even in bipartite graphs with strict preferences, though approximation algorithms achieve constant factors under certain conditions. Dynamic variants model evolving markets where preferences change over time or agents arrive sequentially, introducing notions like dynamically stable matchings that remain stable against ongoing perturbations without full recomputation, with existence proven via fixed-point arguments in specific models.[31]
Hospital-Resident Matching
The hospital-resident matching problem extends the stable marriage problem to a many-to-one setting, where hospitals may accept multiple residents up to specified capacities, while each resident is assigned to at most one hospital. In this model, a set of residents each submits a strict preference ranking over hospitals, and each hospital submits a strict preference ranking over residents, potentially deeming some unacceptable. The objective is to produce a stable assignment that respects these preferences and hospital capacities.[4]
Stability in this context adapts the pairwise notion from the marriage problem to accommodate capacities: an assignment is unstable if there exists a resident r and hospital h such that r prefers h to their current assignment (or prefers being matched to h if unmatched), h prefers r to at least one of its currently assigned residents (or has available capacity if underfilled), and both find the pairing acceptable. A stable matching eliminates all such blocking pairs, ensuring no mutually beneficial deviation is possible.
The resident-oriented deferred acceptance algorithm, a direct extension of the Gale-Shapley procedure, computes a stable matching in this setting. Residents propose sequentially to hospitals in decreasing order of preference; each hospital maintains a tentative list of up to its capacity highest-ranked proposers and rejects the rest. Rejected residents continue proposing to their next preferred hospital, with hospitals updating their tentative lists by potentially displacing lower-ranked assignees. The algorithm terminates in finite steps with a stable matching that is optimal for residents—no other stable matching makes all residents at least as well off, with at least one strictly better off.[4]
Consider a representative instance with two hospitals, H_1 (capacity 2) and H_2 (capacity 1), and four residents R_1, R_2, R_3, R_4. The preferences are as follows:
Residents' preferences:
- R_1: H_1 > H_2
- R_2: H_1 > H_2
- R_3: H_2 > H_1
- R_4: H_1 > H_2
Hospitals' preferences:
- H_1: R_1 > R_4 > R_2 > R_3
- H_2: R_3 > R_1 > R_2 > R_4
Applying the resident-oriented deferred acceptance algorithm:
- Step 1: R_1, R_2, R_4 propose to H_1; R_3 proposes to H_2. H_1 tentatively accepts R_1 and R_4 (its top two), rejecting R_2. H_2 accepts R_3.
- Step 2: R_2 proposes to H_2. H_2 prefers R_3 over R_2 and is at capacity, so it rejects R_2.
No further proposals occur. The stable matching is \{R_1 - H_1, R_4 - H_1, R_3 - H_2\}, with R_2 unmatched. This assignment is resident-optimal among stable matchings.[4]
Non-Bipartite and Other Extensions
The stable roommates problem generalizes the stable marriage problem to non-bipartite settings, where an even number of agents, say $2n, each rank all others in strict order of preference, and the goal is to pair them into n stable pairs such that no two agents prefer each other over their assigned partners.[32] Unlike the bipartite case, where a stable matching always exists, the roommates problem allows for instances with no stable matching, often due to odd-length preference cycles that create unavoidable instabilities.[32] Robert Irving developed a polynomial-time algorithm in O(n^2) that either constructs a stable matching or determines that none exists, by iteratively reducing preference lists through phases of proposal and rejection similar to the Gale-Shapley algorithm, followed by a cycle-elimination step.[32]
For the standard roommates problem with strict preferences, both finding a stable matching and verifying the stability of a given matching are solvable in polynomial time.[32] However, when agents exhibit indifferences—modeled as ties in preference lists—the problem becomes NP-complete to decide whether a stable matching exists, as ties introduce additional complexity in handling equivalent options and potential blocking pairs. Irving and Manlove extended the framework to this case, providing algorithms for weakly stable matchings (where blocking pairs must strictly prefer each other) and super-stable matchings (requiring no indifference-based blocks), though the general solvability remains hard.
Another key extension is the house allocation problem with existing tenants, where agents have strict preferences over a set of indivisible houses, some of which are occupied by current tenants who may relocate or trade.[33] Stability here requires no agent-tenant pair where the agent prefers the tenant's house and the tenant prefers the agent's assignment (or remaining unmatched if applicable), accounting for the need to vacate houses before reallocation, which can form trading cycles or chains.[33] Abdulkadiroğlu and Sönmez introduced a strategy-proof mechanism, the "You request my house—I get your lottery" rule, that produces Pareto-efficient and stable outcomes by integrating top trading cycles with serial dictatorship, ensuring existing tenants can initiate trades without disadvantage.[33]
Post-2000 research has further extended stable matching to incorporate indifferences more broadly and constraints from underlying networks. In non-bipartite settings with ties, super-stability—where no pair, even with indifferent preferences, blocks the matching—can be found in linear time relative to input size when ties are present, building on Irving's reductions. For network-constrained variants, agents can only match along edges of a social or compatibility graph, leading to local stability where blocking pairs must be adjacent; algorithms adapt Irving's method to prune impossible pairs, though existence is not guaranteed and computation can be harder in sparse networks. These extensions highlight applications in peer-to-peer resource sharing and decentralized systems, where network topology limits feasible matches.