For decades the market that places new doctors in hospitals kept collapsing into chaos: exploding offers, jumped deadlines, doctors trapped by early contracts. The fix was not more rules but a better algorithm, the same deferred acceptance you have already seen.
Matching markets in the wild
Deferred acceptance is not a toy. The National Resident Matching Program and school-choice systems use it or close variants. Kidney exchange instead uses cycles and chains. This case shows the theory doing real work: matching rules can supply properties that decentralized markets do not.
A matching is stable if there is no pair who both prefer...
Student-proposing deferred acceptance is strategy-proof for the...
Predict, then play
Three doctors, three hospitals with one post each. Run doctor-proposing deferred acceptance, then swap to hospital-proposing.
Now switch from rankings to compatibility. Find what can be exchanged when donors cannot give to their paired patients.
Why did that happen?
Take a guess, then reveal the reason
Left alone, a matching market unravels: if any doctor-hospital pair prefer each other to their assigned partners, they cut a private deal, so hospitals rush to lock in doctors ever earlier with exploding offers. A stable matching removes every such incentive, because no blocking pair exists by construction. Deferred acceptance computes one for everyone simultaneously, replacing a scramble with a single clean assignment. That is why real clearinghouses adopted it.
The real episodes
The National Resident Matching Program uses a deferred-acceptance-based algorithm. Its redesign also had to accommodate couples, whose joint preferences fall outside the simple one-doctor, one-hospital model and weaken some textbook guarantees. Boston switched its school assignment to student-proposing deferred acceptance in 2005, so truthful ranking is safe for students under the model’s assumptions. Kidney exchange uses directed compatibility graphs, cycles, and chains. That shares the cycle-finding idea with top trading cycles, but it is not the same mechanism.
Two design lessons recur. First, stability reduces incentives for participants to arrange matches outside the clearinghouse. Second, strategy-proofness matters: the old Boston mechanism could punish honest ranking, so sophisticated families had reason to game it. In student-proposing deferred acceptance, truthful reporting is a dominant strategy for students, not for schools. Kidney exchange adds the twist that a non-directed donor can start a long chain, relaxing the mutual-compatibility bottleneck of a simple two-way swap.
Work it out
Stability is what markets could not self-provide
Run the match: doctors propose, hospitals hold their favourite so far and reject the rest, rejected doctors try their next choice, and the process settles at a stable assignment with no blocking pair. Every doctor is as well off as any stable matching allows, and no hospital-doctor pair would both rather defect.
Now imagine no clearinghouse. A hospital that fears losing a top doctor makes an exploding offer months early; doctors accept out of fear; the market moves earlier each year until it breaks. This is exactly the instability that a stable matching rules out. In medical matching and school choice, deferred acceptance supplies stability and safe truthful ranking for the proposing side. Kidney exchange uses a different cycle-and-chain design to find compatible transplants.
Key idea
Real matching markets can unravel without a clearinghouse. Deferred acceptance supplies stable assignments and safe truthful ranking for the proposing side in the basic model. Kidney exchange is a different graph problem that uses compatibility cycles and chains.
Check yourself
Sources
- Gale, D., and Shapley, L. S. (1962). College admissions and the stability of marriage. American Mathematical Monthly, 69(1), 9-15.
- Roth, A. E. (2015). Who Gets What and Why. Houghton Mifflin Harcourt.