Stable Matching

A matching market pairs agents from two sides — applicants and colleges, doctors and residency programs, students and schools, kidney donors and patients — where each side ranks members of the other and money does not clear the market. A matching is stable when it is individually rational (no one prefers going unmatched to their assignment) and has no blocking pair: two agents on opposite sides who both prefer each other to their assigned partners. Stability is the basic engineering criterion of market design, because a matching with a blocking pair contains its own undoing — the pair has both motive and opportunity to defect from the arrangement.¹

The 2012 Nobel Memorial Prize in Economic Sciences went to Lloyd Shapley (“theory of stable allocations”) and Alvin Roth (“practice of market design”), and the citation arc is the story: a 1962 existence proof became, over five decades, the operating system of several real allocation systems.²

The 1962 paper

David Gale and Lloyd Shapley’s “College Admissions and the Stability of Marriage” (American Mathematical Monthly, 69(1):9–15) set up the college-admissions problem: each college has a quota, each applicant a preference ranking, and the naive procedure (offer admission to the q best applicants) fails because colleges cannot tell which offers will be accepted.³

Their procedure is deferred acceptance rendered as a waiting-list algorithm: applicants apply to their first choice; each college holds its top q applicants and rejects the rest; rejected applicants apply to their next choice; colleges re-rank the combined pool and again hold the top q. The process terminates when no applicant can be rejected further. Two results made the paper foundational: a stable assignment always exists (the procedure’s terminal waiting lists are one), and the assignment the procedure produces is applicant-optimal — every applicant is at least as well off under it as under any other stable assignment. The marriage problem of the title is the special case of quota one with equal sides, where the same machinery shows everyone gets matched and the matching is stable.⁴

The authors were notably modest about the whole thing — the concluding remarks concede they had “abandoned reality altogether and entered the world of mathematical make-believe.” Roth’s career was the rebuttal.⁵

Properties that make it a design tool

• Proposer-optimality has a shadow side. Whichever side proposes gets its best stable matching; the other side simultaneously gets its worst stable matching. Which side of the market an institution lets make offers is therefore a distributional choice, not a cosmetic one — the NRMP’s switch from hospital-proposing to applicant-proposing was precisely such a choice.
• The rural hospitals theorem. The set of agents left unmatched is the same in every stable matching. A program that fails to fill its slots cannot fix this by switching to a different stable mechanism — the gap is structural, which redirected policy attention toward why some positions are unattractive rather than toward mechanism-shopping.
• Incentives. For the proposing side, reporting preferences truthfully is a dominant strategy (Dubins & Freedman 1981; Roth 1982). No stable mechanism can be strategy-proof for both sides, so market designers choose which side to protect — and in school choice, protecting parents turned out to matter more than protecting schools.

All three results are developed in the Nobel scientific background.⁶

Roth’s empirical turn: stability as a survival criterion

Roth’s contribution was to take stability out of the theorem and into the field. The National Resident Matching Program had been running since 1952 on an algorithm nobody had a theory for; Roth showed in 1984 that it was, unrecognized, a deferred-acceptance procedure — and that the market’s decades of smooth operation because of that accident was the strongest evidence for stability as the survival criterion for matching institutions. Markets whose mechanisms produced unstable matchings tended to fail or unravel: participants contracted early and earlier each year, fled to alternative arrangements, or the institution collapsed outright (the unraveling of the law-clerk and gastroenterology-fellowship markets are the documented cases).⁷

By the 1990s the NRMP’s hospital-proposing algorithm was under stress — applicants were widely advised to game their lists, and new two-career couples fit the model badly. Roth and Elliott Peranson redesigned it in 1995–97 as an applicant-proposing deferred-acceptance mechanism with accommodations for couples, adopted in 1998. The redesign deliberately moved the optimal-stable payoff from programs to applicants.⁸

Where the machinery runs now

• School choice. New York City’s high-school match (2003, Abdulkadiroğlu–Pathak–Roth) and Boston’s (2005) replaced mechanisms that punished honest rankings — under the old Boston system, listing a popular school first could cost a student their fallback, so sophisticated families gamed and unsophisticated ones paid. Deferred acceptance made honesty safe.⁹
• Kidney exchange. Buying organs is illegal nearly everywhere, so the price system is off the table by statute. Roth, Sönmez, and Ünver built paired and chained exchange on matching machinery: incompatible donor–patient pairs swap, and non-directed donors start chains. This is the pure case of matching as the allocation regime for goods where money is repugnant.¹⁰
• Dating, 2026. Singapore’s GovTech pilot FirstDate (launched September 29, 2026, for unmarried public officers 21–35) runs questionnaire responses through the Gale–Shapley algorithm and issues one match per cycle — roughly monthly — with three days for both sides to accept. The pitch is the anti-swipe: one introduction, both sides’ preferences considered, no infinite pool. It follows the student-run Aphrodite Project (NUS/Yale-NUS, 2019), which used a modified Gale–Shapley for campus matching.¹¹

Markets without prices

Matching theory’s domain is the space where the price mechanism is blocked or absent — by law (organs), by public obligation (school seats), or by the nature of the good (a marriage is not improved by auctioning it). The Nobel background frames it directly: some allocations are handled by prices, but in many instances “using the price system would encounter legal and ethical objections,” and many matching goods are indivisible and heterogeneous, making markets thin — so outcomes depend on the institutions that govern transactions.¹² This is the inverse of the dynamic-pricing world of moral-economy-price-tag: there, prices adjust so finely that the shared reference point (and the appeal) disappears; here, prices are abolished and stability supplies the legitimacy that the reference price supplied there. Both pages are about what holds an allocation regime morally together.

Open questions

• Does stability predict good matches, or merely matches that won’t be defected from? The NRMP’s stability measures the absence of blocking pairs against stated rankings — it says nothing about whether the rankings captured fit. FirstDate’s own website concedes the point: “compatibility on paper does not guarantee chemistry.”
• Preference elicitation quality is the binding constraint in most deployments — a stable matching over noisy rankings is stably wrong. The questionnaire is the mechanism.

Cross-domain connections

• moral-economy-price-tag — the non-price allocation regime; what legitimizes allocation when there is no reference price (see “Markets without prices” above)
• schelling-commitment-and-focal-points — strategy-proofness is commitment engineering: a mechanism that makes honesty dominant burns the bridge to profitable manipulation, the institutional version of Schelling’s removed options
• ostrom-design-principles — matching institutions are designed commons-governance for allocation: clear rules, monitoring built into the mechanism, cheap conflict resolution via re-runs
• prisoners-dilemma — blocking pairs are the cooperative-game shadow of defection; a stable matching is an allocation where no defection pair can profit, the core’s answer to the PD’s instability
• assortative-mating — the empirical pattern matching markets produce: the marriage-economics literature (Becker through Choo–Siow to Goldman–Gracie–Porter) uses the same two-sided framework to measure who actually matches with whom, and why

Sources

• David Gale and Lloyd S. Shapley 1962 — College Admissions and the Stability of Marriage
• Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design
• Darcel Al Anthony 2026 — CNA Explains: What is the Gale-Shapley algorithm and how is it powering GovTech’s new dating platform?

Footnotes

1. Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design ↩

2. Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design ↩

3. David Gale and Lloyd S. Shapley 1962 — College Admissions and the Stability of Marriage ↩

4. David Gale and Lloyd S. Shapley 1962 — College Admissions and the Stability of Marriage ↩

5. David Gale and Lloyd S. Shapley 1962 — College Admissions and the Stability of Marriage ↩

6. Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design ↩

7. Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design ↩

8. Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design ↩

9. Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design ↩

10. Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design ↩

11. Darcel Al Anthony 2026 — CNA Explains: What is the Gale-Shapley algorithm and how is it powering GovTech’s new dating platform? ↩

12. Economic Sciences Prize Committee, Royal Swedish Academy of Sciences 2012 — Stable Allocations and the Practice of Market Design ↩