n men and n women, each with a complete, strictly-ranked preference list over the other side. A matching is stable if no two people who aren't paired together would both rather elope: no man and woman exist who each prefer each other to their own assigned partner. Gale and Shapley proved in 1962 that a stable matching always exists, no matter the preferences, and gave an algorithm that finds one: free men propose down their own list one at a time; a free woman accepts whoever proposes; an already-engaged woman switches only if the new proposer beats her current partner, and otherwise rejects him outright. It's the tenth entry filed under Greedy, and the first one that isn't scheduling, covering, or filling anything — it's pairing up two equal-size groups so the result can't be undone by any single pair acting alone.
Three men and three women, fixed preferences, built so the demo shows real drama either way you run it:
| Person | Preference order (favorite first) |
|---|---|
| M1 | W1 > W2 > W3 |
| M2 | W1 > W2 > W3 |
| M3 | W1 > W3 > W2 |
| W1 | M2 > M1 > M3 |
| W2 | M2 > M3 > M1 |
| W3 | M1 > M2 > M3 |
Every one of them ranks W1 or ranks second-choice collisions in a way that forces a real decision partway through — nobody sails through untouched. Pick who proposes and whether engagements can be broken, then press Step or Run.
Termination: every proposal a person makes is strictly further down their own
list than their last one, and each list holds exactly n names — so no one can
propose more than n times, and the whole run costs at most n²
proposals total, one bound per (proposer, receiver) pair. Completeness: a receiver,
once engaged, never goes back to being single — she only ever trades up, never down to
nothing. If some proposer were still free after every list ran out, every receiver would already
have to be engaged (each rejection only happens because she already has, or immediately takes, someone),
which pairs off all n receivers with n distinct proposers — leaving
none left over for the supposedly-still-free one. With equal counts on both sides that's a
contradiction, so no one is ever left out.
Stability: suppose, for contradiction, some man m and woman
w aren't matched to each other but each prefers the other to their own final partner.
Since men propose strictly downward, m ending up with someone worse than w
means he must have proposed to w at some point and been turned away — either
rejected on the spot or accepted and later dumped. Either way, at that exact moment w
was engaged to someone she liked at least as well as m. She only ever trades up from
there, so her actual final partner is at least that good in her eyes too — meaning she likes
her final partner at least as much as m, which directly contradicts the assumption
that she prefers m. No blocking pair can survive, so the result is always stable.
Run the demo with men propose: M1 and M2 both open with W1, W1 dumps M1 the instant M2 arrives (she prefers him), M3 then gets rejected by W1 outright and falls back to W3. Final result: M1–W2, M2–W1, M3–W3 — confirmed stable by an independent check against every man's full list, not just trusted from the run's own bookkeeping. Switch to women propose on the identical preferences: W1 and W2 both open with M2, M2 rejects W2 outright (he already has W1, whom he prefers), W2 falls back to M3. Final result: M1–W3, M2–W1, M3–W2 — also stable, and a genuinely different matching. M2–W1 holds either way (that pair is each other's mutual favorite, so no proposal order can ever pull them apart), but M1 and M3 trade partners depending purely on who gets to propose: M1 lands his second choice when men propose and his last choice when women do, the exact mirror of the theorem below.
This is also the site's first exact Greedy result where "exact" doesn't mean "the one right answer." Both matchings above are equally stable — there is no single ground truth here the way there is for, say, Huffman's optimal code length. What Gale-Shapley actually guarantees is stronger and stranger: whichever side proposes gets the best partner they could possibly have in any stable matching of these exact preferences, while the side that receives gets the worst partner they could possibly be stuck with in any stable matching — provably, not just on this example. Proposing is an advantage, not a formality.
function stableMatching(menPref, womenPref) {
const n = menPref.length;
// Precompute each woman's rank of every man, so "does she prefer X to Y"
// is an O(1) lookup instead of an O(n) scan of her list.
const rankW = womenPref.map(list => {
const r = {};
list.forEach((m, i) => { r[m] = i; });
return r;
});
const nextProposal = new Array(n).fill(0);
const wifeOf = new Array(n).fill(-1); // indexed by woman
const free = [...Array(n).keys()]; // free men, as a queue
while (free.length) {
const m = free.shift();
const w = menPref[m][nextProposal[m]++];
const cur = wifeOf[w];
if (cur === -1) {
wifeOf[w] = m; // she was free
} else if (rankW[w][m] < rankW[w][cur]) {
wifeOf[w] = m; // she trades up
free.push(cur); // her old partner is free again
} else {
free.push(m); // she keeps her current partner
}
}
const husbandOf = new Array(n);
wifeOf.forEach((m, w) => { husbandOf[m] = w; });
return husbandOf; // husbandOf[m] = w
}This is the men-proposing version; swapping which side proposes is the identical loop with the two preference arrays swapped, exactly what the demo's who proposes control does to the shipped script.
Making an engagement irrevocable — first acceptance wins, no trading up later — produces a genuinely unstable result, not just a different one. Run the demo with men propose and the broken rule: W1 accepts M1 immediately and that's locked in, so when M2 proposes next she's forced to reject him outright even though she prefers him, M3 gets locked out of W1 the same way and settles for W3. Final result: M1–W1, M2–W2, M3–W3 — and the demo's own independent stability check (re-examining every man's list against the real preferences, not the run's own bookkeeping) flags a real blocking pair: M2 prefers W1 to his assigned W2, and W1 prefers M2 to her assigned M1. Both would rather be with each other than stay put — exactly the elopement stability is supposed to rule out. This isn't a fluke of one small example: a 20,000-trial sweep with 4 men and 4 women and fresh random preferences each time found the correct algorithm stable on all 20,000 (as the proof above says it must be), while the locked-engagement variant was genuinely unstable on 68.8% of them. Deferred acceptance — letting a "yes" be provisional until something better shows up — isn't an optional refinement; it's the entire mechanism the stability proof leans on.
Whoever proposes is systematically favored, and that's a property of the algorithm, not an accident of these particular preferences. The Why it works section's theorem isn't just abstract: on this exact demo dataset, M1 gets his second choice when men propose but his last choice when women propose — identical preferences, opposite outcomes, purely because of who moves first. A real-world deployment that lets one side propose "for efficiency" is quietly choosing who the algorithm favors; the U.S. National Resident Matching Program, the best-known real deployment of this exact algorithm at national scale, is a case where which side gets to do the proposing was itself a matter of public debate, not just an implementation detail. This page's demo has no third "split the difference" option, and that's honest rather than an oversight — finding a stable matching that's fair to both sides at once is a different, harder problem this proposal algorithm was never designed to solve.
Time: O(n²) — at most n² proposals in
total (each of n proposers exhausts at most n names), and each proposal
does O(1) work given the precomputed rank table above; skip that precomputation and
each comparison degrades to an O(n) scan of the receiver's raw list, an easy
O(n³) mistake to make by accident. Space: O(n²)
for the preference lists and their rank tables, the same size as the input itself.
See Choosing a Greedy Strategy for how this entry fits the site's other nine Greedy entries — short version: it's exact by a third proof shape (no wasted proposal survives), joining exchange-argument and lower-bound-meets-upper-bound, and it's the guide's first entry where "exact" doesn't pin down one right answer at all.