College Admissions and the Stability of Marriage
A matching no pair would walk out of — and a simple algorithm that always finds one.
Pair up a room of people two by two so that no secret couple would both rather ditch their partners for each other — Gale and Shapley proved you always can.
The big idea
Imagine pairing people off — job-seekers with employers, students with schools, partners with partners. A pairing is stable if there is no pair of people who aren't together but would both rather be: no temptation strong enough to blow it up. In 1962 two mathematicians, David Gale and Lloyd Shapley, proved that such a stable arrangement always exists, however tangled everyone's preferences are — and they gave a simple recipe to find it.
How it came about
Gale and Shapley wrote their seven-page paper for a teaching journal, framing it as the 'stable marriage problem': n men and n women, each with a ranked wish-list. Their recipe is a courtship in rounds. Everyone proposes to their favourite; each person on the receiving end holds on to the best offer so far and turns the rest down; the rejected try again, one rank lower, the next round. Nobody is ever permanently stuck — the receiving side keeps trading up — and the music stops at a stable match.
What they didn't know is that a U.S. clearinghouse for placing new doctors had stumbled onto essentially the same procedure a decade earlier, without ever proving it worked. Gale and Shapley supplied the proof the practice had been missing.
Why it mattered
The result says a fair, sustainable arrangement isn't merely a hope but a guarantee — reachable by a fast and honest procedure. Decades later the economist Alvin Roth used it to redesign how American doctors are matched to hospital residencies, how children are assigned to public schools in some big cities, and how living kidney donors are paired with patients. Shapley and Roth shared the 2012 Nobel Memorial Prize in Economics for it; Gale had died in 2008 and could not be named.
An everyday picture
Think of musical chairs played politely. Each round you walk toward your favourite chair; whoever is sitting there compares you with themselves, keeps the better fit, and nudges the other to keep looking. Because a chair only ever swaps its sitter for someone it likes more, the game can't loop forever — and when it ends, no two people would both rather trade seats. There's a catch the widget makes visible: whoever does the walking gets the better deal. The proposers end up with their best possible stable partner; the proposed-to, with their worst.
Where it sits
This paper sits in the Library's game-theory line, beside von Neumann and Morgenstern (1944), John Nash (1950), and Kenneth Arrow (1951). Arrow had just proved a famous impossibility — that no voting rule can fairly distil everyone's preferences into a single social ranking. Gale and Shapley answer with a possibility: a different, humbler goal — a stable match — can always be achieved, and built by hand. Read side by side, they trace the boundary between the collective arrangements we can guarantee and the ones we cannot.
There always exists a stable set of marriages.
any argument which is carried out with sufficient precision is mathematical, and the reason that your friends and ours cannot understand mathematics is not because they have no head for figures, but because they are unable to achieve the degree of concentration required to follow a moderately involved sequence of inferences.