the ground / stratum · Mechanism
Every spring, some forty thousand newly-minted American doctors are sorted among the hospitals that will train them — not by anyone choosing, but by an algorithm. The same machine assigns children to public schools in New York and Boston. It was proved correct in a short paper in 1962, and the proof is a small miracle: there is always a way to pair everyone so that no two people would rather have each other than what they got. This page builds that machine and runs it in front of you.
Here is the problem, stripped to its bones. Two groups must be paired off one-to-one — say applicants to positions. Everyone has ranked everyone on the other side, in strict order of preference. You are the matchmaker. Pair them up.
You might think the goal is to make people as happy as possible on average. It isn't — that turns out to be both ill-defined and gameable. The goal is humbler and far more useful: produce a matching that is stable, meaning self-enforcing. A matching is unstable if there is a blocking pair — an applicant and a position who are not matched to each other but who each prefer the other to their assigned partner. Left alone, that pair will defect: they'd both be better off abandoning the match and pairing up privately. A matching with no blocking pair has no such escape hatch. Nobody can find a partner who would have them and whom they'd prefer. No two would rather.
That such a matching exists at all, for every possible set of preferences, is not obvious — and it is the theorem David Gale and Lloyd Shapley proved in 1962, in a paper with the modest title College Admissions and the Stability of Marriage. Their proof is an algorithm so simple you can run it by hand. It is called deferred acceptance, and the trick is in the word deferred: no acceptance is ever final until the very end.
One side proposes. Each applicant, still unmatched, proposes to the best position on their list that hasn't yet rejected them. Each position, receiving offers, does not accept — it merely holds the best offer so far and rejects the rest, keeping its options open. A held applicant can be bumped later by a better one. Round after round, rejected applicants drop down their lists and propose again, until no one is left to propose. Then, and only then, every held offer becomes a marriage. Run it.
The proposing side reaches across to the position it most wants that still might have it; a held line is solid, the live proposal flashes, a rejection snaps back. Watch no acceptance become final until the end.
However you reroll the preferences, two things never change. The run always ends — each applicant can be rejected by each position at most once, so there are only finitely many rejections to go around. And when it ends, the search for a blocking pair always comes back empty. That is the whole of Gale–Shapley: a constructive proof, run in front of you, that a stable matching exists for every preference profile in the world.
A stable matching always exists. But there is usually more than one — and which one you land on depends entirely on who got to propose.
Switch the proposing side in the instrument and watch the matching change, and with it the two average-rank numbers. The side that proposes does conspicuously better. This is not a quirk of the example. Gale and Shapley proved it in the same paper: applicant-proposing deferred acceptance is applicant-optimal — it gives every single applicant the best partner they could have in any stable matching, all at once. And it is simultaneously position-pessimal: it gives every position its worst stable partner. Flip who proposes and the roles flip exactly.
So the stable matchings aren't a formless pile. They have a hidden skeleton. Between the applicant-optimal one (best for every applicant, worst for every position) and the position-optimal one (the mirror) lie all the compromises — and they are ordered. If you rank one stable matching above another whenever every applicant weakly prefers it, you get a lattice: a structure where any two stable matchings have a well-defined "best of both" above them and "worst of both" below. John Conway noticed this; Donald Knuth wrote it down. Climb it.
Every stable matching for the current preferences, brute-force enumerated and stacked from the applicant-optimal at the top to the position-optimal at the bottom. Click any row to inspect it. The averages show the conflict of interest as a number.
Now the question that turned this from a theorem into a Nobel Prize. People don't have to tell the truth. An applicant submits a stated ranking, and could lie — list a long-shot first, hide a safety, anything — if lying gets a better match. A mechanism everyone games is worthless. So: can you beat deferred acceptance by lying?
The answer is the most beautiful asymmetry in the field. For the side that proposes, the answer is no, never: telling the truth is a dominant strategy. No applicant, against any opponents, can ever do better by submitting anything other than their true preferences (Dubins–Freedman and Roth, 1981–82). The instrument will try all of an applicant's possible lies and find that none beats honesty.
For the side that receives, the answer is yes, sometimes — and this is unavoidable. Alvin Roth proved in 1982 that no stable matching mechanism can be strategy-proof for everyone at once. Whichever side you protect by letting them propose, the other side is left with cases where a well-placed lie pays. Below is the smallest such case: three applicants, three positions, and one position that can lie its way from its worst match to its best.
① The proposing side can't gain by lying — exhaustively. Pick an applicant from the current instance; the machine runs every one of their possible misreports through applicant-proposing deferred acceptance and reports the best partner any lie can buy.
each bar is one misreport, height = the true rank it yields · gold = the honest match · taller-than-gold would mean a profitable lie (there are none)
② The receiving side sometimes can. A fixed 3×3 where applicants propose. Riverside's honest favourite is Cy, but truthful deferred acceptance hands it Bo, its last choice. Watch what one lie does.
Read that last move carefully, because it is exactly the incentive the real world has to manage. By declaring its true last choice unacceptable, Riverside makes deferred acceptance route around the matching that stuck it with Bo — and lands in a different stable matching where it gets Cy, its true favourite. The lie is safe (it still ends up matched) and strictly better. No stable mechanism can close this door for both sides at once; you can only choose which side to hand the safe, honest strategy to. That choice has stakes measured in careers.
The headline example is not a metaphor. The clearinghouse that sorts U.S. medical graduates into residencies has run since 1952 — first as the National Intern Matching Program, today the National Resident Matching Program — and the algorithm it used was, unknowingly, essentially deferred acceptance, a fact Alvin Roth uncovered in 1984 by reading its rulebook as game theory. Crucially, that algorithm was program-optimal (a modified variant equivalent to letting the hospitals propose), handing the safe, honest strategy to the hospitals and leaving students exposed. After Roth's analysis the Match was redesigned (Roth & Peranson, 1999) and switched — adopted in 1997, first run in the 1998 match — to applicant-proposing, so that the tens of thousands of students each year — the side with the least power and the most to lose — can now safely tell the truth. The same theory rebuilt school choice in New York City (2003) and Boston (2005), replacing systems that punished families for ranking honestly. In 2012 the Nobel Memorial Prize in Economics went to Lloyd Shapley and Alvin Roth, "for the theory of stable allocations and the practice of market design." (Gale, who would surely have shared it, had died in 2008; the prize is not awarded posthumously.)
Couples break everything. The clean theorem assumes each agent wants one partner. Real residents include married couples who want two positions in the same city — a single agent with a joint preference over pairs. The moment you allow that, Roth showed (1984) a stable matching may not exist at all, and Ronn proved (1990) that merely deciding whether one exists is NP-complete. The real NRMP runs a sophisticated heuristic (Roth–Peranson) that finds a stable matching when it can and a near-stable one when it can't — there is no longer a guarantee, only a very good search. The tidy proof above is the frictionless-plane version of a genuinely hard real problem.
And you must pick a victim. Roth's impossibility is not a gap to be patched. Every stable mechanism leaves one side able, in some instances, to gain by lying. Applicant-proposing protects applicants perfectly and leaves positions exposed; there is no third option that protects both. The design question is never "how do we stop all manipulation" — it's "who can least afford to be the one who must strategize," and we hand them the honest side.
Every claim here is recomputed in your browser by the same code, and was verified offline first in research/stable-matching/verify.mjs before a word of it was asserted. That program runs 61,594 checks across thousands of random preference profiles and passes all of them: deferred acceptance always returns a matching with zero blocking pairs; that matching is provably the proposer-optimal one (matched, for every proposer, against the full brute-force enumeration of all stable matchings); the join of any two stable matchings is itself stable (the lattice); no single proposer's misreport — over every permutation of their list — ever improves their true-preference partner; the unmatched set is identical in every stable matching (the Rural Hospitals theorem, McVitie–Wilson 1970 / Roth 1986); and the 3×3 manipulation above is a genuine, minimal example, found by exhaustive search. The instruments are that same machine with a face.
Sources & provenance.
D. Gale & L. S. Shapley, "College Admissions and the Stability of Marriage," American Mathematical Monthly 69 (1962), 9–15 — the existence theorem, the deferred-acceptance algorithm, and proposer-optimality. · D. E. Knuth, Mariages stables (1976) — the lattice structure of stable matchings, credited there to John H. Conway. · L. E. Dubins & D. A. Freedman, "Machiavelli and the Gale–Shapley algorithm," Amer. Math. Monthly 88 (1981); A. E. Roth, "The economics of matching: stability and incentives," Math. of Operations Research 7 (1982) — truth-telling is dominant for the proposing side, and no stable mechanism is strategy-proof for both sides. · A. E. Roth, "The evolution of the labor market for medical interns and residents," J. Political Economy 92 (1984) — the NRMP is a stable mechanism; with couples a stable matching may not exist. · E. Ronn, "NP-complete stable matching problems," Journal of Algorithms 11 (1990), 285–304 — with couples, deciding whether a stable matching exists is NP-complete. · A. E. Roth & E. Peranson, "The redesign of the matching market for American physicians," American Economic Review 89 (1999); NRMP adopted applicant-proposing in 1998. · A. Abdulkadiroğlu, P. Pathak & A. Roth on the NYC (2005) and Boston (2005) school-choice redesigns. · The 2012 Sveriges Riksbank Prize in Economic Sciences in Memory of Alfred Nobel to Lloyd S. Shapley and Alvin E. Roth. · Worked checks and the verifier: /research/stable-matching/.