Gale-Shapley Stable Matching
Two equal-size groups, each member ranks the other group in order of preference. Find a matching such that no pair would rather defect to be together. Gale and Shapley (1962) showed such a stable matching always exists, and gave a simple "propose-and-reject" algorithm that finds one. Roth's Nobel 2012 was for adapting this to kidney exchange and school choice.
click "next step" to begin
why this works and why it matters
The algorithm. Every "proposer" approaches their top remaining choice. Each "acceptor" tentatively accepts their best offer so far and rejects the rest. Rejected proposers move to their next choice. Repeat until no one is rejected. The result is a stable matching: no pair would prefer each other over their current partners.
Why stable. Suppose pair (M, w) would both prefer each other over their current partners. Then M would have proposed to w before settling for someone less preferred. Either w accepted (contradiction, they're not matched), or w rejected M because she had a better offer — but her current partner can only be at least as good as that better offer. Contradiction.
Asymmetry. The algorithm produces the best stable matching for proposers and the worst stable matching for acceptors. Whichever side proposes wins. In real medical residency matching (the NRMP), this asymmetry was the motivating concern.
Applications. The 1962 paper is one of the most-cited in economics. Adaptations: New York City school choice (Roth-Sönmez-Ünver), kidney exchange (Roth Nobel 2012), medical residency matching since 1952 (NRMP), the FCC spectrum auction, partner-dance assignment.