Execute deferred acceptance proposals to eliminate every rogue blocking pair and reach stable equilibrium.
- Step proposal rounds to see receivers hold best offers and reject lower ranks
- Scan the full pairing matrix to verify the blocking pair count hits zero
- Invert the proposing side to inspect the opposing extreme of the lattice
After thisYou can design two-sided clearinghouses and matching markets that resist strategic unraveling.
Short on timeThe MatchingBoard interactive clearinghouse in §2
Match Day
3 minthe hook
Each year the National Resident Matching Program places tens of thousands of graduating doctors into hospital posts with one promise: no blocking pair. No applicant and hospital would rather have each other than the partners they were given.
Four applicants and four hospitals sit on the board below, each with a ranked list. Deferred acceptance settles it in four rounds, and three rejections are the whole cost of the promise.
The picture is the waterfall: offers fall from the proposing side, each hospital holds the best offer it has seen, and the rest go back down. A hospital only ever swaps up, so the water only falls.
The waterfall lands on one end of the lattice, not on a unique matching. Switch the proposing side to stand at the other end.
When the left side proposes and the dust settles, which variety of stable matching emerges?
proposers — left
holds — right
every left–right pair, checked for blocking at the final matching
| w | x | y | z | |
|---|---|---|---|---|
| A | matched | i holds | i holds | i holds |
| B | i holds | matched | i holds | i holds |
| C | j holds | j holds | j holds | matched |
| D | i holds | i holds | matched | i holds |
matched · blocks would be a blocking pair · i holds means the left vertex already has someone it ranks higher · j holds is the mirror · — is not mutually acceptable. Blocking pairs in the matching above: 0.
Deferred acceptance returns a matching with no blocking pair — that is what stability means here. Switch the proposing side and the same table is recomputed for the other extreme; it is empty of blocking pairs too.
the two extremes, both stable
| left | partner when left proposes | partner when right proposes | differs? |
|---|---|---|---|
| A | w | x | better for the proposer |
| B | x | w | better for the proposer |
| C | z | z | same |
| D | y | y | same |
The left side proposes: four rounds and three rejections end at A–w, B–x, C–z, D–y. Switch the proposing side and the panel recomputes from scratch to land on the other extreme. The board also opens on Kuhn's augmenting-path search.
Step through the rounds to watch offers fall down the preference lists. Each receiver holds its favourite proposal so far and rejects the rest; a rejected proposer immediately moves to its next choice.
Watch the held column; when a hospital swaps one offer for a better one, the invariant is that the displaced offer drops to its next choice and no accepted offer is ever withdrawn.
NextWhy do greedy matches inevitably produce rogue pairs that prefer each other?
The Pair That Would Rather Swap
2 minthe trap
Consider any proposed matching between two sides. What condition makes it unstable?
A pair is a blocking pair if prefers over their assigned partner and prefers over their assigned partner. If even one such pair exists, both individuals have active incentive to defect and leave together.
A matching is stable if and only if it contains zero blocking pairs. Exhaustively auditing an existing matching is simple ( checks), but constructing an assignment guaranteed to possess no rogue pairs is a non-trivial feat of game theory.
NextHow does deferred acceptance guarantee that no blocking pair can ever form?
The Conway–Knuth Lattice
2 minthe invariant
The mathematical input is not a standard graph, but two families of strict linear orders. The set of all valid stable matchings for a given market forms a geometric structure: a distributive lattice (Conway; Knuth 1976).
Define a partial order on stable matchings by proposer welfare: matching if every proposer ranks their partner in at least as high as in . Under this order, any two stable matchings possess a stable meet (the point-wise receiver compromise) and a stable join (the point-wise proposer compromise).
The two extreme poles of this lattice are generated by swapping who proposes. When left proposes, you land on the lattice summit; when right proposes, you land on the lattice floor.
NextWhy does the proposer-optimal outcome sit at the very top of the rotation lattice?
The Proposer Advantage and Asymmetric Equilibrium
2 minthe algebra
Theorem (Gale & Shapley 1962). The deferred acceptance algorithm always terminates, and the terminal assignment contains zero blocking pairs.
Termination is guaranteed by simple monotonic counting. Proposers never propose to the same receiver twice, descending strictly down their preference lists. The process must halt in at most total proposals (McVitie & Wilson 1971).
Why is the terminal state immune to mutiny? Suppose a proposer and receiver secretly prefer each other over their assigned matches. Because ranks above their final match, must have already proposed to earlier in the run, only to be rejected in favour of someone desired even more.
Once the algorithm terminates, could a proposer 'a' and receiver 'w' still secretly prefer each other to their allocated partners?
Proposer Optimality (Gale & Shapley 1962; Dubins & Freedman 1981). Every proposer receives the best partner they could possibly secure in any stable matching, while every receiver receives their worst possible partner among all stable matchings.
NextHow does the National Resident Matching Program assign tens of thousands of medical residents?
Stepping the Waterfall
2 minthe simulation
Return to the interactive board and toggle the proposing side. Observe how the two runs map the extreme boundaries of the lattice: left-optimal produces A–w, B–x, C–z, D–y, while right-optimal yields A–x, B–w, C–z, D–y.
Examine the blocking pair matrix beneath the completed run. Every cell audits a possible partnership; during intermediate rounds, blocking pairs proliferate in red. Only on the final round does the blocking tally drop to zero.
Toggle the board to augmenting paths to see how the mathematical question transforms. Kuhn (1955) and Berge (1957) locate maximum cardinality matchings without regard to human preferences.
1 minboss round
On the augmenting-path board, every left agent accepts every right agent. How does a maximum bipartite matching differ from a stable matching?
NextWhy can candidates never game the system by submitting insincere ranking lists?
Medical Residencies, Kidney Exchanges, and Market Design
2 minsystems
In 1952, American medical schools and residency hospitals faced rampant unraveling: hospitals made binding offers to medical students years in advance to preempt competitors. The National Resident Matching Program (NRMP) adopted deferred acceptance, revolutionising clinical assignments nationwide (Roth 1984).
The same mechanism powers urban public school assignment systems in Boston and New York, matching hundreds of thousands of students to schools without black-market swaps.
Paired kidney exchange registries adapt these equilibrium mechanics to save lives, clearing cyclical barter chains across incompatible donor-patient pairs.
Strategic Manipulation and the Rural Hospitals Invariant
Deferred acceptance is strategy-proof for the proposing side: no proposer can improve their partner by misrepresenting their true preference rankings (Dubins & Freedman 1981; Roth 1982). Proposers have zero incentive to lie.
Receivers, however, can game the system: a receiver can strategically truncate or permute their rankings to force proposers further down their lists, climbing higher up the lattice.
The Rural Hospitals Theorem (Roth 1986). The exact set of agents matched is invariant across all stable matchings in the lattice! Rural hospitals that go unfilled in the doctor-optimal matching will also go unfilled in the hospital-optimal matching; changing who proposes never creates new matches for underserved institutions.
Attributions
- Gale & Shapley 1962 — College Admissions and the Stability of Marriage: formulated the deferred-acceptance algorithm, proving existence, stability, and proposer-optimality.
- Kuhn 1955 — The Hungarian method and augmenting-path search for maximum bipartite matching.
- Berge 1957 — The augmenting path theorem characterizing maximum matchings.
- McVitie & Wilson 1971 — Sequential proposer-driven implementation bounding execution at steps.
- Knuth 1976 — Marriages Stables: structural discovery of the distributive lattice of stable matchings.
- Dubins & Freedman 1981 — Proof of strategy-proofness for proposing agents.
- Roth 1984 — Analysis of the National Resident Matching Program, establishing market design as an empirical discipline.
- Roth 1986 — The rural hospitals theorem, establishing match-invariance across the stable lattice.