The encyclopedia · R&D & Science · Technical decision · 1962
Gale and Shapley's 1962 algorithm made matching markets honest
A 1962 paper proved stable matchings always exist and gave an algorithm where listing true preferences is the winning strategy.
David Gale · Lloyd Shapley
the move
David Gale and Lloyd Shapley published 'College Admissions and the Stability of Marriage' in the American Mathematical Monthly in 1962. They asked whether stable matchings — assignments in which no two agents would rather be with each other — always exist in two-sided markets like marriage or college admissions.
Their answer was constructive: the deferred-acceptance algorithm, in which one side proposes and the other holds provisional offers, always terminates at a stable matching. The same procedure gives the proposing side its best possible stable outcome, which is why truthful ranking is the dominant strategy for proposers.
Fifty years later the Royal Swedish Academy awarded the 2012 economics prize to Shapley and Alvin Roth 'for the theory of stable allocations and the practice of market design.' Roth had shown that stability explains which real markets survive, and rebuilt the residency match, school choice and kidney exchange on this algorithm.
why it works
- Existence plus an algorithm made stability usable, not abstract.
- Truthful preference lists became the dominant strategy for proposers.
- It gave designers a lens: stable markets survive, unstable ones collapse.
- It powered practical redesigns in medicine, education and organ exchange.
what transfers
Before building a market, check the matching mechanism is stable and strategy-proof: if misreporting pays, the market fills with manipulation. An algorithm that makes honesty optimal is market design.
what came after
The algorithm became the engine of the US residency match redesign, Boston and New York school choice, and kidney-exchange chains — all named in the Nobel citation. Gale-Shapley is now standard vocabulary in market design, operations research and computer science.
references
- The Prize in Economic Sciences 2012 — Press release
- College Admissions and the Stability of Marriage (Internet Archive scan)
- Fixing the 'Match': How to Play the Game
spotted an error? The archive wants to know.