Source: gale_shapley_algorithm.md
The stable matching problem was first formulated by David Gale and Lloyd Shapley in their 1962 paper "College Admissions and the Stability of Marriage" (American Mathematical Monthly, Vol. 69, pp. 9-15). The problem asks: given two equally sized sets of agents (e.g., students and colleges, men and women, doctors and hospitals), each with strict preference orderings over agents on the other side, find a matching such that no unmatched pair would prefer each other to their current partners.
Definition (Blocking Pair). Given a matching M, a pair (s, c) where s is a student and c is a college forms a blocking pair if:
Definition (Stable Matching). A matching M is stable if it contains no blocking pairs.
Theorem (Gale-Shapley, 1962). For every instance of the stable matching problem with strict preferences, a stable matching always exists and can be found by the Deferred Acceptance algorithm.
This is the canonical version where students (the "proposing" side) make offers to colleges (the "receiving" side).
ALGORITHM: Student-Proposing Deferred Acceptance
INPUT: Set of students S = {s_1, ..., s_n}
Set of colleges C = {c_1, ..., c_m}
Preference list P(s_i) for each student over colleges
Preference list P(c_j) for each college over students
Capacity q_j for each college c_j
Initialize: All students are FREE. All colleges have empty tentative lists.
WHILE there exists a free student s who has not yet proposed to all colleges:
c <- first college on s's preference list to whom s has not yet proposed
s proposes to c
IF c has fewer than q_j tentative holds:
c tentatively holds s // "maybe"
ELSE IF c prefers s to its least-preferred tentative hold s':
c replaces s' with s // "maybe" to s, "no" to s'
s' becomes FREE
ELSE:
c rejects s // "no"
OUTPUT: All tentative holds become final assignments.
Key mechanism: Acceptances are deferred -- colleges hold proposals tentatively and can replace them with better offers in later rounds. This deferral is what guarantees stability.
The roles are reversed: colleges make offers to students.
ALGORITHM: College-Proposing Deferred Acceptance
INPUT: Same as above.
Initialize: All colleges have q_j unfilled positions. All students are FREE.
WHILE there exists a college c with unfilled positions that has not
proposed to all acceptable students:
s <- highest-ranked student on c's list to whom c has not yet proposed
c proposes to s
IF s is FREE:
s tentatively holds c's offer // "maybe"
ELSE IF s prefers c to current tentative hold c':
s switches from c' to c // "maybe" to c, "no" to c'
c' regains one unfilled position
ELSE:
s rejects c's offer // "no"
OUTPUT: All tentative holds become final assignments.
Termination: The algorithm must terminate because:
Each student proposes to each college at most once.
With n students and m colleges, there are at most n * m possible proposals.
Each round either results in a new proposal or the algorithm terminates.
Therefore, the algorithm terminates in at most n * m rounds.
Stability: The output is always stable. Proof by contradiction: Suppose (s, c) is a blocking pair in the output matching M. Then s prefers c to their assigned college. This means s proposed to c before their assigned college. Since s is not matched to c, c must have rejected s (either immediately or by replacing s with a more preferred student). But colleges only replace students with more preferred ones, so c's final match is at least as preferred as s. This contradicts the assumption that c prefers s to a current match.
Theorem (Gale-Shapley, 1962). The student-proposing DA produces a matching that is student-optimal among all stable matchings. That is, every student is matched to their most-preferred college achievable in ANY stable matching.
Definition (Valid partner). A college c is a valid partner for student s if there exists some stable matching in which s is matched to c.
Theorem (restated). In the student-proposing DA, each student is matched to their most-preferred valid partner.
Proof sketch: By induction on the rounds of the algorithm. Suppose at some round, a student s is rejected by a valid partner c for the first time. Then c rejected s in favor of some student s' whom c prefers. But since this is the first rejection of a valid partner, s' has not yet been rejected by any valid partner, and so s' has only proposed to colleges they prefer to c (or c itself). There exists a stable matching M where s is matched to c. In M, s' must be matched to some college c' that s' likes no better than c (since s' proposed to c before c'). Then (s', c) would be a blocking pair in M, contradicting its stability.
Theorem. The student-proposing DA produces the college-pessimal stable matching. Every college is matched to its least-preferred set of valid partners.
This creates a fundamental asymmetry:
Proposing side gets their best stable outcome.
Receiving side gets their worst stable outcome.
The college-proposing DA reverses these roles: it produces the college-optimal, student-pessimal stable matching.
Theorem (Knuth, 1976; Conway, unpublished). The set of all stable matchings forms a distributive lattice under the partial order defined by student preferences.
Given two stable matchings M and M', define:
M v M' (join): match each student with whichever college they prefer between M and M'.
M ^ M' (meet): match each student with whichever college they like less between M and M'.
Both M v M' and M ^ M' are themselves stable matchings. The student-optimal matching is the supremum (top) of this lattice, and the college-optimal matching is the infimum (bottom).
Implication: There can be exponentially many stable matchings (up to 2^{n/2} for n students), but the lattice structure means the proposer-optimal and receiver-optimal matchings bound them all.
Theorem. For any two stable matchings M and M', if every student weakly prefers M to M', then every college weakly prefers M' to M. The interests of the two sides are diametrically opposed within the lattice of stable matchings.
The Hospitals/Residents (HR) problem is a direct generalization of the stable marriage problem where hospitals (colleges) can accept multiple residents (students). Each hospital h has a capacity q_h.
Formulation: Given n residents and m hospitals with capacities, find an assignment where:
Each resident is assigned to at most one hospital.
Each hospital is assigned at most q_h residents.
No blocking pair exists.
The student-proposing DA generalizes directly: hospitals hold up to q_h tentative offers at a time, rejecting only when full and receiving a better applicant. All results (existence, optimality, lattice structure) carry over.
Equivalence Theorem (Roth, 1984). The set of stable matchings in the HR problem has the same structure as if each hospital position were treated as a separate agent with identical preferences. This means many-to-one matching reduces theoretically to one-to-one matching.
In practice, agents may:
Be indifferent between some partners (ties in preferences).
Find some partners unacceptable (incomplete preference lists).
Three stability concepts arise when ties are allowed:
| Stability | Definition |
|---|---|
| Weak stability | No blocking pair where both agents strictly prefer each other to current match |
| Strong stability | No blocking pair where one agent strictly prefers and the other weakly prefers |
| Super stability | No blocking pair where both agents weakly prefer each other |
Complexity results:
Weakly stable matchings always exist and can be found in O(n^2) time by breaking ties arbitrarily and running standard DA.
Finding a maximum-cardinality weakly stable matching is NP-hard (Manlove et al., 2002), even with very restricted tie structures.
Strongly stable matchings may not exist; checking existence is solvable in polynomial time.
Super-stable matchings may not exist; checking existence is solvable in polynomial time.
Practical importance: SMTI arises in Scottish hospital matching (HRT -- Hospitals/Residents with Ties) and adoption matching (pairing children with families), where strict orderings over all candidates are unrealistic.
Some extensions require each college to fill a minimum number of seats, not just a maximum. This introduces feasibility constraints that can conflict with stability: a stable matching satisfying all lower quotas may not exist.
A unifying generalization where agents negotiate over contracts (specifying salary, position type, etc.) rather than simple matches. The DA algorithm generalizes under certain "substitutability" conditions on colleges' choice functions. Many classical results (existence, optimality, strategy-proofness) extend to this framework.
When residents apply as couples (both must be placed in the same city), stable matchings may not exist, and finding one is NP-complete. Roth and Peranson developed heuristic algorithms for the NRMP that handle couples in practice, though without theoretical guarantees.
The Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel 2012 was awarded jointly to Alvin E. Roth and Lloyd S. Shapley "for the theory of stable allocations and the practice of market design."
Shapley (with Gale) provided the foundational theory in 1962. Roth, starting in the 1980s, transformed this theory into practical market design, creating some of the most successful applications of economic theory in the real world.
Roth made the remarkable discovery that the National Resident Matching Program (NRMP), which had been matching medical residents to hospitals since 1952, was already using an algorithm equivalent to the hospital-proposing DA -- even though the NRMP designers were unaware of Gale and Shapley's work. This provided powerful empirical evidence for the theory: the NRMP had independently converged on a stable matching mechanism because unstable alternatives had failed in practice.
Roth showed that earlier clearinghouse mechanisms in the UK (for medical graduates) that did NOT produce stable matchings had collapsed, while those that did produce stable matchings had survived. This established stability as a key practical requirement.
By the 1990s, the NRMP faced new challenges:
The original algorithm was hospital-proposing (hospital-optimal, resident-pessimal).
Married couples applying together could not be handled.
Students felt the system favored hospitals.
Roth, working with Elliott Peranson, redesigned the NRMP to use:
Resident-proposing DA (switching from hospital-optimal to resident-optimal).
Heuristic extensions for couples applying together.
The new algorithm was adopted in 1998 and has been used since.
Theorem (Roth, 1982). The student-proposing DA is strategy-proof for students: no student can obtain a better outcome by misrepresenting their preferences, regardless of what other students or colleges do. Truth-telling is a dominant strategy for the proposing side.
Impossibility Theorem (Roth, 1982). No stable matching mechanism can be strategy-proof for both sides simultaneously (when there are at least 3 agents on each side). Colleges always have potential incentives to misrepresent preferences or capacities under any stable mechanism.
This result has profound implications: it justifies using the student-proposing DA in school choice (where protecting students from strategic manipulation is paramount), even though colleges may have incentives to game the system.
Theorem (Roth, 1984; building on McVitie-Wilson, 1970). In every stable matching:
Implication: The choice between student-optimal and hospital-optimal DA does NOT affect which hospitals have empty seats or which students go unmatched. Rural hospitals that struggle to attract residents cannot be helped by changing the matching algorithm -- the problem lies in preferences, not mechanism design.
Roth (with Abdulkadiroglu and Sonmez, 2003) showed that the "Boston mechanism" used in many school districts was:
Not strategy-proof (parents had to game the system).
Produced unstable and inefficient outcomes.
Disproportionately harmed unsophisticated families.
They proposed replacing it with student-proposing DA. Implementations:
New York City (2004): Replaced a decentralized system where students applied to schools directly. The new system matched ~90,000 students per year and reduced unassigned students from ~30,000 to ~3,000.
Boston (2005): Switched from the Boston mechanism to DA.
Roth, with Sonmez and Unver (2004-2007), applied matching theory to kidney exchange:
Problem: Patient-donor pairs where the donor is incompatible with the intended patient.
Solution: Find cycles of swaps where each donor gives to a compatible patient in another pair.
Used the Top Trading Cycles algorithm (adapted from Shapley-Scarf, 1974) for kidney exchange chains.
Led to the creation of the New England Program for Kidney Exchange (2004) and influenced the national kidney exchange system.
Theorem. The Gale-Shapley DA algorithm runs in O(n^2) time for n agents on each side.
Proof:
There are n students and n colleges (or m colleges with total capacity n).
Each student proposes to each college at most once.
Therefore, the total number of proposals is at most n * n = n^2 (or n * m in the asymmetric case).
Each proposal requires O(1) time (using appropriate data structures: linked lists for preference lists, arrays for tentative assignments, and ranking arrays for O(1) preference comparisons).
Total: O(n^2).
Lower bound: Any algorithm that finds a stable matching must read Omega(n^2) preference data in the worst case (Ng and Hirschberg, 1990), so Gale-Shapley is asymptotically optimal.
O(n^2) to store the preference lists.
O(n) for the current matching state.
O(n^2) total.
In the worst case, there can be exponentially many stable matchings: up to 2^{n/2} for n agents on each side.
In expectation (random preferences), the number of stable matchings is approximately e * n * ln(n) (Pittel, 1989).
The average rank of partners under random preferences is O(ln n) for the proposing side and O(n / ln n) for the receiving side, further quantifying the asymmetry.
Best case: n proposals (each student's first choice accepts).
Worst case: n^2 proposals (saturates the bound).
Average case (random preferences): n * H_n = O(n ln n), where H_n is the n-th harmonic number (Knuth, 1976; Pittel, 1989). This means that with random preferences, the algorithm terminates much faster than the worst case.
The current simulation uses a score-based admission model with rounds (ED, EA, RD, etc.) rather than a pure Gale-Shapley matching. This is realistic because real college admissions are NOT a pure stable matching market:
Despite the differences, Gale-Shapley theory provides several insights:
Stability as a benchmark: The simulation can check whether its output matching is "approximately stable" -- whether there are many pairs where a student and college would both prefer each other to their current match. High instability suggests the mechanism is performing poorly.
Yield modeling: Student-proposing DA predicts students get better outcomes. In reality, the college-proposing nature of admissions (colleges choose whom to admit, students choose among admits) creates an intermediate outcome. The simulation's yield decision phase mirrors students' "accepting" or "rejecting" offers.
The role of ED/EA: Early Decision acts as a partial commitment device. In Gale-Shapley terms, it is as if a student irrevocably proposes to one college first, which has been shown to benefit students at the cost of reducing the set of stable matchings.
Hook multipliers and affirmative action: These correspond to "modified preferences" -- colleges effectively rank students differently than pure academic merit would suggest. Gale-Shapley theory shows that modified preferences change the stable matching set but the algorithm still produces a stable outcome relative to the modified preferences.
Capacity constraints: The many-to-one HR problem directly models colleges with limited seats. The simulation's enrollment targets correspond to hospital capacities in the HR formulation.
A possible enhancement for the simulation would be a hybrid approach:
Use the current scoring model to generate preference lists (colleges rank students by score, students rank colleges by desirability/fit).
Run DA on these preference lists to find the student-optimal stable matching.
Compare with the round-based simulation output to measure "instability" or "inefficiency."
This comparison could quantify how much the sequential round structure (ED/EA/RD) departs from the theoretical optimum.
Gale, D. and Shapley, L.S. (1962). "College Admissions and the Stability of Marriage." American Mathematical Monthly 69(1): 9-15.
Roth, A.E. (1982). "The Economics of Matching: Stability and Incentives." Mathematics of Operations Research 7(4): 617-628.
Roth, A.E. (1984). "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory." Journal of Political Economy 92(6): 991-1016.
Roth, A.E. and Peranson, E. (1999). "The Redesign of the Matching Market for American Physicians." American Economic Review 89(4): 748-780.
Roth, A.E., Sonmez, T., and Unver, U. (2004). "Kidney Exchange." Quarterly Journal of Economics 119(2): 457-488.
Knuth, D.E. (1976). Marriages Stables. Les Presses de l'Universite de Montreal.
Abdulkadiroglu, A., Pathak, P.A., and Roth, A.E. (2005). "The New York City High School Match." American Economic Review 95(2): 364-367.
Hatfield, J.W. and Milgrom, P. (2005). "Matching with Contracts." American Economic Review 95(4): 913-935.
Manlove, D.F., Irving, R.W., Iwama, K., Miyazaki, S., and Morita, Y. (2002). "Hard Variants of Stable Marriage." Theoretical Computer Science 276(1-2): 261-279.
Pittel, B. (1989). "The Average Number of Stable Matchings." SIAM Journal on Discrete Mathematics 2(4): 530-549.
Roth, A.E. and Sotomayor, M. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press.