Stable Matching
& Gale-Shapley
A Nobel Prize-winning algorithm that turns a romantic puzzle into one of computer science's most elegant solutions — and forms the blueprint for everything from medical residency placements to college admissions.
01 The Problem Origin
The stable matching problem was introduced in 1962 by mathematicians David Gale and Lloyd Shapley. Their paper, "College Admissions and the Stability of Marriage," asked a deceptively simple question: can you always arrange marriages between men and women such that no two people would prefer each other over their assigned partners?
02 Problem Formulation
Given n boys and n girls, where each person has a complete, strict preference list over all members of the opposite sex, find a perfect matching (every person is matched) such that the matching is stable.
Example: 2 Boys × 2 Girls
Consider Bob, Brad, Alice, and Angelina. Each has a ranked preference list over the opposite sex:
| Boy | 1st Choice | 2nd Choice |
|---|---|---|
| Bob | Angelina | Alice |
| Brad | Angelina | Alice |
| Girl | 1st Choice | 2nd Choice |
|---|---|---|
| Alice | Brad | Bob |
| Angelina | Brad | Bob |
Both boys prefer Angelina; both girls prefer Brad. There's a clear "conflict" — but as we'll see, a stable matching always exists.
03 Rogue Couples & Stability
A rogue couple (or blocking pair) is a boy b and girl g who are not matched to each other, but who both prefer each other over their current partners.
- b prefers g over his assigned partner b'
- g prefers b over her assigned partner g'
A perfect matching is stable if it contains no rogue couple. In other words, there is no unmatched pair who both prefer each other over their current partners.
Visual Intuition
Adam matched to Beth, Ben to Amy — but Adam prefers Amy and Amy prefers Adam. They'd elope!
Adam matched to Amy, Ben to Beth. No unmatched pair mutually prefers each other.
04 Why It's Tricky
Before giving the algorithm, consider why this isn't obvious. You might wonder: does a stable matching always exist? Could preferences create a cycle where no stable assignment is possible?
The Love Triangle: No Stable Matching in the Same-Sex Case
Suppose we have three boys — Alice, Bob, Carol (ignoring gender labels) — where:
| Person | 1st Choice | 2nd Choice |
|---|---|---|
| Alice | Bob | Carol |
| Bob | Carol | Alice |
| Carol | Alice | Bob |
This forms a cyclic preference. Any pairing leaves someone as a rogue:
- If Alice–Bob are paired: Carol and Bob prefer each other over their partners (rogue!)
- If Bob–Carol are paired: Alice and Carol prefer each other (rogue!)
- If Alice–Carol are paired: Alice and Bob prefer each other (rogue!)
05 The Gale-Shapley Algorithm
Gale and Shapley described their algorithm colorfully as a "mating ritual" that plays out over several days. The algorithm is sometimes called the Deferred Acceptance Algorithm because girls never immediately commit — they always keep their options open.
Each day proceeds in three phases:
- Morning — Boys Propose: Each free (unengaged) boy courts the highest-ranking girl on his list whom he hasn't already courted.
- Afternoon — Girls Deliberate: Each girl who receives proposals keeps (tentatively) her most preferred suitor and rejects all others. A girl who was previously "holding" a boy may now dump him for a better one.
- Evening — Crossed Off: Each rejected boy crosses the rejecting girl off his list.
The ritual ends when no boy is rejected — all current tentative engagements become marriages.
Pseudocode
06 Interactive Simulator
Step through the Gale-Shapley algorithm yourself. Watch how proposals, rejections, and upgrades unfold day by day.
07 Proof of Termination
Proof — Counting Crossings
Define the potential function Φ = total number of (boy, girl) pairs that have not yet been crossed off by that boy. Initially, Φ = n² (each boy has n girls on his list). At the start of each day after day 1, at least one new crossing occurs (since at least one boy was rejected the previous evening). So Φ strictly decreases by at least 1 each day. Since Φ ≥ 0, and it can't go below 0, the process must stop in at most n² steps. Adding the initial day, the algorithm terminates within n² + 1 days.
(all uncrossed)
day (day 2+)
to finish
08 Four Key Lemmas
These four lemmas are the building blocks for proving correctness and optimality. Each follows directly from how the algorithm works.
Formally: if boy b marries girl g, then b has courted every girl he prefers over g.
Proof
Boy b proposes in order of his preference list. He proposes to g only after being rejected by or rejected from all girls above g on his list. Since b marries g, he never goes below g — meaning he has courted every girl he prefers to g.
Formally: if boy b remains single at the end, then b has courted all n girls.
Proof
By the termination condition, the algorithm stops when no boy is rejected. If b is still free, he must have been rejected by everyone on his list (otherwise the algorithm would have continued with b courting another girl). Therefore b has proposed to all n girls.
Formally: girl g marries the best boy among those who ever courted her, by her preference ordering.
Proof
When girl g receives multiple proposals on any day, she keeps her most preferred suitor and rejects the rest. Crucially, once g holds onto a boy, she only ever upgrades — she replaces him only if someone she prefers comes along. Therefore her final partner is the best boy who ever courted her.
Formally: if at least one boy courts girl g, then g ends up married.
Proof
Once g receives a proposal, she holds onto someone (by the algorithm's rule). A girl only releases a boy to take a better one — she never becomes free again once she's been courted. Therefore if she's ever courted, she ends up holding someone when the algorithm terminates.
09 Proof of Correctness
Proof
Suppose for contradiction that some boy b does not marry. By Lemma 2, b courted all n girls. By Lemma 4, every girl he courted gets married. So all n girls are married. But there are only n boys (equal groups), and all n girls are married to boys — so all boys must also be married. Contradiction with b being single.
Proof — by Contradiction
Suppose boy b and girl g form a rogue couple: b prefers g over his wife g', and g prefers b over her husband b'.
Since b prefers g over g', by Lemma 1, b must have courted g before g' (he proposes in decreasing preference order).
But g ended up with b', not b. By Lemma 3, g marries her favorite among all who courted her. Since b courted g and g didn't end up with b, she must prefer b' over b.
But this contradicts our assumption that g prefers b over b'. ↯
10 Who Benefits? Boy-Optimal & Girl-Pessimal
The algorithm doesn't just produce a stable matching — it produces a specific one with a remarkable fairness (or unfairness) property.
A girl g is a valid partner for boy b if there exists some stable matching in which they are together. Among all valid partners, b's optimal mate is his most preferred, and his pessimal mate is his least preferred valid partner.
Proof sketch
Suppose for contradiction that some boy b is rejected by his optimal mate g during the algorithm — g drops b for some boy b' she prefers. So g prefers b' over b.
Since g is b's optimal mate, there exists a stable matching S where b is with g. In S, b' is matched to some girl g' (not g).
But b' prefers g over his current partner g' (he wouldn't have proposed to g first if he preferred g' — boys propose in order). And g prefers b' over b. So (b', g) is a rogue couple in S — contradicting S being stable. ↯
Proof sketch
Let M* be the Gale-Shapley matching. Suppose girl g is matched to b in M*. Suppose there is another stable matching S where g is matched to b', and suppose g prefers b' over b (i.e., b is not pessimal for g).
By Theorem 4, b' gets his optimal mate in M*. Since b' is with g in S, g is a valid partner for b'. So b''s optimal mate is at least as good as g. But in M*, b' ends up with someone at least as preferred as g. In S, g prefers b' over her partner in S only if... This leads to a contradiction with S being stable.
11 Uniqueness
An interesting property: the boy-optimal stable matching is unique, as is the girl-optimal stable matching. But these two may differ.
If running Gale-Shapley with boys proposing gives the same result as girls proposing, then exactly one stable matching exists. Conversely, if they differ, there are at least two distinct stable matchings.
Run GS with girls proposing → result M₂.
If M₁ = M₂: unique stable matching. If M₁ ≠ M₂: multiple stable matchings exist.
12 Number of Stable Matchings
The number of stable matchings can be exponential in the worst case. This means we can't enumerate all of them efficiently.
For certain preference lists with n boys and n girls, the number of stable matchings can be as large as 2^(n/2).
Consider this construction for n = 4 (2k with k=2): arrange preferences so that stable matchings correspond to binary choices at each of k "decision points." Each decision point independently doubles the count, giving 2k = 2n/2 total stable matchings.
13 Optimization Criteria
Among all stable matchings, which one should we pick? Researchers have proposed several optimality criteria for choosing a "best" stable matching. Their complexity tells an interesting story.
For a stable matching M, define the rank of a pair (b, g) in M as boy b's rank of g on his list. Then:
r(M) = max rankc(M) = Σ ranksd(M) = |Σboys - Σgirls|| Criterion | Goal | Complexity | Notes |
|---|---|---|---|
| Min-Regret | Minimize worst rank | Polynomial | Run GS, check and restrict |
| Min-Egalitarian | Minimize total ranks | Polynomial | Network flow approach |
| Sex-Equal | Equalize boys' & girls' total ranks | NP-hard | Requires searching exponential space |