Stable Matching

Stable matching asks a different question from every other matching problem in this vault: not how many pairs can we form, but which pairing will hold together. Each agent submits a strict ranking over the agents on the other side; a matching is stable when no two agents who are not matched to each other would both rather be. Such a pair is called a blocking pair, and the definition of a solution is entirely negative — a stable matching is one against which no blocking pair exists. There is no objective function anywhere in the statement. Gale and Shapley proved in 1962 that for the two-sided (bipartite) case a stable matching always exists, and proved it constructively by exhibiting deferred acceptance (Gale & Shapley 1962, summarised in Kleinberg & Tardos ch. 1). The set of all stable matchings turns out to carry a startling amount of structure — it is a distributive lattice (Knuth 1976, attributing the result to Conway) whose two extremes are exactly the proposer-optimal and receiver-optimal matchings. Drop the bipartite assumption and the guarantee evaporates: the stable roommates problem has instances with no stable matching at all, exhibited in Gale and Shapley’s own paper and decided in polynomial time only in 1985 by Irving.

This is not the same problem as Bipartite Matching

The vault already holds a 3,788-word note on maximum bipartite matching, and the two problems share a picture — two columns of dots, edges between them, pick a set of edges with no shared endpoint. They are otherwise unrelated:

	Bipartite Matching (maximum matching)	Stable matching (this note)
Input	a graph: an edge exists or it does not	complete strict rankings from every agent
Objective	maximise `	M
Solution concept	an optimum of a scalar objective	absence of a blocking pair
Certificate of optimality	an augmenting path / König min-vertex-cover	check all n² pairs for a blocking violation
Solution set	many optima, no useful structure among them	a distributive lattice
Algorithms	augmenting paths, Hopcroft–Karp O(E√V), max-flow	deferred acceptance O(n²)
Non-bipartite case	Blossom algorithm, still polynomial, still always exists	may have no solution at all

The single sharpest distinction: maximum matching optimises a global count and ignores preferences entirely; stable matching honours per-agent preferences and optimises nothing. They must never be merged, and a solution to one is not evidence about the other — the maximum matching of a stable-matching instance is trivially of size n (every perfect matching is maximum), and the stable matching of a maximum-matching instance is undefined because there are no rankings.

Mental Model — Stability Is a Negative Condition

Start with the mechanism the definition is protecting against. Suppose a central clearinghouse announces an assignment of n doctors to n hospital programmes. Two participants — a doctor d and a hospital h who were not matched to each other — compare notes. If d would rather be at h than at her assigned programme, and h would rather have d than the doctor it was assigned, then nothing the clearinghouse says can stop them. They sign a private contract outside the match, and the announced assignment falls apart. The pair (d, h) is a blocking pair, and the clearinghouse has produced an unstable matching.

Stability says exactly this and nothing more: there is no such pair. Kleinberg and Tardos’s framing is the cleanest — “individual self-interest prevents any hospital–student side deal” (slide 3). It is a self-enforcement property, not a quality property. A stable matching can be, and often is, terrible: it can give every agent their last acceptable choice, and it will still be stable if nobody can find a partner who reciprocates the wish to defect.

flowchart TB
    subgraph MATCH["announced matching M"]
        D1["doctor d"] ---|matched| H1["hospital h'"]
        D2["doctor d'"] ---|matched| H2["hospital h"]
    end
    D1 -. "d prefers h to h'" .-> H2
    H2 -. "h prefers d to d'" .-> D1
    BLOCK["BLOCKING PAIR (d, h)<br/>both strictly prefer each other<br/>to their assigned partner<br/>=> they defect, M collapses"]
    D1 --> BLOCK
    H2 --> BLOCK
    STABLE["M is STABLE<br/>iff no such pair exists<br/>over all n squared candidate pairs"]
    BLOCK -.->|"absent for every pair"| STABLE

What it shows: the only way a matching can fail. Two agents matched elsewhere both prefer each other; the arrows of desire point both ways, so the defection is mutually profitable and needs no coordinator. The insight to take: stability is checked pair by pair, and one bad pair is enough to destroy the whole assignment — which is why the verification routine below is an exhaustive O(n²) double loop and not a clever algorithm.

Why “no blocking pair” and not an optimality criterion

This is the conceptual centre of the note, and it is worth being explicit about because every other matching problem in this vault is an optimisation problem.

You could imagine defining the “right” matching by an objective: minimise the total rank each agent assigns their partner (the egalitarian matching), or minimise the worst rank anybody receives (the minimax matching), or maximise the number of agents who get their first choice. All of those are well-posed and all of them are computable. None of them is what the problem is asking for, for three reasons.

First, an objective needs interpersonal comparability that does not exist. Summing ranks across agents asserts that doctor A’s move from her 3rd to her 2nd choice is exactly as valuable as doctor B’s move from her 7th to her 6th. Rankings are ordinal — they carry no such information. Any scalar objective smuggles in a cardinal assumption the input never supplied. Roth makes the point in the language of cooperative game theory: stability is a property of the core of the matching game, not of a social welfare function (Roth 1982; the Nobel committee’s summary calls stability “a central concept in cooperative game theory”, popular background 2012).

Second, an optimum is not self-enforcing. The egalitarian matching minimises total rank, but nothing stops two agents inside it from discovering they prefer each other and walking out. If they can, the clearinghouse’s announcement was a suggestion, not an assignment. Stability is precisely the condition under which the announcement binds. This is not a theoretical nicety — it is the empirical finding that made the field. Roth studied regional medical-matching schemes in the United Kingdom and found that mechanisms producing stable matchings survived and mechanisms producing unstable ones “had broken down in various ways” (Nobel popular background; the original study is Roth 1984).

Third, stability is the condition under which a centralised market can replace a decentralised one at all. The pre-1952 American market for medical interns had unravelled to the point where contracts “were typically being signed two years in advance” of graduation (Roth & Peranson 1999). A clearinghouse fixes unravelling only if participants have no incentive to transact outside it. That is stability, restated.

The vocabulary shifts by field

Computer scientists say unstable pair (Kleinberg & Tardos); economists say blocking pair or the pair blocks µ; cooperative game theorists say the matching is not in the core. In the one-to-one case these are the same condition. They diverge once hospitals have multiple seats or agents may be unmatched, where “blocking” has to be extended to a coalition and to individual rationality — see the multi-seat definition quoted below.

Formal Statement, With a Worked Instance

An instance of the stable marriage problem consists of two disjoint sets A and B, each of size n, and for every agent a strict total order over all n agents on the other side. A matching M is a bijection A → B. Writing M(a) for a’s partner and a ≻ b ≻ c for “strictly prefers”, the matching is unstable if there exist a ∈ A and b ∈ B with

• b ≻_a M(a) — a strictly prefers b to the partner M gave them, and
• a ≻_b M⁻¹(b) — b strictly prefers a to the partner M gave them,

and stable otherwise. Every symbol: ≻_a is agent a’s own ranking; M(a) is who a got; M⁻¹(b) is who b got. Both conditions must hold — a pair where only one side wants to defect is not a blocking pair, because the other side will not sign.

Take the three-by-three instance from Kleinberg and Tardos’s slide 19, which is the smallest instance in the literature with more than one stable matching:

proposer	1st	2nd	3rd		receiver	1st	2nd	3rd
A	X	Y	Z		X	B	A	C
B	Y	X	Z		Y	A	B	C
C	X	Y	Z		Z	A	B	C

M = {A–X, B–Y, C–Z} is stable. Walk the two pairs that look dangerous.

• (B, X). Receiver X ranks B first and is holding A, so X would love to defect. But a blocking pair needs both sides: B’s list is Y X Z, and B is holding Y — their first choice. B will not move. Not a blocking pair. This is the case that catches people: one side desperately wants the swap and it still does not block.
• (A, Y). Proposer A’s list is X Y Z and A holds X, so A will not defect. Stop there — there is no need to ask Y at all. A blocking pair is a conjunction, so the first false ends the test.

Every remaining pair involves C or Z, who are ranked last by everyone who is not already stuck with them, so nothing else blocks either.

M' = {A–Y, B–X, C–Z} is the second stable matching. Note that A and B have swapped, A is worse off, B is better off, and C and Z are unmoved. That swap is the whole of the lattice structure in miniature: the stable matchings of an instance differ from each other by rotations that make one side uniformly better and the other side uniformly worse.

Verified here (2026-08-28, gcc 16.1.1, /proc/loadavg 6.64 4.79 3.62 at run start) by exhaustive enumeration of all 3! = 6 perfect matchings with an O(n²) blocking-pair check on each:

KT 3x3 (slide 19) : n=3, |stable set| = 2
  M0                 A-0 B-1 C-2   sumRankA=5 sumRankB=7 blocking=0
  M1                 A-1 B-0 C-2   sumRankA=7 sumRankB=5 blocking=0

(0 = X, 1 = Y, 2 = Z; sumRankA is the total 1-based rank each proposer assigns their partner, so lower is better for that side.) The two stable matchings have sumRankA of 5 and 7 and sumRankB of 7 and 5 — exactly mirrored. Nothing forced that; it falls out of the structure.

Checking Stability: Real C

Stability has no clever certificate. To verify a claimed stable matching you check every one of the n² ordered pairs. This is the routine every other measurement in this note and in The Gale-Shapley Algorithm is validated against, so it is written to be obviously correct rather than fast.

/* rank tables: ra[a*n + b] = position of b in a's list (0 = most preferred)
 *              rb[b*n + a] = position of a in b's list
 * mA[a] = the partner matching M gives to proposer a, or -1 if unmatched.
 * Returns the number of blocking pairs; 0 means M is stable. */
static long count_blocking(const Inst *I, const int *mA)
{
    int n = I->n;
    int *mB = malloc(sizeof(int) * (size_t)n);
    for (int b = 0; b < n; b++) mB[b] = -1;
    for (int a = 0; a < n; a++) if (mA[a] >= 0) mB[mA[a]] = a;   /* invert M */
 
    long bad = 0;
    for (int a = 0; a < n; a++) {
        for (int b = 0; b < n; b++) {
            if (mA[a] == b) continue;                 /* already partners */
            /* an unmatched agent prefers ANY acceptable partner to nothing */
            int a_prefers_b = (mA[a] < 0) ||
                (I->ra[(size_t)a*n + b] < I->ra[(size_t)a*n + mA[a]]);
            int b_prefers_a = (mB[b] < 0) ||
                (I->rb[(size_t)b*n + a] < I->rb[(size_t)b*n + mB[b]]);
            if (a_prefers_b && b_prefers_a) bad++;    /* BOTH sides must want it */
        }
    }
    free(mB);
    return bad;
}

Line by line, the three things that go wrong when people write this from memory:

• The rank table, not the preference list. pref[a][k] answers “who is a’s k-th choice”; rank[a][b] answers “where does b sit on a’s list”. Stability checking asks the second question, so precompute rank[a][pref[a][k]] = k once. Searching the preference list per comparison turns an O(n²) check into O(n³).
• Both conjuncts, in the right direction. a_prefers_b reads a’s table; b_prefers_a reads b’s table. Reading both from one table is the single most common bug and produces a checker that certifies unstable matchings.
• The unmatched case. With complete lists and |A| = |B| nobody is unmatched, but the moment lists are incomplete (agents may declare others unacceptable) a free agent prefers anyone acceptable to being alone. Omitting the < 0 branches makes the checker silently permissive on exactly the instances where it matters — see the truncation experiment in The Gale-Shapley Algorithm, which relies on this branch being right.

flowchart TB
    IN["matching M, rank tables ra and rb"] --> INV["invert M: build mB from mA<br/>so both directions are O(1)"]
    INV --> LOOP["for every ordered pair (a, b)<br/>n squared iterations"]
    LOOP --> SKIP{"is b already<br/>a's partner?"}
    SKIP -->|yes| NEXT["next pair"]
    SKIP -->|no| T1{"ra[a][b] < ra[a][M(a)] ?<br/>i.e. does a prefer b?"}
    T1 -->|no| NEXT
    T1 -->|yes| T2{"rb[b][a] < rb[b][M(b)] ?<br/>i.e. does b prefer a?"}
    T2 -->|no| NEXT
    T2 -->|yes| BAD["BLOCKING PAIR<br/>increment the counter"]
    NEXT --> LOOP
    LOOP --> DONE{"counter == 0 ?"}
    DONE -->|yes| OK["M is STABLE"]
    DONE -->|no| NO["M is UNSTABLE"]

What it shows: the exact control flow of count_blocking. The insight to take: the two rank-table lookups are the whole algorithm, and they must read different tables — the short-circuit at T1 is why an implementation that reads ra twice never reports a false negative and therefore looks correct until it silently certifies garbage.

The checker is also how the existence claim gets tested rather than assumed: enumerate all n! perfect matchings, run count_blocking on each, count the survivors. That is O(n! · n²) and useless above n ≈ 10, but for n ≤ 8 it is a complete oracle, and every structural claim below was checked against it.

Existence in the Bipartite Case

Gale and Shapley’s theorem is that for two-sided instances with strict complete preferences, at least one stable matching always exists. The proof is not an existence argument in the topological sense — it is an algorithm that terminates with a stable matching, which is why matching deployed in the real world and general-equilibrium computation did not. (The contrast is worth holding onto: Nash Equilibrium also always exists in finite games, but by a fixed-point argument, and finding one is PPAD-complete. Gale–Shapley proves existence by construction in O(n²). See the parent Games and Strategic Systems in C MOC, which makes this the organising distinction of the whole ladder.)

The algorithm and its termination/correctness proofs live in The Gale-Shapley Algorithm and are not repeated here. What belongs in this note is what the existence theorem buys you and what it does not:

• It buys you: the guarantee that the clearinghouse always has something to announce, for every possible profile of submitted rankings, with no feasibility check needed up front.
• It does not buy you: uniqueness. Instances routinely have many stable matchings, and which one you produce is a choice with distributional consequences. That is the subject of the lattice, below, and of proposer-optimality in the sibling note.
• It does not survive: dropping bipartiteness (§ stable roommates), adding couples with joint preferences (§ couples), or adding cardinal side constraints. Each of those is a separate negative result, and each has bitten a real deployment.

Resolved 2026-08-29 — the primary source has now been read

An earlier revision of this note flagged everything attributed to Gale & Shapley 1962 as second-hand, because the JSTOR record at https://www.jstor.org/stable/2312726 returns HTTP 200 with a landing page containing no article text, and the mirror at https://www.eecs.harvard.edu/cs286r/courses/fall09/papers/galeshapley.pdf is a page-image scan from which pdftotext recovers only the JSTOR cover boilerplate.

The route that worked. Josep Massó’s paper directory at Universitat Autònoma de Barcelona — already the source of the Dubins–Freedman paper cited in this note — also hosts the original: pareto.uab.es/jmasso/pdf/GaleShapleyAMM1962.pdf, fetched 2026-08-29 at HTTP 200, 832,155 bytes, 8 pages, whose cover page identifies it as The American Mathematical Monthly, Vol. 69, No. 1 (Jan., 1962), 9–15, by D. Gale and L. S. Shapley. It is a genuine scan of the article — and it has no text layer at all: pdffonts lists zero embedded fonts and pdftotext returns 8 characters. That is an extraction failure, not a retrieval failure, and the two must not be confused; the pages are perfectly legible once rendered with pdftoppm -png -r 135. The same directory serves Gale & Sotomayor’s Ms. Machiavelli and the Stable Matching Problem, AMM 92(4), Apr. 1985, pp. 261–268 (GaleSotomayorAMM1985.pdf, 1,022,005 bytes, 9 pages), under the same conditions.

The existence theorem, transcribed from page 12 of the scan:

Theorem 1. There always exists a stable set of marriages.

Seven words, with no hypotheses stated in the theorem itself — the standing assumptions (equal numbers of men and women, complete rankings, and “for convenience we assume there are no ties”) are set up in §2 and §3. Their definition of the thing being avoided, from page 10, is likewise stated in the college-admissions vocabulary rather than the marriage one:

Definition. An assignment of applicants to colleges will be called unstable if there are two applicants α and β who are assigned to colleges A and B, respectively, although β prefers A to B and A prefers β to α.

The marriage restatement follows in §3: “we call a set of marriages unstable … if under it there are a man and a woman who are not married to each other but prefer each other to their actual mates.” Two further details from the same page are worth recording because they are routinely mis-attributed. Their proof of Theorem 1 is the deferred-acceptance construction, and they bound it themselves — “Eventually (in fact, in at most n² − 2n + 2 stages) every girl will have received a proposal” — so the quadratic bound is in the original paper, not a later addition (see The Gale-Shapley Algorithm). And the optimality definition is stated one-sidedly, from page 10: “A stable assignment is called optimal if every applicant is at least as well off under it as under any other stable assignment.”

The roommates counterexample, transcribed from Example 3 on page 12:

Example 3. A problem similar to the marriage problem is the “problem of the roommates.” An even number of boys wish to divide up into pairs of roommates. A set of pairings is called stable if under it there are no two boys who are not roommates and who prefer each other to their actual roommates. An easy example shows that there can be situations in which there exists no stable pairing. Namely, consider boys α, β, γ and δ, where α ranks β first, β ranks γ first, γ ranks α first, and α, β and γ all rank δ last. Then regardless of δ’s preferences there can be no stable pairing, for whoever has to room with δ will want to move out, and one of the other two will be willing to take him in.

One correction to how this note previously presented it: Gale and Shapley specify only each of α, β, γ’s first choice and that all three rank δ last — they say nothing about second choices, and δ’s list is explicitly arbitrary. The table in the stable-roommates section below (1: 2,3,4, 2: 3,1,4, 3: 1,2,4) is a specialisation of their instance with the middle entries filled in, taken from Irving’s restatement; it is a valid instance of their family, but the original is the more general statement, and the argument does not depend on the second choices at all. The brute-force verification below therefore confirms one member of the family rather than the family; the family-level argument is Gale and Shapley’s own sentence, quoted in full above.

A second source failed in a way that is not recoverable this way, and is recorded for contrast: the Royal Swedish Academy’s scientific background document for the 2012 Prize (advanced-economicsciences2012.pdf) fetched at HTTP 200 and 727 KB, and pdftotext reports 14,294 “words” — but everything past the cover page is mojibake (grep -c stable returns 0), because the embedded subset fonts carry no ToUnicode map. Word count is not a validity check. The Academy’s shorter popular background at popular-economicsciences2012.pdf extracts cleanly and is what is cited in this note wherever the Nobel committee is quoted.

The Lattice Structure of the Stable Set

This is the surprising part, and the part most treatments of stable matching skip.

Define a partial order on the stable matchings of a fixed instance from one side’s point of view. Write M ≽_A M' when every proposer weakly prefers their partner in M to their partner in M'. It is not obvious that this relation is ever interesting — two matchings could easily disagree, with proposer a preferring M and proposer a' preferring M', making them incomparable. They can be incomparable, and often are. What is not obvious at all is the following.

Theorem (Conway, reported in Knuth 1976). The set of stable matchings of a stable-marriage instance, ordered by ≽_A, is a distributive lattice.

Unpacking that symbol by symbol, because it is doing a lot of work:

• A lattice is a partial order in which every pair of elements has a least upper bound (the join) and a greatest lower bound (the meet). Here the operations are pointwise and almost insultingly simple. Given two stable matchings M and M', define M ∧ M' by giving each proposer a whichever of M(a) and M'(a) a prefers, and M ∨ M' by giving each proposer whichever they prefer less. The claim is that both of these are themselves stable matchings. That is the shock: take two valid solutions, let every proposer independently grab their favourite of their two partners, and — although nothing in the construction checks for collisions — no two proposers pick the same receiver, and the result has no blocking pair.
• Distributive means the two operations distribute over each other: X ∧ (Y ∨ Z) = (X ∧ Y) ∨ (X ∧ Z). Distributivity is a genuinely restrictive property; most lattices are not distributive.
• Because the lattice is finite and non-empty, it has a unique top and a unique bottom. The top under ≽_A — the matching every proposer weakly prefers to every other stable matching — is the proposer-optimal stable matching. The bottom is the proposer-pessimal one. And by a separate theorem the order reverses exactly for the other side: the proposer-optimal matching is simultaneously receiver-pessimal. Roth states the consequence squarely: “all students have a common interest in the ‘student-optimal’ stable outcome, while all colleges prefer the ‘college-optimal’ stable outcome” (Roth 1982 §7) — a common interest that is surprising given that students compete with each other for colleges, and colleges compete with each other for students. Restricted to the stable set, that competition vanishes.

Both extremes are computable in O(n²): run deferred acceptance with A proposing to get the top, run it with B proposing to get the bottom. That is developed in The Gale-Shapley Algorithm, where the asymmetry is the whole point.

The lattice, drawn

The four-by-four instance from Kleinberg & Tardos’s quiz 3 has exactly six stable matchings — enumerated here by brute force over all 4! = 24 perfect matchings, which reproduces the six the slide lists, in the same set.

flowchart TB
    M3["M3 = A-Y B-Z C-W D-X<br/>proposer ranks (1,1,1,1)<br/>PROPOSER-OPTIMAL, receiver-pessimal"]
    M5["M5 = A-Z B-Y C-W D-X<br/>proposer ranks (2,2,1,1)"]
    M2["M2 = A-X B-Y C-W D-Z<br/>proposer ranks (3,2,1,2)"]
    M4["M4 = A-Z B-W C-Y D-X<br/>proposer ranks (2,3,2,1)"]
    M1["M1 = A-X B-W C-Y D-Z<br/>proposer ranks (3,3,2,2)"]
    M0["M0 = A-W B-X C-Y D-Z<br/>proposer ranks (4,4,2,2)<br/>proposer-pessimal, RECEIVER-OPTIMAL"]
    M3 --> M5
    M5 --> M2
    M5 --> M4
    M2 --> M1
    M4 --> M1
    M1 --> M0

What it shows: the Hasse diagram of the six stable matchings of the KT 4×4 instance, best-for-proposers at the top, ordered by ≽_A. Ranks in parentheses are 1-based positions of A’s, B’s, C’s, D’s partner on that proposer’s own list. The insight to take: M2 and M4 are incomparable — A prefers M4, B prefers M2 — and the lattice supplies their meet (M5, where each proposer takes their better of the two: (2,2,1,1) is the componentwise minimum of (3,2,1,2) and (2,3,2,1)) and their join (M1, the componentwise maximum). Both of those are again stable. Descending the diagram, every proposer gets weakly worse and every receiver gets weakly better, monotonically, all the way from proposer-optimal to receiver-optimal.

The proposer-rank vectors make the componentwise structure literal: M5 = min(M2, M4) and M1 = max(M2, M4) coordinate by coordinate, and both minimum and maximum land back inside the stable set. There is no reason from the definition of stability to expect that.

Measured here

Structure claims deserve to be checked, not recited. The following was measured on 2026-08-28 (gcc 16.1.1 -O2, splitmix64 PRNG, fixed seed 20260828, /proc/loadavg 6.64 4.79 3.62 at start and 6.59 4.81 3.64 at end). For each random instance the program enumerates all perfect matchings, keeps the stable ones, then tests every pair for meet/join closure and every triple for distributivity:

| instances | n | mean |stable set| | max | lattice closure held | distributivity held | A-proposing GS lattice top | B-proposing GS lattice bottom | |---|---|---|---|---|---|---|---| | 20,000 | 4 | 1.496 | 6 | 20,000 / 20,000 | 20,000 / 20,000 | 20,000 / 20,000 | 20,000 / 20,000 | | 2,000 | 6 | 1.933 | 8 | 2,000 / 2,000 | 2,000 / 2,000 | 2,000 / 2,000 | 2,000 / 2,000 |

Three things to read off this table. One: closure and distributivity held on every instance — consistent with the theorem, and a useful smoke test that the meet/join implementation is right. Two: deferred acceptance lands exactly on the lattice extremes, every time, independently confirming the proposer-optimality theorem by a completely different route (enumerate everything, then compare) than the usual proof. Three: the mean stable-set size is small — under 2 even at n = 6. Most random instances have a unique stable matching, in which case the whole lattice collapses to a point and the proposer/receiver distinction is empty. That is why the distributional argument only becomes visible in aggregate, and it foreshadows the “core convergence” finding in real markets discussed under Production Notes.

The asymptotics run the other way, though: Pittel (1989) proved that for uniformly random preferences the expected number of stable matchings is asymptotic to e⁻¹ · n · ln n, so the set does grow — just slowly, and from a very small base. At n = 6, e⁻¹ · 6 · ln 6 ≈ 3.95, well above the measured 1.93; the asymptotic has not remotely kicked in at that size, which is exactly the kind of gap that makes small-n intuition misleading.

Uncertain

Verify: whether the distributive-lattice theorem is due to Conway or to Knuth, and the exact 1976 citation. Reason: the primary source is D. E. Knuth, Mariages Stables (Presses de l’Université de Montréal, 1976) — a monograph, in French, not available online; every source consulted here cites it second-hand. Irving 1985 cites Knuth’s book as reference [3] but discusses it only for average-case analysis, not the lattice. En & Faenza 2026 write that stable matchings “can be organized to form a distributive lattice under a natural partial order Knuth (1976)”; several secondary write-ups attribute the theorem itself to J. H. Conway and Knuth’s book as the place it was reported. To resolve: read Mariages Stables directly.

A 2026 refinement worth knowing about

The distributive-lattice theorem is a statement about the one-to-one marriage model. Blair (1984) proved the converse — every finite distributive lattice arises as the stable-matching lattice of some instance — so “distributive” is exactly the right class there, not an artefact. In April 2026 En & Faenza showed that once agents have general path-independent choice functions (rather than a strict ranking with a quota), all finite lattices arise, including non-distributive ones, answering an open question of Blair (1988) (arXiv:2504.17916v3). The same paper proves minimum-cost stable matching NP-hard under those assumptions. So: distributive in the classical model, not in general. As of 2026-08-28 that paper is a v3 arXiv preprint; treat the result as recent rather than settled textbook material.

The Negative Results

Existence is a two-sidedness theorem, not a matching theorem. Three separate relaxations destroy it, and each one has cost a real deployment real money.

1. Stable roommates: drop bipartiteness and existence dies

The stable roommates problem takes a single set of 2m people, each ranking the other 2m − 1, and asks for a partition into m pairs with no blocking pair. It is the natural non-bipartite generalisation, and Gale and Shapley raised it in the same 1962 paper — as Example 3, immediately before Theorem 1 — along with the observation that it can be unsolvable (Gale & Shapley 1962, p. 12, transcribed in the resolution callout above). Their statement fixes only each of the first three people’s first choice and the fact that all three rank the fourth last; the concrete instance below fills in the middle entries, following Irving’s restatement (Irving 1985 §1):

person	1st	2nd	3rd
1	2	3	4
2	3	1	4
3	1	2	4
4	arbitrary

Irving’s one-line explanation is the whole proof: “anyone paired with person 4 will cause instability.” Persons 1, 2 and 3 form a preference cycle — 1 wants 2, 2 wants 3, 3 wants 1 — and all three rank 4 last. One of the three must be paired with 4, and that person’s own first choice is available to defect with, because the remaining two are paired with each other and one of them ranks the stranded person above their current partner. With four people there are only three possible pairings, so the case analysis is complete; the same instance appears as Kleinberg & Tardos’s slide 10 with the labels A B C D, and their three blocking pairs agree with the three derived below.

flowchart LR
    subgraph P1["pairing (1,2) (3,4)"]
        direction TB
        A1["2 holds 1, but 2's list is 3 1 4<br/>so 2 prefers 3"] --> B1["3 holds 4, but 3's list is 1 2 4<br/>so 3 prefers 2"]
        B1 --> C1["pair (2,3) BLOCKS"]
    end
    subgraph P2["pairing (1,3) (2,4)"]
        direction TB
        A2["1 holds 3, but 1's list is 2 3 4<br/>so 1 prefers 2"] --> B2["2 holds 4, but 2's list is 3 1 4<br/>so 2 prefers 1"]
        B2 --> C2["pair (1,2) BLOCKS"]
    end
    subgraph P3["pairing (1,4) (2,3)"]
        direction TB
        A3["1 holds 4, but 1's list is 2 3 4<br/>so 1 prefers 3"] --> B3["3 holds 2, but 3's list is 1 2 4<br/>so 3 prefers 1"]
        B3 --> C3["pair (1,3) BLOCKS"]
    end
    P1 --> R["every pairing has a blocking pair<br/>=> NO stable matching exists"]
    P2 --> R
    P3 --> R

What it shows: the exhaustive case analysis for the four-person roommates instance. There are only three ways to partition four people into two pairs, and each one is destroyed by a specific blocking pair. The insight to take: the obstruction is an odd preference cycle among 1, 2, 3 — a structure that simply cannot occur in a two-sided instance, because there every cycle alternates sides and is therefore even. That parity is the entire content of the Gale–Shapley existence theorem.

Confirmed by brute force here (2026-08-28, /proc/loadavg 4.31 4.82 3.87 at run start) — enumerate all pairings, run the roommates blocking-pair check on each:

Case 1 -- Gale & Shapley's size-4 roommates instance (Irving 1985 Sect.1) (n=4)
   0: 1 2 3        (0-based transcription of the table above)
   1: 2 0 3
   2: 0 1 3
   3: 0 1 2
   brute force : 0 stable matching(s)
   Irving      : reports NO stable matching
   agreement   : YES

Irving’s algorithm, implemented

The problem stayed open for 23 years. Knuth listed it among twelve research problems in Mariages Stables and “suggested that it may be possible to prove the problem NP-complete” (Irving 1985 §1). Irving’s 1985 paper settles it in the other direction with an O(n²) algorithm that decides existence and constructs a stable matching when one exists. It runs in two phases.

Phase 1 — the proposal sequence. Structurally identical to deferred acceptance, but with one set instead of two, so a person can simultaneously be proposing and holding a proposal. Everyone proposes down their list; a recipient holds the best proposal seen so far and rejects the rest; a rejected proposer moves on. Irving’s Lemma 1 is the load-bearing result: if y rejects x during this sequence, then x and y cannot be partners in any stable matching. Phase 1 therefore ends either with every person holding a proposal, or with someone rejected by everybody — in which case Corollary 1.2 says no stable matching exists, since that person has no possible partner at all. This is what happens on the size-4 instance above.

When phase 1 does terminate with everyone held, Corollary 1.3 lets you reduce the lists: a person y holding a proposal from x deletes everyone they like less than x. The reduced lists have the pleasing property that b is on a’s list if and only if a is on b’s.

Phase 2 — all-or-nothing cycles. Phase 1 usually leaves some lists with more than one entry, and unlike the bipartite case you cannot just stop. Irving’s device is a cyclic sequence a₁, …, a_r in which the second person on aᵢ’s reduced list is the first person on aᵢ₊₁’s. He calls it an all-or-nothing cycle, and Lemma 3 justifies the name: in any stable matching contained in the reduced lists, aᵢ is paired with bᵢ (their first choice) either for all i or for none; and if there is a stable matching where they are paired, there is another where they are not. So you may safely force the whole cycle to be rejected. Finding one is mechanical: from any person p₁ with a long list, let qᵢ be the second on pᵢ’s list and pᵢ₊₁ be the last on qᵢ’s list; the sequence must eventually repeat.

The reduction repeats until either some list becomes empty (no stable matching, Corollary 3.2) or every list has length one, at which case Lemma 4 says the lists are a stable matching.

/* Phase 2 of Irving's algorithm.  `alive[i][j]` is the symmetric adjacency
 * matrix of surviving possible partners; first_of/second_of/last_of scan it. */
static int phase2(void){
    for (;;){
        int start = -1;
        for (int i = 0; i < n; i++){
            int L = len_of(i);
            if (L == 0) return 0;              /* Cor 3.2: no stable matching */
            if (L > 1 && start < 0) start = i; /* a list still undecided      */
        }
        if (start < 0) return 1;               /* Lemma 4: all singletons -> done */
 
        /* p_{i+1} = last(second(p_i)); stop when the p-sequence repeats */
        int seq[2*MAXN+4], m = 0; char seen[MAXN]; memset(seen, 0, sizeof seen);
        int p = start;
        while (!seen[p]){
            seen[p] = 1; seq[m++] = p;
            int q = second_of(p); if (q < 0) return 0;
            p = last_of(q);       if (p < 0) return 0;
        }
        int s = 0; while (seq[s] != p) s++;    /* the tail seq[0..s-1] is discarded */
        int r = m - s;                          /* the cycle is a_1..a_r            */
        int a[MAXN]; for (int i = 0; i < r; i++) a[i] = seq[s+i];
 
        /* force b_i to reject a_i, for every i in the cycle */
        int b[MAXN];
        for (int i = 0; i < r; i++){ b[i] = first_of(a[i]); if (b[i] < 0) return 0; }
        for (int i = 0; i < r; i++) del_pair(a[i], b[i]);
        /* a_i now proposes to b_{i+1}; b_{i+1} drops everyone worse than a_i */
        for (int i = 0; i < r; i++){
            int c = first_of(a[i]); if (c < 0) return 0;
            truncate_after(c, a[i]);
        }
        for (int i = 0; i < n; i++) if (len_of(i) == 0) return 0;
    }
}

Two implementation notes. First, Irving’s O(n²) bound depends on representing the reduced lists by leftmost/rightmost markers into the original preference array — he proves the total number of marker moves cannot exceed n². The implementation above instead keeps an explicit symmetric alive matrix and rescans for first/second/last, which is O(n) per lookup and therefore O(n³) overall. That was a deliberate trade: the marker version is where a first implementation goes wrong (and where mine did, segfaulting on the first run), and the output is identical. Second, the “tail” p₁ … p_{s−1} found on the way into the cycle is discarded here; Irving notes it carries extra information the algorithm does not exploit, and that remembering it across calls is what keeps seek_cycle inside the O(n²) budget.

Validation. All four instances quoted in Irving’s paper reproduce exactly, and the algorithm was then differentially tested against the brute-force oracle:

case	source	brute force	Irving	agree
size-4	Gale & Shapley’s instance, Irving §1	0 stable matchings	reports none	yes
size-8	Knuth’s instance, Irving §1 (“exactly 3 stable matchings”)	3	finds (0,3)(1,2)(4,5)(6,7), 0 blocking pairs	yes
size-6	Irving §2 worked example (paper’s answer: 1/6, 2/3, 4/5)	1	finds (0,5)(1,2)(3,4) = 1/6, 2/3, 4/5	yes
size-6	Irving §2 second example (“no solution exists”)	0	reports none	yes

and on random instances with fixed seed 20260828 + n:

n	instances	Irving agrees with brute force	instances admitting a stable matching	wall time
4	4,000	4,000 / 4,000	3,858 (96.45 %)	0.001 s
6	4,000	4,000 / 4,000	3,735 (93.38 %)	0.007 s
8	4,000	4,000 / 4,000	3,607 (90.17 %)	0.067 s
10	4,000	4,000 / 4,000	3,580 (89.50 %)	0.680 s
12	800	800 / 800	714 (89.25 %)	1.669 s

xychart-beta
    title "Fraction of random stable-roommates instances that admit a stable matching"
    x-axis "n (number of people)" [4, 6, 8, 10, 12]
    y-axis "percent solvable" 85 --> 100
    bar [96.45, 93.38, 90.17, 89.50, 89.25]
    line [96.45, 93.38, 90.17, 89.50, 89.25]

What it shows: measured solvability of uniformly random roommates instances, 4,000 instances each at n = 4, 6, 8, 10 and 800 at n = 12, fixed seed. The insight to take: non-existence is not a curiosity. Around one instance in ten already has no stable matching at n = 8, and the curve is still descending — a production system that assumes a solution exists will hit the failure path on ordinary input, not on an adversarial one.

16,800 random instances, zero disagreements. Note the third column: roughly 10 % of small random roommates instances have no stable matching at all, and the fraction is still falling slowly at n = 12. Non-existence is not a pathological corner case you can ignore; it is a routine outcome. (The wall times are dominated by the O((n-1)!! · n²) brute-force oracle, not by Irving’s algorithm — at n = 12 the oracle examines 10,395 pairings per instance.)

2. Couples break existence in hospital-residents

The second-largest deployment problem in matching, and the one that forced the 1990s NRMP redesign. When two applicants are a couple who want positions in the same city, they no longer have individual preferences over positions — they have a joint preference over pairs of positions. That single change introduces a complementarity, and complementarity destroys the argument on which deferred acceptance rests.

Roth & Peranson state the mechanism precisely (Roth & Peranson 1999):

The key to the stability of the outcome in simple markets is that (in the worker-proposing version of the algorithm) no firm ever regrets having rejected a worker’s application, since it only does so when it has an application it prefers… However, in a market containing couples, suppose that a firm f₁ receives an application from a worker w₁, and rejects an application from a less-preferred worker w′ in order to hold w₁’s application. Suppose further that w₁ is married to w₂, whose application is being held by firm f₂… Finally, suppose that firm f₂ now receives an application it prefers and rejects the application of w₂. In order for the couple c now to apply to its next-choice pair of firms, w₁ must be withdrawn from firm f₁. Thus, firm f₁ now regrets having rejected worker w′.

“No receiver ever regrets a rejection” is the monotonicity invariant that makes deferred acceptance work at all. Couples break it, and with it both the algorithm and the existence theorem. The smallest known counterexample is due to Klaus & Klijn (2005), reproduced as Example 1 in Kojima, Pathak & Roth (2013): one single doctor s, one couple c = (f, m), two hospitals with one seat each.

• couple c: only (h₁, h₂) is acceptable — both together or neither
• single s: h₁ ≻ h₂ ≻ unmatched
• h₁: f ≻ s · h₂: s ≻ m

Verified exhaustively here — enumerate every capacity-respecting, individually-rational assignment of {s, f, m} to {h₁, h₂, unmatched} and test each for a block:

  s->--  f->--  m->-- : BLOCKED  (couple c blocks with (h1,h2))
  s->--  f->h1  m->h2 : BLOCKED  (single doctor s blocks)
  s->h1  f->--  m->-- : BLOCKED  (couple c blocks with (h1,h2))
  s->h2  f->--  m->-- : BLOCKED  (single doctor s blocks)

  candidate matchings examined: 4 ; stable matchings found: 0

Four candidates, four blocks, zero stable matchings — matching the paper’s case analysis line for line. And it is worse than non-existence: Ronn (1990) showed that deciding whether a stable matching exists in a market with couples is NP-complete (cited in Kojima, Pathak & Roth). So there is no “just check first” workaround either. Klaus & Klijn (2005) identify a sufficient condition — weak responsiveness, meaning an improvement for one member of the couple is an improvement for the couple — under which existence is restored; but responsiveness “essentially excludes complementarities in couples’ preferences”, which is to say it excludes the thing couples actually want. Kojima, Pathak and Roth’s own reading of NRMP data is that couples’ stated preferences do not satisfy it, and that guaranteeing existence in such markets is “virtually impossible”.

What the NRMP does instead is discussed under Production Notes.

3. Ties, incompleteness, and the third relaxation

The classical model assumes preferences are strict and complete. Real markets supply neither. Allowing agents to declare others unacceptable (incomplete lists) is benign — stable matchings still always exist, they may leave agents unmatched, and the Rural Hospitals Theorem guarantees the same set of agents is matched in every stable matching, so no clever choice of stable matching can fill an unpopular rural programme. Allowing ties is not benign: it splits “stable” into weak, strong, and super-stability, and finding a maximum-cardinality weakly stable matching becomes NP-hard. New York City’s high-school match runs headlong into this, because schools rank applicants in coarse priority tiers rather than strictly, and the standard fix — break ties at random — is shown to be inefficient but unavoidable if you insist on strategyproofness.

Uncertain

Verify: (a) the exact NP-hardness statement for maximum-cardinality weakly stable matching with ties, and its attribution (usually Iwama, Manlove, Miyazaki & Morita 1999 / Manlove et al. 2002); (b) the precise statement and attribution of the Rural Hospitals Theorem — (b) resolved 2026-08-28, see below; (c) the Klaus & Klijn 2005 statement of weak responsiveness. Reason: these primary papers were not fetched. (a) is asserted here from secondary reports inside sources that were read — Roth & Peranson enumerates the simple-market theorems that fail with couples and cites Roth & Sotomayor (1990) for a comprehensive treatment; the NYC paper handles ties. (c) is quoted at second hand from Kojima, Pathak & Roth. To resolve: fetch Iwama et al. (ICALP 1999) and Klaus & Klijn (JET 121:75–106, 2005).

(b) is closed. Hospital-Residents and the NRMP states the theorem verbatim from Roth 2008 (IJGT, fetched in full), which attributes it to Roth 1986, Econometrica 54:425–427, with the first clause credited to McVitie & Wilson. That note also verifies the theorem computationally: 22,500 random instances, exhaustive stable-set enumeration, zero violations — including 456 instances that have both an under-subscribed hospital and more than one stable matching, which are the only cases where the theorem could have failed.

Failure Modes and Gotchas

Confusing stability with quality. A stable matching can assign everybody their last choice. Stability constrains pairs, not outcomes. The measured lattice above makes this concrete: in the KT 4×4 instance, M0 and M3 are both perfectly stable, and the proposers’ total rank differs by a factor of three between them (4 versus 12). If a stakeholder asks “is this a good match?”, “it is stable” is not an answer.

Confusing stable matching with maximum matching. See the callout at the top. The failure mode in code is subtler than the failure mode in conversation: someone reaches for a max-flow or Hopcroft–Karp library because the input “is a bipartite matching problem”, gets a perfect matching in O(E√V), and ships it. It will be perfect and it will be full of blocking pairs, because the preference data was never read. If your input has rankings, a maximum-matching algorithm is answering a different question. Cross-reference: Bipartite Matching.

Reading the blocking-pair condition as a disjunction. a prefers b and b prefers a. One-sided desire is not a block. This is the bug that makes a verifier report instability on correct output, and the debugging session that follows is miserable because the verifier is the thing you trust.

Forgetting the unmatched branch with incomplete lists. A free agent prefers any acceptable partner to being free. Omit that and your checker certifies matchings that leave an agent idle next to a programme with a vacancy that wants them — the exact configuration real clearinghouses care most about.

Assuming a unique solution. Measured above: mean stable-set size 1.50 at n = 4 and 1.93 at n = 6, but the maximum observed was 6 and 8 respectively, and Pittel shows the expected count grows like e⁻¹ n ln n. If your test suite only uses instances with a unique stable matching, it cannot detect a proposer/receiver orientation bug, because both orientations produce the same answer. Deliberately include multi-solution instances — the KT 3×3 and 4×4 above are the standard ones.

Assuming existence when the model is not two-sided. The existence theorem is about bipartite instances. Roommates: ~10 % of small random instances have no solution (measured above). Couples: non-existence, and deciding existence is NP-complete (Ronn 1990). Any system that “just runs the matching” and has no code path for no stable matching exists will one day fail in production with no diagnostic.

Assuming ties are harmless. Strict preferences are load-bearing. With ties, “stable” fractures into three inequivalent definitions and the optimisation problems become NP-hard. School districts hit this immediately because schools rank in priority tiers, not strict orders.

Believing that stability is a fairness property. It is not, in either direction. The lattice has two extremes with opposite distributional consequences, and both are stable. Choosing which one to compute is a policy decision disguised as an implementation detail — which is precisely the scandal that forced the NRMP redesign, and the subject of The Gale-Shapley Algorithm and Proposer-Optimality and Strategic Truncation.

Alternatives and When to Choose Them

you want	use	why not stable matching
the largest number of pairs, no preferences	Bipartite Matching — Hopcroft–Karp O(E√V)	stability needs rankings; without them the concept is undefined
minimum total cost over a perfect matching, cardinal costs	Hungarian Algorithm / min-cost flow	requires interpersonal comparability that ordinal rankings do not supply
a matching in a general (non-bipartite) graph, no preferences	Blossom algorithm	always exists and is polynomial; stable roommates may have no solution
minimise the sum of ranks over stable matchings (egalitarian)	polynomial in the classical model via the lattice’s rotation poset	the egalitarian matching is stable, so this is a refinement of stability, not an alternative to it
one-sided allocation — objects to agents, objects have no preferences	Top Trading Cycles	stability is a two-sided concept; TTC targets Pareto efficiency and strategyproofness instead
allocation with money in the loop	The VCG Mechanism, auctions — see Games and Strategic Systems in C MOC P4	matching is what you use when prices are ruled out (schools, organs)
strategyproofness for everyone, and you can give up stability	serial dictatorship	Roth 1982 Theorem 4 exhibits exactly this: an efficient, universally dominant-strategy-truthful procedure whose outcomes need not be stable
stability and universal strategyproofness	nothing — it does not exist	Roth 1982 Theorem 3: “No stable matching procedure for the general matching problem exists for which truthful revelation of preferences is a dominant strategy for all agents.”

That last row is the fundamental trade-off of the field, and it is worth stating as a triangle: stability, universal strategyproofness, pick one. Roth’s Theorem 4 shows the second is achievable alone (serial dictatorship, which “bears some resemblance to the football draft”); Gale–Shapley shows the first is achievable alone; Theorem 3 shows both together are impossible. Every deployed matching mechanism is a choice about where on that boundary to sit, and every one of them chose stability — because, empirically, unstable clearinghouses die.

flowchart TB
    START["you have a matching problem"] --> Q1{"do agents have<br/>rankings over<br/>the other side?"}
    Q1 -->|no| MAX["maximum matching<br/>Hopcroft-Karp / max-flow<br/>or Blossom if non-bipartite"]
    Q1 -->|yes| Q2{"are both sides<br/>strategic agents<br/>with preferences?"}
    Q2 -->|"no, one side is<br/>passive objects"| TTC["Top Trading Cycles<br/>Pareto efficient + strategyproof"]
    Q2 -->|yes| Q3{"is the instance<br/>two-sided?"}
    Q3 -->|"no, one pool"| ROOM["stable roommates<br/>Irving 1985 O(n squared)<br/>MAY HAVE NO SOLUTION"]
    Q3 -->|yes| Q4{"complementarities?<br/>couples, joint quotas"}
    Q4 -->|yes| HARD["existence not guaranteed<br/>deciding it is NP-complete<br/>use a heuristic + fallback"]
    Q4 -->|no| Q5{"are preferences<br/>strict?"}
    Q5 -->|"no, ties"| TIES["weak / strong / super stability<br/>optimisation becomes NP-hard<br/>break ties, then run DA"]
    Q5 -->|yes| DA["deferred acceptance<br/>O(n squared), always succeeds<br/>choose which side proposes"]

What it shows: the decision procedure from “I have things to pair up” to an algorithm. The insight to take: the two questions that actually matter are are there preferences (which separates this note from Bipartite Matching) and is the instance two-sided (which separates guaranteed existence from possible non-existence). Everything below those two nodes is a matter of degree; those two are matters of kind.

Production Notes

The National Resident Matching Program. The canonical deployment, running since 1952, matching roughly 20,000–25,000 new physicians to residency programmes annually in the years Roth studied (Roth & Peranson 1999 report 20,071 positions filled in 1987 rising to 24,749 in 1996). It exists because the decentralised market failed: competition for scarce students drove offers earlier and earlier until contracts were being signed roughly two years before graduation, on students who did not yet know what branch of medicine they wanted (Roth 1984; Roth, JAMA 2003). The NRMP’s own current description of its algorithm is applicant-proposing deferred acceptance in plain English — “the matching algorithm is ‘applicant-proposing’… Applicant B is ‘bumped’ from the tentative match with the program to make room for Applicant A… When all applicants’ rank order lists have been considered, the matching algorithm is complete and all tentative matches become final” (nrmp.org, retrieved 2026-08-28). “Tentative” is the word doing the work; that is deferred acceptance.

Core convergence: the stable set is tiny in practice. This is the most operationally important empirical finding in the field, and it directly contradicts what the random-instance measurements above would lead you to expect. Roth and Peranson ran the original NRMP algorithm and an applicant-proposing algorithm on five years of real data and counted how many applicants received a different match:

year	positions filled	applicants receiving a different match	preferred the applicant-proposing result	preferred the incumbent result
1987	20,071	20	12	8
1993	20,916	16	16	0
1994	22,353	20	11	9
1995	22,937	14	14	0
1996	24,749	21	12	9

Roughly one applicant in a thousand is affected by the choice of orientation. Their explanation is that the set of stable matchings collapses when preference lists are short: “the high transaction costs involved in interviewing place a practical limit on how many interviews are conducted, and one consequence of this is that the set of stable outcomes is very small, and there are very few opportunities for participants to engage in strategic manipulation… (Neither of these would be the case in the absence of transaction costs.)” That parenthesis is the key to reconciling this table with the lattice measurements above — those used complete preference lists over all n partners, which is exactly the no-transaction-cost regime Roth and Peranson say is unrealistic.

The politics of which side proposes. The NRMP algorithm was programme-proposing, and in the mid-1990s the market suffered “a crisis of confidence concerning whether the matching algorithm was unreasonably favorable to employers at the expense of applicants”. The American Medical Student Association together with Ralph Nader’s Public Citizen Health Research Group, and the AMA Medical Student Section, formally advocated that the algorithm be changed (Roth & Peranson 1999 §I). The NRMP Board commissioned a redesign in the autumn of 1995; the Board decided to adopt the new applicant-proposing algorithm in May 1997, and the first match run with it completed in March 1998. (Secondary accounts disagree about the year: the Nobel committee’s popular background says “adopted by the NRMP in 1997”, Kleinberg & Tardos’s slides say “algorithm overhauled in 1998”. Both are half right — decision 1997, first live match 1998, per the primary source.) The irony the table above records: the redesign was politically necessary and mathematically almost inconsequential, changing about 20 applicants’ matches. What it did change was the direction of the residual strategic incentive, which is the subject of The Gale-Shapley Algorithm.

timeline
    title The NRMP, from market failure to redesign
    1940s : hospitals compete for scarce students : offers pushed ~2 years before graduation : students commit before knowing their specialty
    1952 : centralised clearinghouse introduced : programme-proposing, the Boston Pool algorithm
    1962 : Gale and Shapley publish deferred acceptance : nobody connects it to the medical market for two decades
    1982 : Roth proves no stable mechanism is strategyproof for both sides : and that proposer-side truth-telling is dominant
    1984 : Roth shows the NRMP algorithm is essentially deferred acceptance : and that stability explains its survival
    1995 : crisis of confidence : student groups and Public Citizen demand a redesign : NRMP Board commissions a new algorithm
    1997 : NRMP Board votes in May to adopt the applicant-proposing algorithm
    1998 : first live match on the new algorithm completes in March
    2003 : NYC high-school match redesigned on the same basis
    2012 : Nobel Prize in Economic Sciences to Shapley and Roth

What it shows: the fifty-year gap between the theorem and its deployment, and the fact that the redesign was driven by a political crisis rather than by a mathematical discovery. The insight to take: the decision year (1997) and the first-live-match year (1998) are different, which is why secondary sources disagree about “when the NRMP changed” — both dates are in the primary paper.

Couples in the live system. Roth & Peranson report that 6–8 % of applicants participate as couples, and 8–12 % submit some form of the match variations the algorithm has to accommodate. Because stability is not guaranteed with couples, the deployed algorithm is a heuristic that can loop; the paper’s sequencing experiments found that “the number of loops encountered was fewest when couples were introduced to the match after single applicants”, and that introducing couples last “reduces the numbers of loops… without changing the prospects of couples or single applicants”. That is engineering, not theory — the theory says the problem is NP-complete.

School choice. New York City’s high-school match, ~90,000 eighth-graders against ~500 programmes, was redesigned in 2003 on an applicant-proposing deferred-acceptance basis. Under the old three-round system, students could rank only five schools and about 30,000 a year ended up assigned administratively to schools they had not listed; the redesign cut that by roughly 90 % (Nobel popular background). The residual problem there is ties: schools rank in priority tiers, and Abdulkadiroğlu, Pathak & Roth (2009) show that no mechanism can be both strategyproof for students and dominate deferred-acceptance-with-random-tiebreaking in efficiency — measuring that, in their NYC simulations, only about 1.9 % of eighth-graders could be matched to schools they prefer under an efficiency-improving alternative.

Beyond hospitals and schools. Kleinberg and Tardos close their chapter with a systems application worth noting in this vault: content delivery networks assigning “billions of users to servers, every 10 seconds”, where users have preferences based on latency and packet loss and servers have preferences based on bandwidth and co-location cost — citing Maggs & Sitaraman’s Akamai retrospective. The matching frame is not confined to markets with human participants; it applies wherever two populations must be paired and each side has an ordering. Compare Multi-Tenancy and Fairness in LLM Serving and Stock Exchange Order Matching System Design, both of which are mechanisms in this sense and neither of which is described as one in its own note.

See Also

• The Gale-Shapley Algorithm — deferred acceptance: how the existence theorem is proved constructively, the O(n²) bound, proposer-optimality measured, and strategyproofness
• Bipartite Matching — the adjacent, different problem: maximum matching optimises a global count and ignores preferences; read the comparison table at the top of this note before assuming the two are related
• Proposer-Optimality and Strategic Truncation — the distributional consequence of the lattice, and how a receiver manipulates
• Hospital-Residents and the NRMP — the many-to-one generalisation and the real deployment
• Top Trading Cycles — the one-sided allocation problem, where stability is not the right concept
• Nash Equilibrium — the non-cooperative solution concept; stability is the cooperative one (the core), and the contrast between constructive and fixed-point existence proofs is the spine of the parent MOC
• Best Response and the Equilibrium Condition — a blocking pair is a joint profitable deviation, which is exactly what a best-response condition does not rule out
• Dominant Strategies and Iterated Elimination — the solution concept behind “truth-telling is dominant for proposers”
• Common Knowledge and Rationality Assumptions — stability presumes agents can identify and act on a mutually profitable defection; what that presumes about information
• Games and Strategic Systems in C MOC — parent map; this note and its sibling are the P5 rung