The idea: a matching nobody wants to break
Four students A–D apply to four schools W–Z, and each school has one seat. Every student ranks the schools and every school ranks the students, best first. We want to pair them up so that the result holds: no student and school should both want to leave their partners for each other.
Blocking pairs and stability
A matching pairs each student with one school. A blocking pair is a student s and a school h that are not paired, where s prefers h to its own school and h prefers s to its own student. Both would gain by breaking their matches, so the matching would fall apart. A matching with no blocking pair is stable.
On preference set P1, the matching A–W, B–X, C–Y, D–Z looks fine row by row, but D ranks W 1st and W ranks D 1st: D–W is a blocking pair. (Demo: a matching that is not stable)
Deferred acceptance, step by step
David Gale and Lloyd Shapley (1962) showed that a stable matching always exists and gave a simple way to find it. One side proposes; on this page the students do, unless you pick schools.
- Take a free student (the page picks the one with the smallest letter).
- The student proposes to the best school on its list that it has not tried yet.
- A free school holds the offer. It does not commit: acceptance is deferred.
- A school that holds an offer compares the two students. If it prefers the new one, it trades up and the old student is free again. Otherwise it rejects the new one.
- Either way the loser crosses that school off its list. Repeat until nobody is free.
On P1, A, B and C get their first choices Y, W and Z. Then D proposes to W, and W trades B for D. B goes to Z, and Z trades C for B. C goes to Y, and Y trades A for C. One proposal set off three trade-ups in a row. A is rejected by W and ends at X, its 3rd choice: 8 proposals in all. (Demo: students propose, three trade-ups in a row)
Why it ends, and why the result is stable
- It ends. Each proposal crosses a school off one list or matches a free student, and no student proposes to the same school twice, so there are at most n² proposals. A sharper count gives n² − n + 1 (13 for n = 4).
- Everyone is matched. A school that got a proposal always holds someone from then on. If a student were rejected by all n schools, all n schools would hold other students, and there are only n − 1 others.
- No blocking pair. Students only move down their lists and schools only move up. Suppose student s prefers school h to its partner. Then s proposed to h earlier and lost it, so h holds someone it ranks above s, and h does not want s.
The worst cases come when everybody wants the same thing. In P2 every student ranks W first and every school ranks D first. Each new proposal to a popular school pushes someone further down: 10 proposals, a trade-up at every school, and A ends at Z, its last choice. (Demo: everyone has the same favourite)
Who proposes matters
One set of lists can have several stable matchings. The algorithm returns the one that is best for the proposers: every proposer gets the best partner it has in any stable matching (proposer-optimal). The same result is the worst stable matching for the receivers (receiver-pessimal).
On P1, when the schools propose they need only 5 proposals and end at A–Z, B–Y, C–X, D–W: three schools get their 1st choice, while A, B and C get their last. (Demo: schools propose on the same lists)
| who proposes | result on P1 | proposals | student ranks | school ranks |
|---|---|---|---|---|
| students | A–X, B–Z, C–Y, D–W | 8 | 3 + 2 + 2 + 1 = 8 | 1 + 2 + 3 + 3 = 9 |
| schools | A–Z, B–Y, C–X, D–W | 5 | 4 + 4 + 4 + 1 = 13 | 1 + 1 + 2 + 1 = 5 |
Where it is used
The US National Resident Matching Program places medical graduates in hospital residencies with a variant of deferred acceptance (Roth and Peranson, 1999); since then the applicants propose. Boston, New York and other cities use it to assign pupils to public schools. Proposing is strategy-proof for the proposers: no student can get a better school by lying about its list. Receivers sometimes can. Shapley and Alvin Roth shared the 2012 Nobel Prize in economics for this work.
Stable matching is a matching in a bipartite graph, like the maximum matchings on Bipartite Matching and the Hungarian Algorithm. There the goal is the most pairs or the lowest total cost; here every pair is allowed and the goal is that nobody wants to break up. Gale-Shapley is not a greedy algorithm in the usual sense (see Greedy vs DP Coin Change): an early "yes" can be taken back.
How to read the animation
- Each row is one preference list, best first. Green: current partner. Orange: the proposal being decided.
- Grey on the proposing side: already tried and lost. Grey on the receiving side: ranked below the partner, so that receiver would reject it.
- A blue box is a proposal, a red box a rejection or a dropped partner. Green lines are pairs; a red line is a blocking pair found by Check Stability.
What the page leaves out
Lists are complete and strict, sides are equal in size, and each school has one seat. The page leaves out schools with several seats (the hospitals/residents problem, where a hospital holds its best q offers), incomplete lists and ties, couples who must be placed together (the main complication in the real residency match), the lattice of all stable matchings and how to walk it with rotations, the stable roommates problem on one side (Irving's algorithm, where a stable matching may not exist), and the O(n²) implementation details.
See where this page fits on the Graph Algorithms mind map.