In conventional microeconomics, markets clear through the medium of price: if supply exceeds demand, prices fall; if demand exceeds supply, prices rise. But in the most consequential arenas of human civilization, money is legally, morally, or culturally forbidden. You cannot auction medical residency slots at Johns Hopkins to the highest cash bidder; parents cannot purchase admissions to public high schools; you cannot legally sell a human kidney to wealthy dialysis patients on an open exchange. How do you design efficient, fair allocations in markets without prices? In 1962, mathematicians David Gale and Lloyd Shapley published a legendary paper: “College Admissions and the Stability of Marriage”. Their Deferred Acceptance Algorithm revolutionized market design, earning Alvin Roth and Lloyd Shapley the 2012 Nobel Prize.
The Two-Sided Matching Problem
Consider two disjoint sets of agents: a set of $n$ Men (or Doctors, or Students) $M = {m_1, dots, m_n}$ and a set of $n$ Women (or Hospitals, or Schools) $W = {w_1, dots, w_n}$.
- Each man $m in M$ possesses a strict, complete ordinal preference ranking over all women: $P(m) = w_2 succ w_1 succ w_3 dots$
- Each woman $w in W$ possesses a strict preference ranking over all men: $P(w) = m_1 succ m_3 succ m_2 dots$
A matching $mu: M cup W to M cup W$ is a bijection such that $mu(m) = w iff mu(w) = m$.
The Concept of Stability & Blocking Pairs
An allocation in a matching market cannot be enforced by decree if participants can run away with someone else. A matching $mu$ is unstable if there exists a rogue couple $(m, w)$ called a blocking pair:
- Man $m$ strictly prefers woman $w$ to his assigned partner $mu(m)$: $w succ_m mu(m)$, AND
- Woman $w$ strictly prefers man $m$ to her assigned partner $mu(w)$: $m succ_w mu(w)$.
If a blocking pair exists, man $m$ and woman $w$ will simply abandon their assigned matches, elope together, and shatter the institutional system. A matching is Stable if and only if no blocking pair exists and every match is individually rational.
The Gale-Shapley Deferred Acceptance Algorithm
Gale and Shapley designed an algorithm that provably terminates in a stable matching in finite steps ($O(n^2)$):
Round 1: Each unmatched man proposes to his highest-ranked woman. Each woman evaluates all proposals she receives, puts her most preferred suitor on tentative hold, and rejects all other suitors.
Round $k$: Each man who was rejected in the previous round proposes to his next highest-ranked choice who has not yet rejected him. Each woman considers her new suitors alongside the suitor she held tentatively from prior rounds: she holds her favorite among them and rejects the rest.
Termination: When no men are rejected, all tentative holds become final marriages.
The Mathematical Marvel of Stability and Optimality
Gale and Shapley proved three fundamental theorems:
- Universal Existence: The algorithm always halts, and the resulting matching is guaranteed to be stable. No blocking pairs can ever exist.
- Proposer-Optimality: Out of all possible stable matchings that could theoretically exist, the Gale-Shapley algorithm selects the M-optimal stable matching. Every single proposer receives the best partner they could ever achieve in any stable matching!
- Receiver-Pessimality: Simultaneously, the receiving side receives the worst partner they could obtain across all stable matchings.
In 1982, Alvin Roth proved the strategic corollary: truth-telling is a dominant strategy for all proposers. No proposer can ever benefit by submitting a fake preference list. However, receivers can strategically manipulate their reported rankings.
From Abstract Marriages to Saving Human Lives
In the 1990s, economist Alvin Roth recognized that the National Resident Matching Program (NRMP), which matches 40,000 medical students to hospitals each year, was collapsing because hospitals were making premature, unraveling offers. Roth redesigned the national clearinghouse using Gale-Shapley, stabilizing medical residency allocation.
In 2004, Roth co-founded the New England Program for Kidney Exchange. Often, a willing kidney donor is biologically incompatible (blood or tissue type) with their loved one. Roth adapted matching algorithms (top trading cycles and paired exchanges) to match incompatible pairs across the nation, creating living donor swap chains that have saved thousands of human lives without a single dollar changing hands.
