Hospital-Residents and the NRMP

The hospital-residents problem (HR) is Stable Matching with one side allowed to take more than one partner: each hospital h publishes a quota q(h) — the number of residency positions it wants to fill — and the matching assigns each doctor to at most one hospital and each hospital at most q(h) doctors. Deferred acceptance generalizes to it almost unchanged, so stable matchings always exist. What is not obvious, and is the intellectual centre of this note, is the Rural Hospitals Theorem (Roth 1986): across every stable matching of a given instance, the set of doctors who are employed is identical, and the number of positions each hospital fills is identical (Roth 2008, Theorem 13). A rural programme that goes half-empty under one stable matching goes half-empty under all of them — and it gets exactly the same doctors every time. No clever choice of stable outcome can help it. Around that theorem sits the best-documented market design in existence: the National Resident Matching Program (NRMP), which has cleared the American physician labour market since the early 1950s, was discovered in 1984 to have been running hospital-proposing deferred acceptance for three decades without anyone realizing it, and was redesigned in the 1990s to run applicant-proposing instead — a redesign whose hardest problem, couples, is not solved by a theorem but by a heuristic that could in principle fail.

What this note assumes and what it does not repeat

The one-to-one theory — the definition of a blocking pair, why stability is the right criterion, the lattice of stable matchings, the stable-roommates non-existence result, and the couples counterexample verified exhaustively — lives in Stable Matching. The algorithm itself, its O(n²) bound, proposer-optimality and its strategyproofness are in The Gale-Shapley Algorithm and Proposer-Optimality and Strategic Truncation. This note extends those to quotas, states and demonstrates the Rural Hospitals Theorem, and tells the deployment history, which is where the real content is.

---

Mental Model — a hospital is a stack of one-slot employers, until it isn’t

The cleanest way to think about HR is to notice that a hospital with quota q behaves almost like q separate one-position employers who happen to share a ranking of doctors. “Almost” is doing real work: the hospital’s preference over sets of doctors is what economists call responsive — swapping any assigned doctor for a better unassigned one improves the set, and filling an empty slot with an acceptable doctor improves the set — and responsiveness is exactly the assumption under which the one-to-one theory survives the generalization. When a hospital’s preferences are not responsive (it wants two cardiologists or none; it wants gender balance; it wants a couple together), the theory falls over. Couples are precisely that failure, and they are the last section of this note.

flowchart LR
    subgraph D["Doctors (one position each)"]
        r0["r0"]; r1["r1"]; r2["r2"]; r3["r3"]; r4["r4"]
    end
    subgraph H["Hospitals (quota q)"]
        h0["h0 — City General<br/>q = 2"]
        h1["h1 — Metro Teaching<br/>q = 2"]
        h2["h2 — Rural Regional<br/>q = 2"]
    end
    r0 --> h0; r2 --> h0
    r1 --> h1; r3 --> h1
    r4 --> h2
    h2 -.->|"one slot stays<br/>empty in EVERY<br/>stable matching"| h2

What it shows: the shape of a hospital-residents instance — a many-to-one matching where the “many” side is capped by a quota. The insight to take: the dotted self-loop is the whole point of the note. h2’s vacancy is not an artefact of which stable matching the clearinghouse happened to compute; it is a property of the instance. Every stable matching leaves h2 at 1 of 2, and every stable matching fills that one slot with the same doctor.

Why the quota generalization is nearly free

Formally, an HR instance is (R, H, q, ≻) where R is a set of residents, H a set of hospitals, q : H → ℕ the quotas, and ≻ a profile of strict preference orders — each resident r ranks a subset of hospitals (the ones it finds acceptable), each hospital h ranks a subset of residents. Lists are allowed to be incomplete: an agent that ranks nobody is simply never matched, and an agent that omits you would rather go unmatched than take you. A matching M assigns each resident to at most one acceptable hospital and each hospital h at most q(h) acceptable residents.

A pair (r, h) blocks M when both would defect to each other:

• r finds h acceptable and either is unmatched or strictly prefers h to M(r); and
• h finds r acceptable and either has a free slot (|M(h)| < q(h)) or strictly prefers r to the worst resident currently in M(h).

M is stable if it is individually rational (nobody is assigned an unacceptable partner) and admits no blocking pair. The second bullet is the only place quotas enter, and they enter in the mildest possible way: the hospital’s “current partner” in the one-to-one test is replaced by its worst current partner, plus a free-slot escape hatch. Everything downstream — existence, the lattice, the optimality results — survives.

---

The Algorithm, in Real C

Deferred acceptance for HR is the one-to-one algorithm with the hospital’s holding rule widened. In the resident-proposing direction: every unassigned resident proposes to the best hospital it has not yet been rejected by; a hospital holds any proposal while it has a free slot, and otherwise holds it only by bumping its worst current holder. Bumped residents go back into the pool. The program written for this note (hr.c, ~250 lines, built with gcc -O2 -Wall -Wextra) is not committed to the vault; the two load-bearing routines are reproduced in full here, and every number reported below came from running it.

/* r strictly prefers a to b; UNMATCHED is worst. Unacceptable counts as unmatched. */
static int r_prefers(const HR *I, int r, int a, int b)
{
    int ra = (a == UNMATCHED) ? -1 : I->rrank[r][a];
    int rb = (b == UNMATCHED) ? -1 : I->rrank[r][b];
    if (ra < 0) return 0;            /* a not acceptable: never an improvement */
    if (rb < 0) return 1;            /* b unacceptable/unmatched, a acceptable  */
    return ra < rb;                  /* lower index = better */
}

Line by line: rrank[r][h] is the position of h on r’s list, or -1 if r never ranked it. The two guard clauses encode incompleteness properly — a hospital you did not rank is worse than unemployment, not merely low-ranked, which is the single most common bug when moving from complete to incomplete lists. Getting this predicate wrong silently produces matchings that look stable to a buggy checker and are not.

static void da_resident(const HR *I, int *M)
{
    int next[MAXR];                       /* next index on r's list to try */
    int stack[MAXR], top = 0;
    for (int r = 0; r < I->nr; r++) { M[r] = UNMATCHED; next[r] = 0; stack[top++] = r; }
 
    while (top > 0) {
        int r = stack[--top];
        while (next[r] < I->rlen[r]) {
            int h = I->rpref[r][next[r]++];
            if (I->hrank[h][r] < 0) continue;              /* h does not rank r */
            int load = 0, worst = -1, worst_r = -1;
            for (int s = 0; s < I->nr; s++)
                if (M[s] == h) { load++;
                    if (I->hrank[h][s] > worst) { worst = I->hrank[h][s]; worst_r = s; } }
            if (load < I->quota[h]) { M[r] = h; break; }   /* vacancy: hold */
            if (I->hrank[h][r] < worst) {                  /* bump the worst holder */
                M[worst_r] = UNMATCHED; stack[top++] = worst_r;
                M[r] = h; break;
            }
            /* else rejected outright; loop to r's next choice */
        }
    }
}

The stack holds residents who currently have no position. next[r] is a monotone cursor: a resident never revisits a hospital that has rejected it, which is what bounds the whole run at the total length of all rank order lists — O(Σ|list|), i.e. O(nm) for complete lists, exactly as in the one-to-one case (Kleinberg & Tardos ch. 1). The inner for recomputes the hospital’s load and worst holder by scanning; that is O(n) per proposal and deliberately naive — a production implementation keeps a per-hospital heap, but the naive version is the one you can read and check against the brute-force oracle, and at the sizes used here it costs nothing.

flowchart TB
    S["Candidate pair (r, h)"]
    A{"Does r find h acceptable?"}
    B{"Is r unmatched, or does r<br/>strictly prefer h to M(r)?"}
    C{"Does h find r acceptable?"}
    D{"Does h have a free slot?<br/>|M(h)| &lt; q(h)"}
    E{"Does h prefer r to the<br/>WORST resident in M(h)?"}
    NO["not a blocking pair"]
    YES["BLOCKING PAIR<br/>the matching is unstable"]

    S --> A
    A -->|no| NO
    A -->|yes| B
    B -->|no| NO
    B -->|yes| C
    C -->|no| NO
    C -->|yes| D
    D -->|yes| YES
    D -->|no| E
    E -->|yes| YES
    E -->|no| NO

What it shows: the exact decision procedure count_blocking runs for every acceptable (r, h) pair — the stability test, drawn. The insight to take: only the two boxes on the right differ from the one-to-one case. Quotas enter as a free-slot escape hatch and a comparison against the hospital’s worst current holder rather than its only one. Everything else — including the two “is it acceptable?” gates that make incomplete lists work — is unchanged from Stable Matching.

The hospital-proposing direction is the mirror image and is what the NRMP actually ran from 1951 until 1998. Both directions were implemented, and both are checked by an independent count_blocking routine that scans every acceptable pair — never by trusting the algorithm that produced the matching.

---

The Rural Hospitals Theorem

Here is the statement, quoted from Roth’s own retrospective (Roth 2008, Theorem 13, attributing it to Roth 1986, Econometrica 54:425–427):

Theorem 13: (Rural Hospital Theorem, Roth 1986): When all preferences over individuals are strict, and hospitals have responsive preferences, the set of students employed and positions filled is the same at every stable matching. Furthermore, any hospital that has some empty positions at some stable matching is assigned precisely the same set of students at every stable matching.

Three separate invariants are packed into two sentences, and they get progressively stronger:

1. The set of matched doctors is identical across all stable matchings. If you are unemployed at one stable matching, you are unemployed at all of them. (For the one-to-one marriage model this part is due to McVitie and Wilson; Roth notes his first sentence is “a straightforward generalization” of it.)
2. The number of positions each hospital fills is identical across all stable matchings. A hospital’s headcount is an invariant of the instance, even though which doctors it gets is not.
3. An under-subscribed hospital gets the identical roster. This part, Roth points out, “has no parallel when matching is one-to-one” — it only says anything when a hospital has more than one slot and leaves at least one empty.

Why this is the answer to a policy question, and why the answer is “no”

Roth is explicit about where the theorem came from. Rural residency programmes chronically failed to fill, and disproportionately filled with graduates of foreign medical schools; when the NRMP was being redesigned in the 1990s, the natural question was whether the new algorithm could be tuned to help them. The theorem answers that question in the negative, and it does so in the strongest possible way. From the paper:

These often cannot fill all their residency positions… the question was, when a new match algorithm is being written, can it relieve the plight of these hospitals? Given that the empirical evidence supported the view that stability is an important component of match success, the following theorem answers that question in the negative.

The logic chain matters: if you insist the outcome be stable — and the empirical evidence from the British regional markets is that unstable clearinghouses get abandoned — then the rural hospital’s fill rate is not a design variable at all. It is determined by the submitted preferences. The only levers left are outside the algorithm: change the preferences (loan forgiveness, salary, visa sponsorship), change the quotas, or run a separate rural-priority match that is not stable and accept the consequences.

The intuition, and a proof sketch

The invariance follows from a counting argument on top of the one-to-one machinery. In the one-to-one model the deferred-acceptance lattice has an “opposite interests” property: moving from one stable matching to another, every doctor who changes moves along their preference order in one direction and every hospital in the other. The rural theorem sharpens this into a conservation law.

flowchart TB
    A["Stable matching M<br/>doctor d is unmatched"] --> B{"Suppose some other<br/>stable matching M′<br/>employs d"}
    B --> C["d works at hospital h in M′<br/>so h finds d acceptable"]
    C --> D["In M, h must have filled<br/>every slot with doctors<br/>it prefers to d"]
    D --> E["Those doctors are employed in M.<br/>Repeat the argument at their<br/>M′ assignments…"]
    E --> F["…every hospital in the chain is<br/>FULL in M with strictly better doctors,<br/>so total positions filled in M<br/>exceeds total filled in M′"]
    F --> G["Symmetric argument gives<br/>the reverse inequality"]
    G --> H["Contradiction: both totals equal<br/>⇒ the matched set is invariant"]

What it shows: the shape of the standard proof of the first two clauses of the Rural Hospitals Theorem — a two-sided counting argument that pins the total number of filled positions from both directions at once. The insight to take: stability does not merely constrain the outcome, it conserves a quantity. Once you know the total is conserved and the per-agent comparisons all point the same way, per-hospital headcount has nowhere to move.

Uncertain

Verify: the exact structure of Roth’s 1986 proof, and whether the argument sketched above matches it. Reason: no copy of the primary paper could be retrieved — not a copy that failed to yield text, but no PDF at all. Roth 1986, Econometrica 54(2):425–427 is a three-page Notes-and-Comments piece behind JSTOR (jstor.org/stable/1913160). It does not appear on Roth’s own paper index, and twelve candidate URLs were tried — two filename guesses under web.stanford.edu/~alroth/, the JSTOR PDF endpoint, and nine course-page mirrors (dklevine.com, econweb.ucsd.edu, public.websites.umich.edu, faculty.wcas.northwestern.edu, and others). Every one returned HTML: HTTP 404, HTTP 403, or a JavaScript “Session Verification” interstitial. This is a retrieval failure, not an extraction failure, so the render-and-read route (pdftoppm -png -r 120 … on an image-only scan, which recovers text pdftotext cannot) does not apply — there is no PDF to rasterize. A future attempt should re-check whether a scan has appeared before spending time on rendering. The theorem statement quoted above is verbatim from a primary source that was read (Roth 2008, Roth’s own restatement), and the conclusions are verified against the exhaustive computation below. The proof sketch is reconstructed, not quoted, and should be treated as an aid to intuition rather than a citation. To resolve: obtain Roth (1986) or Roth & Sotomayor (1990), Two-Sided Matching, ch. 5.

The one-to-one ancestor, with a proof that can be read

The 1986 paper is unreachable, but its predecessor is not, and it carries a full proof of the first clause plus an explicit statement of what the many-to-one version means for the NRMP. David Gale and Marilda Sotomayor’s Ms. Machiavelli and the Stable Matching Problem (American Mathematical Monthly 92(4), April 1985, pp. 261–268; read 2026-08-29 by rendering the page-image scan, which has no text layer) devotes its §3 to two preliminary propositions, and calls the first one “rather surprising.”

Their convention is that an unmatched person is self-matched — a matching μ is a bijection of M ∪ W onto itself of order 2, so μ(x) = x encodes “unmatched” without a special case. With that:

Proposition 1. If μ and μ' are stable matchings for (M, W), then the people who are self-matched are the same for both.

That is exactly clause 1 of the Rural Hospitals Theorem, in the one-to-one model, four decades before the note you are reading. The proof rests on a decomposition lemma that is worth seeing because it is where the “conservation” intuition sketched above becomes a real argument:

Lemma 1. Suppose W ⊂ W' and μ is a stable matching for (M, W; P) and μ' for (M, W'; P') where P' agrees with P on W. Let M_μ be all men who prefer μ to μ' and let W_{μ'} be all women who prefer μ' to μ. Then μ and μ' are bijections between M_μ and W_{μ'}.

The mechanism, in one sentence: take a man m who strictly prefers μ, so w = μ(m) ≠ m; then w ≠ μ'(m), and w must prefer μ'(w) to m, for otherwise (m, w) would block μ' — hence w ∈ W_{μ'}. The symmetric argument gives the reverse inclusion, and since both sets are finite and both maps injective, they are bijections. The pairing is what does the work. Every man who gains has a distinct woman who loses, and vice versa, so the two “gainer” sets have the same cardinality — which is why nothing can be created or destroyed as you move around the stable set.

Gale and Sotomayor then draw the NRMP consequence themselves, in prose, and the wording repays close reading because it is more careful than most restatements:

This is particularly striking in the context of the student-hospital situation. Suppose NRMP were to change its policy and impose the student rather than hospital-optimal matching. Of course this would make all the students at least as well off, but those students who were not accepted by any hospital would still not be accepted and, on the other hand, each hospital would end up admitting the same number of students, though in general not the same set, under the student-optimal as under the hospital-optimal scheme.

“Same number, in general not the same set” is clause 2 exactly, and the hedge is the reason clause 3 is a separate sentence in Roth’s theorem: an under-subscribed hospital does get the same set, but a full one need not. Getting this backwards — claiming every hospital gets the same doctors — is the most common misstatement of the Rural Hospitals Theorem, and Gale and Sotomayor’s parenthesis is the cleanest place to see why it is wrong.

One further sentence from the same page dates the manipulation question and shows it was live before the redesign debate: “In particular, Roth has recently shown by an example that even when the college optimal matching is used, as in the case of NRMP, it may still be possible for a college to get a better class by appropriate misrepresentation of preferences.” Colleges — the proposing side under the old algorithm — could still gain, because a college is not a single agent with a single slot; that is the Proposer-Optimality and Strategic Truncation guarantee failing at the many-to-one boundary, and it is formalised as Roth’s Theorem 11, stated next.

The impossibility that frames all of this

Every strategic claim in this note sits under one negative result, and it is worth stating in the author’s own words rather than paraphrasing. From Alvin Roth, The Economics of Matching: Stability and Incentives, Mathematics of Operations Research 7(4), November 1982, pp. 617–628 (read 2026-08-29):

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.

The abstract states the pair of results the paper is built around: “no matching procedure exists which always yields a stable outcome and gives players the incentive to reveal their true preferences, even though procedures exist which accomplish either of these goals separately,” and “matching procedures do exist, however, which always yield a stable outcome and which always give all the agents in one of the two disjoint sets of agents the incentive to reveal their true preferences.” Stability and two-sided strategyproofness are incompatible; stability and one-sided strategyproofness are not. That is the whole design space, and the 1990s NRMP redesign was a choice of which side to put on the safe half of it.

Roth’s proof needs only three men and three women, a preference profile with exactly two stable outcomes x (which the men prefer) and y (which the women prefer), and the observation that any stable matching procedure h must return one of them — after which whichever side lost can restate its preferences so that its favourite becomes the unique stable outcome, forcing h’s hand. Roth’s 2008 restatement of the same theorem uses a two-by-two version and adds the sharper corollary: “anyone who doesn’t end up matched to who they would be matched to at his or her optimal stable matching can potentially manipulate a stable mechanism in this way.”

The many-to-one refinements matter more for this note than the marriage-model version, and Roth 2008 states them in sequence:

Theorem (Roth 2008 numbering)	Statement	Consequence for the NRMP
6 (Roth 1982a)	“No stable matching mechanism exists for which stating the true preferences is a dominant strategy for every agent.”	Two-sided strategyproofness is off the table before any design work starts
8 (Dubins & Freedman 1981; Roth 1982)	“In the game induced by the man-proposing deferred acceptance algorithm … it is a weakly dominant strategy for each man to state his true preferences.”	Whichever side proposes is safe — in the marriage model
11 (Roth 1985)	“No stable matching mechanism exists which makes it a dominant strategy for all colleges to state their true preferences, although the student-proposing deferred acceptance algorithm makes it a dominant strategy for all students to state their true preferences.”	Applicant-proposing protects applicants fully; it cannot protect programmes, because a programme has several slots
12 (Sönmez 1997)	“No stable matching mechanism makes it a dominant strategy for a college to always reveal its capacity.”	Programmes can manipulate by withholding positions, not only by mis-ranking — which is why Roth and Peranson run quota-reduction experiments as well as truncation experiments

Theorem 11 is the exact reason the programmes’ bound in Table 5 below cannot be driven to zero the way the applicants’ bound in Table 4 nearly is. Applicant-proposing deferred acceptance makes truth-telling weakly dominant for applicants; nothing makes it dominant for programmes, and the residual incentive has to land somewhere.

Uncertain

Verify: nothing in the theorem statements above — but record the near-miss. The web.stanford.edu scan of Roth (1982) carries a degraded OCR text layer, and pdftotext renders Theorem 3 as “No stable matching procedure for the general matching problem exists [for] which truthful revelation is a dominant strategy for every agent” — silently dropping “of preferences” and turning “for all agents” into “for every agent”. The wording quoted above is transcribed from the page image (pdftoppm -png -r 150, page 622), not from the text layer. Nothing of substance changed here, but a text layer that reads fluently is not evidence that it is complete: when a scanned source appears to say something slightly odd, render the page before quoting it. Roth 1985 (JET 36:277–288) and Sönmez 1997 were not fetched; Theorems 10–12 are quoted from Roth’s own 2008 restatement, which is a primary source for the statements but not for their proofs.

Measured, not asserted

Assertion is cheap; the theorem is surprising enough to be worth checking. The program enumerates every feasible individually-rational assignment of residents to hospitals-or-unemployment — (m+1)ⁿ candidates — tests each with the independent blocking-pair scanner, and compares the survivors.

On a five-doctor, three-hospital instance with quotas 2/2/2, where h2 (“Rural Regional”) is ranked last by every doctor who ranks it:

=== worked instance: 5 residents, 3 hospitals, quotas 2/2/2 ===
resident-proposing DA : r0:h0  r1:h1  r2:h0  r3:h1  r4:h2  | fill: h0=2/2 h1=2/2 h2=1/2
   blocking pairs: 0
hospital-proposing DA : r0:h0  r1:h1  r2:h1  r3:h0  r4:h2  | fill: h0=2/2 h1=2/2 h2=1/2
   blocking pairs: 0

all stable matchings found by exhaustive search over 4^5 candidates:
  [0] r0:h0  r1:h1  r2:h1  r3:h0  r4:h2  | fill: h0=2/2 h1=2/2 h2=1/2
  [1] r0:h0  r1:h1  r2:h0  r3:h1  r4:h2  | fill: h0=2/2 h1=2/2 h2=1/2
  stable matchings: 2
  Rural Hospitals Theorem holds on this instance: YES
  a matching that DOES fill h2 to 2/2: r0:h2  r1:h2  r2:h1  r3:h0  r4:h0  | fill: h0=2/2 h1=1/2 h2=2/2
     ...but it has 6 blocking pair(s); e.g. (r0,h0)
  rural hospital h2: best fill over ALL feasible matchings   = 2/2
  rural hospital h2: best fill over STABLE matchings         = 1/2

Read that output carefully, because the last four lines are the theorem’s whole bite in one instance:

• There are two stable matchings here, so the choice is genuinely non-trivial — r2 and r3 swap hospitals between them, and the two extreme matchings are exactly what resident-proposing and hospital-proposing DA return.
• Both of them fill h2 at 1 of 2, and both fill it with the same doctor (r4). The invariance is not a coincidence of which algorithm ran.
• A matching that fills h2 completely does exist — the program found one and printed it. It is simply not stable: it carries six blocking pairs, the first being (r0, h0), because r0 was shoved into the rural hospital while h0, which ranks r0 second, had room. That matching would not survive contact with a real market; r0 would ring h0 directly.

So: the rural hospital’s vacancy is not caused by the algorithm, and cannot be cured by the algorithm. It is caused by the preferences.

Scaling that to a sweep over 22,500 pseudo-random instances (4–6 residents, 2–4 hospitals, quotas drawn from {1, 2}, incomplete lists, fixed xorshift seed so the run reproduces):

Metric	Value
Instances tested	22,500
Instances with 0 stable matchings	0 (existence, as guaranteed)
Instances with >1 stable matching	3,091 (13.7%)
Mean size of the stable set	1.159 (max observed: 5)
Instances with an under-subscribed hospital	6,322
…of which the stable set has size > 1	456 (the non-trivial cases)
Rural Hospitals Theorem violations	0

The row that matters is the second-to-last. In 456 instances there was both a hospital with an empty slot and more than one stable matching to choose between — the only situation in which the theorem makes a falsifiable claim — and in every one of them the matched set, the per-hospital headcount, and the under-subscribed hospital’s roster were identical across the whole stable set. The distribution of stable-set sizes is also worth noticing on its own: 1:19409 2:2662 3:380 4:47 5:2. 86% of random small instances have a unique stable matching. That number is a small-scale echo of the “core convergence” result that Roth and Peranson found in the real NRMP data, and it is the reason the 1990s redesign changed so few people’s outcomes.

---

The History — which is where the value is

The NRMP is the best-documented market design in existence, largely because Roth kept writing it down. The timeline below is assembled from Roth’s JAMA 2003 history, his 1984 JPE case study, and the Roth & Peranson 1999 AER redesign paper.

timeline
    title The American resident match, 1900s-1998
    1900s-1920s : Decentralized hiring, offers creep earlier every year
    1927 : Columbia dean asks hospitals to defer offers to April : That hope was in vain
    1930s-1940s : Appointments made up to two years before graduation : Inquiries arrive from sophomores
    1945 : Cooperative Plan fixes a uniform date : Offers stay open ten days
    1949 : Exploding offers : a twelve-hour deadline is rejected as too long
    1950 : Mullin-Stalnaker priority algorithm proposed : Not deferred acceptance, and students object
    1951 : Students force the Boston Pool Modification : Trial run, and this IS hospital-proposing DA
    1952 : First binding centralized match, for 1952 internships
    1962 : Gale and Shapley publish deferred acceptance : Unaware the NRMP has run it for a decade
    1984 : Roth identifies the NRMP algorithm as hospital-proposing DA
    1995 : Crisis of confidence : Student groups demand redesign, NRMP Board commissions one
    May 1997 : NRMP Board votes to adopt the applicant-proposing Roth-Peranson algorithm
    March 1998 : First live match run on the new algorithm

What it shows: the two failure modes that centralized matching was invented to cure (unraveling of dates, then exploding offers), followed by the two design decisions that made it last (the 1951 switch to a deferred-acceptance rule, the 1997/98 switch of the proposing side). The insight to take: the algorithm was correct before the theory existed, and it was made correct by student lobbying rather than by mathematics.

Unraveling and exploding offers: the disease

The chief symptom of the early market was that hospitals hired earlier and earlier. In 1927 the dean of Columbia’s College of Physicians and Surgeons wrote round asking hospitals to defer appointments to April; Roth’s dry verdict is “That hope was in vain.” By 1945 Joseph Turner could write that selection “has now been advanced on the school calendar to the beginning of the junior year and, indeed, inquiries now come to me even from sophomores.”

The 1945 “Cooperative Plan” fixed a uniform date and thereby converted one pathology into another. With dates pinned, competition moved to deadlines. Offers that were to remain open for ten days in 1945 had, by 1949, shrunk so far that a twelve-hour deadline was rejected as too long. Roth quotes F. J. Mullin’s catalogue of the resulting chaos: telegrams that could not be released simultaneously, hospitals telephoning students for decisions on the spot, and — the line that best captures why this is a market failure and not merely rudeness —

Students sometimes get panicky and accept poor internships way down on their lists because they have not heard from a higher position on their order of preference.

This is the general disease of decentralized entry-level markets, and Roth and Xing later catalogued it across law clerkships, gastroenterology fellowships, and college football bowls. The clearinghouse is the cure, and the point of the cure is exactly that deferral replaces commitment: a student can hold a good offer without foreclosing a better one.

The 1951 accident: students invent deferred acceptance

The most under-appreciated fact in this history is that the algorithm originally proposed for the match was not deferred acceptance and was not stable, and that it was replaced because medical students objected.

Mullin and Stalnaker’s 1951 design was a priority-matching algorithm. Students ranked hospitals; hospitals ranked students in groups (“1” for the top group up to the number of positions, “2” for the next, and so on). The algorithm then matched in a fixed order of rank-pairs: all 1-1 pairs first, then 2-1, then 1-2, then 2-2, 3-1, 3-2, 1-3, 2-3, and so forth. Putting 2-1 before 1-2 was a deliberate concession to students — their first choices were meant to be considered before hospitals’ first choices.

It backfired, and the failure mode is beautifully specific. Consider a student who ranks a reach hospital first and does not get it, but whose second choice ranks him in its first group. By the time the algorithm reaches 1-2 pairs, that second-choice hospital may already have filled every position in the 1-1 and 2-1 rounds. The student is out — punished for the mere act of having listed an ambitious first choice. Roth quotes Mullin and Stalnaker’s own admission of the “student fear of being penalized for taking a ‘flyer’.”

W. Hardy Hendren, then a Harvard medical student, organized the National Student Internship Committee, which proposed a different rule. The Boston Pool Modification updated rank order lists as it went: a student was tentatively matched to a hospital that currently ranked him in its top group, and was deleted from a hospital’s list only once he was tentatively matched somewhere he preferred — at which point lower-ranked students moved up into that hospital’s top group. Roth’s identification is flat:

This Boston Pool algorithm is equivalent to a “deferred acceptance” algorithm, which can be interpreted as one in which hospitals make offers to applicants, starting at the top of each hospital’s rank-order list, and each applicant holds on to the best offer he or she has received so far but can later reject it if a better offer is forthcoming.

That is Gale–Shapley, hospital-proposing, eleven years before Gale and Shapley published it. Roth’s counterfactual is worth stating plainly: “had the originally proposed match algorithm not been replaced, we would not now be looking back on 50 years of operation of the NRMP.” The natural experiment supporting that claim is the British one. When the UK’s regional markets for house officers unraveled in the 1960s, each National Health Service region built its own clearinghouse; several used priority-matching rules essentially like Mullin and Stalnaker’s. Those failed and were abandoned; the ones producing stable outcomes survived (Nobel background 2012, summarizing Roth 1990, 1991).

1984: Roth reads the manual

Roth’s 1984 Journal of Political Economy paper is the moment the deployed system and the theory were connected. He read the NRMP’s published procedure and identified it as hospital-proposing deferred acceptance — with two immediate corollaries that had been invisible to the market for thirty years. First, the outcome is hospital-optimal: of all stable matchings, it is the one every hospital weakly most prefers and every applicant weakly least prefers. Second, applicants therefore have something to gain by misreporting, while hospitals do not (see Proposer-Optimality and Strategic Truncation). The Nobel committee’s summary is accurate: “The NRMP — where the hospitals offered positions to students — was also criticized for systematically favoring hospitals over students. Indeed, as Gale and Shapley had shown theoretically, the proposing side of the market (in this case, the hospitals) is systematically favored.”

1995–1998: the redesign

By the mid-1990s the analytic point had become a political one. Roth and Peranson describe the atmosphere directly: the market “began to suffer a crisis of confidence concerning whether the matching algorithm was unreasonably favorable to employers at the expense of applicants, and whether applicants could ‘game the system.’” The American Medical Student Association together with Ralph Nader’s Public Citizen Health Research Group, and the AMA’s Medical Student Section, demanded the algorithm be changed or at least honestly described. In a footnote, Roth and Peranson add that the Antitrust Division of the Department of Justice opened a discovery process at around the same time.

In the fall of 1995 the NRMP Board commissioned a new algorithm and a study comparing it to the old one. What the study found is the most quoted result in market design, and it is not what either camp expected.

Resolving the "1997 vs 1998" discrepancy

Secondary sources disagree, and both are right about different events. The Nobel popular background says the new algorithm was “adopted by the NRMP in 1997”. The Kleinberg–Tardos slides say the algorithm was “overhauled in 1998”. Roth and Peranson state both facts in one parenthesis: “(In May 1997, the NRMP Board of Directors decided to switch to the new algorithm, and the first match using the new algorithm was successfully completed in March 1998.)” Board decision May 1997; first live match March 1998. Use both dates and say which is which.

What the redesign actually changed — almost nothing, and it mattered enormously

Roth and Peranson ran the old and new algorithms on the real submitted rank order lists from 1987 and 1993–1996 — roughly 20,000 to 25,000 applicants a year — and counted who got a different result.

Year	Applicants affected	Prefer applicant-proposing	Prefer old algorithm	Programs affected
1987	20	12	8	20
1993	16	16	0	15
1994	20	11	9	23
1995	14	14	0	15
1996	21	12	9	19

Their own summary: “Only about 0.1 percent of applicants are affected by the change in algorithms, and of these, most prefer the match they receive under the applicant-proposing algorithm. Equally few programs are affected by the change of algorithms — and these constitute about 0.5 percent of all programs.”

Two lessons come out of that table, and they pull in opposite directions.

The first is that the theory’s headline result was real but tiny in magnitude. Proposer-optimality genuinely favours the proposing side — the direction of the effect is right in every year — but in this market the set of stable matchings is so small that switching sides moves about one applicant in a thousand. The mechanism is what Roth and Peranson call a “core convergence” result, and its driver is not market size but interview cost: applicants interview at only a handful of programmes, so rank order lists stay short (most applicants listed no more than fifteen programmes) even as the market grows. Short lists shrink the stable set. In a hypothetical market where everyone ranked everyone, the stable set would grow with n and the choice of algorithm would matter a great deal.

The second lesson is that “0.1% of applicants” is not the same as “0.1% of the welfare,” and it is definitely not the same as “0.1% of the politics.” Roth and Peranson are careful here: “in the debate that led to this study, and after our report was circulated to the interested parties, a great deal of discussion stemmed from the view that the difference in welfare was likely to be large for the affected applicants, and likely to be small for the affected programs. This contributed to the decision to adopt the applicant-proposing algorithm, a decision strongly lobbied for by the student organizations, and eventually unanimously adopted by the NRMP Board.”

Bounding manipulation: the number that is not four

Roth and Peranson also bounded manipulation empirically, and this part of the paper is very easy to misread — badly enough that it is worth walking the two experiments separately, because they answer different questions and only one of them is the result.

The preliminary experiment (truncate at the match point). In a simple match, truncating your list exactly at the entry you matched to cannot change anything, because neither proposing algorithm ever backtracks over a rank order list (ROL). The NRMP is not a simple match — the match variations mean “backtracking can occur” — so before measuring anything strategic, Roth and Peranson had to check whether that no-op still holds. It nearly does: “In the majority of cases no change was produced when all ROLs were truncated at the match point; and in no case were more than three applicants affected by such truncations. (Over the more than 60,000 applicants involved in these experiments, only four were affected by truncations of applicants’ ROLs; see Table B1 in Appendix B for the detailed results.)”

This is the sentence that gets misquoted

The “four out of more than 60,000” figure is a sanity check on the algorithm’s backtracking behaviour, not a measurement of how many applicants could gain by lying. It is a count of applicants whose match changed at all when every list was cut at its own match point — a manipulation that yields nothing by construction, since it removes only choices the applicant was never going to get. Reading it as “only four applicants could have profited from misreporting” inverts the paper: that experiment exists solely to license the next one. Roth and Peranson say so explicitly — “truncations at the match point, while not entirely without effect, do not play a substantial role … Because we have now seen that information beyond the match point influences the outcome for only a tiny percentage of participants, concentrating on truncations will give us a comparably good approximation for the numbers of participants who could potentially profit from any kind of strategic manipulation of ROLs.”

The real experiment (truncate one above the match point). Cutting the list one entry shorter than your match is the manipulation with teeth: you are refusing the position you actually got, betting that the resulting cascade delivers something better. Because one person’s truncation moves other people, a naive count over-counts, so Roth and Peranson iterate — truncate everyone, keep only those whose match improved, restore the rest, repeat until the set stops shrinking. The survivors are still an over-count (“even in a group of truncators who all do better when they all truncate their preferences, some may be profiting from the truncated ROLs of the others”), hence upper limit.

Table 4 — upper limit of the number of applicants who could benefit by truncating their lists at one above their original match point:

Year	Preexisting NRMP algorithm (program-proposing)	Applicant-proposing algorithm
1987	12	0
1993	22	0
1994	13	2
1995	16	2
1996	11	9

Table 5 — the same bound for programs:

Year	Preexisting NRMP algorithm	Applicant-proposing algorithm
1987	15	27
1993	12	28
1994	15	27
1995	23	36
1996	14	18

So the correct statement of the finding is a transfer of manipulability, not its elimination. Under the old program-proposing algorithm, between 11 and 22 applicants a year could in principle have gained by truncating, against 12–23 programmes. Switching to applicant-proposing drives the applicants’ bound to 0, 0, 2, 2, 9 — essentially to zero in the early years — and simultaneously raises the programmes’ bound to 27, 28, 27, 36, 18, higher in every single year. Roth and Peranson state both halves plainly: “As expected, more applicants can benefit from list truncation under the preexisting NRMP algorithm than under the applicant-proposing algorithm,” and “consistently more programmes benefit from list truncation under the applicant-proposing algorithm than under the preexisting NRMP algorithm.”

That is exactly what the one-to-one theory predicts and Proposer-Optimality and Strategic Truncation explains: the proposing side gets its optimal stable matching and has nothing to gain by lying, and the receiving side is the side left with an incentive. The 1990s redesign did not make the NRMP strategyproof; it chose which side bears the residual incentive, and chose the side with less capacity to act on it. A programme director runs the same market every year and can learn; an applicant participates once.

Two refinements keep this honest. First, the applicants’ bound is “in each year almost exactly equal to the number of applicants who received a preferred match under the applicant-proposing match (line 2 of Table 2)” — compare 12, 22, 13, 16, 11 against 12, 16, 11, 14, 12 above — which Roth and Peranson read as evidence “that this upper bound is very close to the precise number that would be predicted in the absence of match variations.” Second, the programmes’ bounds really are over-counts: re-running the 1995 experiment on a 50-percent sample of the programmes in the bound cut it substantially (Table 6), from 23 to 12 under the old algorithm and from 36 to 22 under the applicant-proposing one — “still an upper limit,” in their own column heading.

One caveat the paper is careful about and that a summary must not drop: the clean theoretical upper bound — “we can identify an upper bound on the number of applicants who could possibly profit from manipulating their Rank Order Lists, by seeing how many applicants receive different matches at the two algorithms” — does not directly apply to the NRMP, “because it depends for its proof on the existence of optimal stable matchings for each side of the market, which we know (from the sequencing experiments) do not exist in the NRMP data.” Couples destroy the side-optimal matchings; Table 2 is therefore a numerical benchmark to compare the computed bounds against, not a bound in its own right. And programmes have a second lever applicants do not: reducing the number of positions they submit, whose temptation “can be shown to be larger with the program-proposing algorithm than with the applicant-proposing algorithm (see Tayfun Sonmez, 1997, 1999)” — which cuts the other way, and is why the paper runs quota-reduction experiments as well as truncation experiments.

flowchart LR
    subgraph OLD["Program-proposing (pre-1998)"]
        OA["applicants who could gain<br/>by truncating: 11–22/yr"]
        OP["programmes who could gain: 12–23/yr"]
    end
    subgraph NEW["Applicant-proposing (1998–)"]
        NA["applicants: 0, 0, 2, 2, 9"]
        NP["programmes: 27, 28, 27, 36, 18"]
    end
    OA -->|"collapses"| NA
    OP -->|"rises"| NP
    style NA fill:#eefaee
    style NP fill:#ffecec

Figure — where the manipulation incentive went. Numbers are Roth and Peranson’s Tables 4 and 5, years 1987 and 1993–1996. The insight to take away: these are upper limits on a population of 20,000–25,000 applicants and 3,000–4,000 programmes, so both columns are tiny in relative terms — but the change is a reallocation, not a repair. No mechanism can be strategyproof for both sides at once — Roth’s 1982 Theorem 3, quoted above — so the redesign’s real decision was which side to leave exposed.

The NRMP’s own current description (fetched 2026-08-28) confirms the design is still applicant-proposing: “The matching algorithm is ‘applicant-proposing’ meaning it attempts to place an applicant (Applicant A) into the program indicated as most preferred on Applicant A’s rank order list,” with tentative matches that can be bumped and that “become final and binding for training” when all lists have been processed. Note that the public page describes the simple algorithm and does not mention couples or the stack machinery below.

---

Couples, and the Part That Is Not a Theorem

Couples are where hospital-residents stops being a solved problem. Two doctors who are a couple do not have individual preferences over positions; they have a joint preference over pairs of positions — (h₁, h₂) for her and him — and typically will take a mediocre pair in the same city over an excellent position and a terrible one a thousand miles apart. That is a complementarity, and it violates responsiveness, which is the assumption everything above rests on.

Stable Matching works the mechanism through in detail, including the exact quotation from Roth and Peranson explaining why couples break the “no hospital ever regrets a rejection” invariant, and an exhaustive verification of the Klaus–Klijn minimal counterexample (four candidate matchings, four blocked, zero stable). That is not repeated here. Three things are worth adding at the HR level.

Couples are a scale problem, not a curiosity

About 4 percent of NRMP applicants participate as couples, and 8–12% submit supplemental rank order lists for a second position — Roth and Peranson’s Table 1 puts both squarely in the “substantial part of the match” category, not the footnote category. Roughly 7% of the 3,000–4,000 participating programmes have positions that can revert to another programme if unfilled. The clearinghouse cannot treat couples as an edge case to be swept up afterwards; the “match variations” are the design.

And it has not gone away. Thirty years on, the NRMP’s own Results and Data: 2026 Main Residency Match reports 1,258 couples — 2,516 individual applicants, which against 48,050 active applicants is 5.2 percent, slightly higher than the 1990s figure. Their Table 14 tracks a decade:

Year	Couples	Individuals	Both matched	One matched	Neither matched	Match rate
2026	1,258	2,516	1,113	114	31	93.0%
2025	1,259	2,518	1,122	102	35	93.2%
2024	1,218	2,436	1,097	87	34	93.6%
2023	1,239	2,478	1,095	114	29	93.0%
2022	1,222	2,444	1,095	100	27	93.7%
2021	1,224	2,448	1,089	108	27	93.4%
2020	1,224	2,448	1,128	84	12	95.6%
2019	1,076	2,152	993	59	24	95.0%
2018	1,165	2,330	1,082	67	16	95.8%
2017	1,125	2,250	1,040	66	19	95.4%

The NRMP explains its own arithmetic, which is worth reproducing because the headline “match rate” is not what a reader assumes: it is “calculated by adding the number of ‘Both Matched’ (1,113 × 2 = 2,226) to the number of ‘One Matched’ (114) and dividing by number of ‘Individuals’ (2,516)” — so the One Matched column counts couples, not people, and each such couple contributes one matched individual. Note also that “Approximately 60 percent of couples are U.S. MD seniors,” which is why couples out-perform the market (93.0% against 79.8% for active applicants overall): they are on average stronger candidates, not beneficiaries of a favourable rule.

The NRMP’s definition of the object the algorithm handles is precise, and it is a narrower object than the general theory’s “couple”:

A couple is defined as any two individuals who identify themselves as such in the R3 system and who submit rank order lists of identical length. The matching algorithm treats the two lists as a unit; matching the couple to the highest pair of program choices where both partners obtain a match.

Two consequences. First, the equal-length requirement is what makes “pair k of the joint list” well defined — the couple submits a list of pairs, not two independent lists, which is exactly the joint-preference model that breaks responsiveness. Second, the deployed system provides an escape valve the textbook model does not: couples “have the option of one partner indicating a willingness to be unmatched at a specific rank on the rank order list if the other partner matches to the program paired to that rank”, and Table 14’s One Matched column counts exactly those (114 in 2026). Allowing a designated partner to accept being unmatched enlarges the set of joint outcomes the couple will accept, which makes non-existence strictly less likely — a small, unglamorous, non-theoretical design choice that buys real robustness.

How often does existence actually fail? Measured here

The sibling note verifies the published counterexample. The natural next question — how common is non-existence — appears not to be answered by a headline number anywhere in the sources read, so it was measured directly. A second program written for this note (couples.c) enumerates every feasible assignment of a small market with couples and counts the stable ones, using the correct responsive choice function for blocking (a hospital accepts a set of newcomers only if, after vacating the blocking couple’s current posts, all the newcomers land in its top q). The implementation is validated first against the published example before any random instance is run:

Klaus-Klijn minimal couples instance: 0 stable matchings (theory says 0)

singles couples hosp | instances | no stable | % empty | mean |S|
---------------------+-----------+-----------+---------+---------
   2       0      3  |   20000   |       0   |   0.00% |   1.01
   4       0      3  |   20000   |       0   |   0.00% |   1.17
   2       1      3  |   20000   |    1597   |   7.99% |   1.00
   2       1      4  |   20000   |     743   |   3.71% |   1.02
   3       1      3  |   20000   |    3337   |  16.68% |   0.96
   2       2      3  |   20000   |    5595   |  27.98% |   0.84
   2       2      4  |   20000   |    4466   |  22.33% |   0.91
   0       2      3  |   20000   |    2455   |  12.28% |   0.92

Reading the table:

• The two couple-free rows never fail. 40,000 instances, zero empty stable sets. That is the Gale–Shapley existence theorem showing up as an experimental fact, and it is the control that makes the rest of the table meaningful.
• One couple among two singles and three hospitals: 8.0% of instances have no stable matching at all. One complementarity is enough to destroy existence one time in twelve.
• Two couples: 28.0%. Non-existence is not asymptotically rare; it gets worse fast.
• More hospitals helps (7.99% → 3.71% when a fourth hospital is added at one couple; 27.98% → 22.33% at two). Slack in the market gives the couple somewhere to go, which is the same intuition as Kojima, Pathak and Roth’s large-market results.

Uncertain

Verify: whether these percentages are representative of anything beyond this generator. Reason: the couples’ preference lists here are uniformly random subsets of ordered hospital pairs of random length, which is a much harsher distribution than real couples’ preferences — real couples overwhelmingly want the same city, which is highly correlated, and correlation shrinks the stable set and makes existence more likely. These numbers establish that non-existence is common under adversarial-ish preferences, not that it is common in the NRMP. The NRMP’s own experience, per Roth and Peranson, is that failures are rare enough that none was observed across five years of real data. To resolve: rerun with a city-structured preference generator, or find published simulation results with realistic couple preferences.

The Roth–Peranson answer: a heuristic with a loop detector

Because there is no theorem to lean on, the deployed algorithm is engineering. Roth and Peranson build on Roth and Vande Vate’s (1990) instability-chaining idea: rather than running deferred acceptance to completion, grow a set A(k) of participants inside which there are no instabilities, and which is closed (nobody inside A(k) is matched to anybody outside it). Add one applicant at a time; each addition triggers a cascade of proposals and displacements which is chased until it settles; when A(k) contains everyone, the matching is stable and the algorithm stops.

stateDiagram-v2
    [*] --> AddApplicant: A(0) = all positions, all vacant
    AddApplicant: Add next applicant S(k) to A(k-1)
    AddApplicant --> Propose
    Propose: S proposes down its ROL until held or exhausted
    Propose --> Displaced: a held applicant is bumped
    Displaced --> Propose: bumped applicant proposes on
    Displaced --> CoupleSplit: bumped applicant is half of a couple<br/>or holds a supplemental post
    CoupleSplit: Partner withdrawn -> a position falls vacant<br/>push that program on the PROGRAM STACK
    CoupleSplit --> Propose
    Propose --> DrainProgramStack: applicant stack empty
    DrainProgramStack: Pop a program; push every applicant<br/>who could now block with it
    DrainProgramStack --> Propose: applicant stack refilled
    DrainProgramStack --> AddApplicant: both stacks empty -> M(k) has no internal instability
    AddApplicant --> Adjust: all applicants added
    Adjust: Apply even/odd requests and position reversions,<br/>then re-drain both stacks
    Adjust --> [*]: stacks empty -> final match
    Propose --> LoopDetect: same (applicant, position) vacated repeatedly
    LoopDetect: LOOP DETECTED — no termination guarantee here
    LoopDetect --> Propose: randomize processing order

What it shows: the actual control flow of the deployed Roth–Peranson algorithm, reconstructed from their Section III.A description — two work stacks (applicants and programmes), an outer loop that admits one applicant at a time, and a post-pass for even/odd requests and position reversions. The insight to take: the box labelled LoopDetect is the entire difference between this and a theorem. In a simple market both stacks always drain and the result is provably the applicant-optimal stable matching. With couples, “there is a possibility that at some stages of the algorithm the position stacks would never become empty (i.e., a cycle would occur),” so loop detectors have to be bolted on, keeping a log of which applicant was unmatched from which position; a repeat means a loop is in progress. Roth and Vande Vate observed that some “inessential” loops can be dissolved by randomizing processing order. Loops caused by genuine non-existence cannot be.

Roth and Peranson’s own honesty about this is the model for how to report a heuristic: “But to determine how often it might fail to produce a stable matching we need some computational experiments. The experiments reported next … will also show that failures are rare: we will not observe even a single failure when we explore different versions of the algorithm on previous years’ ROL data.” Zero failures across five years of real data, on multiple sequencing variants. That is evidence, not proof, and they never call it proof.

There is a further reason the deployed system cannot fall back on theory: with couples present, essentially none of the standard structure survives. Aldershof and Carducci (1996) showed by example that even when stable matchings do exist, the set need not form a lattice, there need be no applicant-optimal or hospital-optimal stable matching, and — the point most relevant to this note — the set of unmatched agents need not be the same at every stable matching (per Roth 2008). The Rural Hospitals Theorem itself fails with couples. You can see its failure in the real NRMP data: Roth and Peranson report that in two of the five years studied, the number of applicants matched changed by one between the two algorithms — “in a simple match a change from one stable matching to another would never change the number of applicants matched; so here is another case in which the match variations cause a difference, but a difference which turns out to be very small and unsystematic.” One position in twenty thousand. The theorem is false in the deployed market, and false by about 1 / 20,000.

And there is no cheap escape hatch: Ronn (1990) showed that deciding whether a stable matching exists in a market with couples is intractable, so “just check first, then fall back” is not a strategy either. The result is corroborated by two independent sources read here, and they word it slightly differently, which is worth recording rather than smoothing over. Kojima, Pathak & Roth call it NP-complete; Roth’s own survey states in a footnote that “Ronn (1990) showed that the problem of finding if a given profile of preferences has a stable matching is NP hard when couples are present” (Roth 2008, fn. 23), and its bibliography gives the source as Eytan Ronn, “NP-complete stable matching problems,” Journal of Algorithms 11(2), June 1990, pp. 285–304. The two are consistent — the decision problem is in NP (a candidate matching is checkable in polynomial time by the blocking-pair scan implemented above), so NP-hard plus membership gives NP-complete — but “hard” and “complete” are not interchangeable words and a note that uses one should be able to say why the other holds.

Uncertain

Verify: Ronn’s exact theorem, in particular which variant of the couples model it is stated for (hospital-residents with couples, or the “stable marriage with couples” special case) and whether the hardness survives when couples’ preferences are responsive to their individual preferences. Reason: the primary paper was not retrieved. Journal of Algorithms 11(2) is an Elsevier title with no open mirror found; both statements above are second-hand, from sources that were read in full. To resolve: obtain Ronn (1990), or the treatment in Manlove’s Algorithmics of Matching Under Preferences.

---

Failure Modes and Gotchas

Treating an omitted hospital as “ranked last” rather than “unacceptable.” With incomplete lists, a hospital you did not rank is worse than unemployment. Conflating the two produces matchings that assign doctors to posts they would refuse, and — worse — a stability checker that agrees. The r_prefers guard clauses above exist for exactly this. Symptom: your brute-force enumerator reports far more stable matchings than the theory’s lattice allows, or reports stable matchings in which someone is matched to a hospital not on their list.

Comparing a resident against a hospital’s first holder instead of its worst. The quota generalization changes only one line of the blocking test, and it is easy to compare r against the wrong incumbent. Symptom: deferred acceptance and brute force disagree, and the discrepancies all involve full hospitals.

Assuming the algorithm chooses the rural hospital’s fill rate. This is the policy version of the bug, and it has cost real committees real time. Any request of the form “can the match be tuned to help under-filled programmes fill?” is answered no by the Rural Hospitals Theorem, as long as the outcome must remain stable. Redirect the conversation to the preferences or the quotas.

Assuming the Rural Hospitals Theorem still holds once couples are in the data. It does not, as the NRMP’s own numbers show. If your system has couples, joint programme requirements, or any other complementarity, the invariants are approximations that happen to be extremely good — not guarantees.

Believing “0.1% of applicants affected” means the choice of algorithm does not matter. The magnitude of the effect and the importance of the effect are different quantities. The redesign changed about twenty people’s careers a year, was demanded by student organizations, and was adopted unanimously. Small effects on rare individuals can be exactly the effects a market’s legitimacy rests on.

Assuming the stable set is small because the market is large. It is the opposite: in a market where everyone ranks everyone, the stable set grows with n. The NRMP’s stable set is small because interviewing is expensive and lists are short. A system that removes the interview cost — say, algorithmic pre-screening that lets applicants rank hundreds of programmes — would enlarge the stable set and make the choice of proposing side matter much more.

Trusting the algorithm’s own output as evidence of stability. Every result in this note came from an independent count_blocking scan over all acceptable pairs, and the stable-set enumeration is a separate program path from deferred acceptance. When the two agree you have a real check; when a single code path both produces and validates the matching you have nothing.

---

Alternatives and When to Choose Them

Approach	Guarantees	Fails at	Use when
Applicant-proposing DA (NRMP since March 1998)	Stable; applicant-optimal; strategyproof for applicants	Couples, complementarities, ties	Two-sided market, responsive employer preferences, applicants are the side you want to protect
Hospital-proposing DA (NRMP 1951–1997)	Stable; hospital-optimal	Same, plus applicants can gain by truncation	You are the employer side and the market has not noticed yet
Roth–Peranson instability chaining	Stable in practice; handles couples, supplemental lists, reversions, even/odd requests	No existence guarantee; can loop; no lattice, no optimal stable matching	Real markets with complementarities, where zero observed failures over years of data is the achievable bar
Priority matching (Mullin–Stalnaker 1950; several 1960s NHS regions)	Simple; nothing else	Produces unstable outcomes; participants learn to game it; historically abandoned	Never, in a market participants can circumvent
Top Trading Cycles	Pareto efficient; strategyproof; unique core allocation	Not stable — ignores priorities, so it creates justified envy	One-sided allocation with no genuine employer preferences (houses, offices, kidneys); or school choice when efficiency beats priority-respect
Bipartite Matching (maximum cardinality)	Maximizes total matched pairs, in polynomial time	Ignores preferences entirely; the result is generally unstable	You have a global count to maximize and no per-agent rankings
Decentralized offers with deadlines	None	Unraveling, then exploding offers; documented empirically since the 1920s	The market is small enough that everyone can talk to everyone

The comparison with Top Trading Cycles and Bipartite Matching deserves emphasis because all three carry the word “matching” and none of them solves the same problem. Maximum bipartite matching optimizes a global count and has no notion of preference. TTC honours preferences on one side only and produces an efficient, unstable outcome. Deferred acceptance honours preferences on both sides and produces a stable, generally inefficient outcome. Choosing between the last two is a genuine policy decision, not a technical one — see Top Trading Cycles for the school-choice version of that argument.

---

Production Notes

Scale and cadence. The NRMP fills approximately 20,000 positions a year across 3,000–4,000 programmes, with 20,000–25,000 applicants submitting primary rank order lists in the years Roth and Peranson studied (1987, 1993–1996). It runs once a year, which is what makes an O(Σ|list|) algorithm with naive inner scans perfectly adequate — the computational budget is not the constraint, correctness and auditability are.

Scale today — the market has roughly doubled since the redesign. The Roth–Peranson figures date from the 1990s and are now badly out of date as a description of the deployed system. As of the 2026 Main Residency Match, per the NRMP’s own Match by the Numbers (published March 2026, read 2026-08-29):

Quantity	2026 figure	Change vs 2025
Total positions offered	44,344	↑ 1,107 (2.6%)
Total PGY-1 positions	41,126	↑ 1,085 (2.7%)
Total positions filled	41,482	↑ 718 (1.8%)
Unfilled positions	2,862	↑ 389 (15.7%)
Percent of all positions filled	93.5%	↓ 0.8 pp
Total registered applicants	53,373	↑ 875 (1.7%)
Applicants certifying a rank order list (“active”)	48,050	↑ 842 (1.8%)
Applicants matched to PGY-1 positions	38,354	↑ 687 (1.8%)
Percent of active applicants matched to PGY-1	79.8%	0.0 pp
Couples submitting program choices	1,258	↓ 1
Couples match rate	93.0%	↓ 0.2 pp

NRMP flags most of these lines as “highest on record.” Three things are worth extracting. First, the “approximately 20,000 positions” of the 1990s is now 44,344 offered and 41,482 filled — roughly double, so any performance intuition calibrated on Roth and Peranson’s numbers is off by a factor of two. Second, 2,862 positions went unfilled, and the count rose 15.7% year over year; the Rural Hospitals Theorem says that number is a property of the submitted preferences, not of the algorithm, so it cannot be argued down by changing the match. Third, the couples problem has not shrunk: 1,258 couples means 2,516 individuals, about 5.2% of the 48,050 active applicants — squarely consistent with the “about 4 percent” Roth and Peranson measured from their Table 1 in the 1990s, and confirming that the case the algorithm has no existence theorem for is a permanent, five-percent-of-the-market feature rather than a shrinking legacy problem. Their 93.0% match rate is, notably, higher than the 79.8% for active applicants overall — couples are on average stronger candidates, which is part of why the heuristic has never been observed to fail.

The programme count is not on that summary sheet; it is in the full report, Results and Data: 2026 Main Residency Match (NRMP, Washington DC, May 2026; 94-page PDF, read 2026-08-29). Its Table 1A carries a “No. of Programs” column whose GRAND TOTAL row reads 6,809 programmes offering the 44,344 positions, of which 5,961 are PGY-1 programmes offering 41,126 PGY-1 positions. So the “3,000–4,000 programmes” of the Roth–Peranson era has also roughly doubled. The report’s own SOAP figures complete the picture of what happens to the 2,862 unfilled positions: “An additional 109 positions were unfilled in programs that did not submit a rank order list, bringing the total unfilled to 2,971. Of those, 2,851 were placed in the SOAP… At the conclusion of SOAP, 219 positions remained unfilled from 140 SOAP-participating programs. The overall fill rate, matching and SOAP processes combined, was 99.3 percent.” The Supplemental Offer and Acceptance Program is, in effect, the aftermarket that the stable match is not allowed to be — an explicitly non-stable, first-come mop-up round bolted on after the algorithm has done what stability permits.

A retrieval note for anyone repeating this

The NRMP’s data-reports index at https://www.nrmp.org/match-data-analytics/residency-data-reports/ is a JavaScript-driven listing: a plain curl returns HTTP 200 and 421 KB of HTML containing zero links to any report PDF, because the list is rendered client-side. The reports themselves are static files under https://www.nrmp.org/wp-content/uploads/<YYYY>/<MM>/, and fetching them by that path works with no session or cookie. HTTP 200 on the index page is not evidence that the data is reachable from it.

The match variations are the system. A production HR clearinghouse is not the textbook algorithm. The NRMP handles, per Roth and Peranson: couples submitting joint lists of position pairs (~4% of applicants); supplemental rank order lists for applicants who need a first-year position to accompany a second-year one (8–12%); position reversions, where a programme’s unfilled slot transfers to another programme (~7% of programmes, ~6% of the total quota); and even/odd matching requests, where a programme wants an even number of matches. Their published sequencing specification runs to nine numbered clauses covering the order in which applicants, couples, programmes, reversions and even/odd requests are processed — because with complementarities present, processing order changes the outcome, whereas in a simple match it provably does not.

Design by computational experiment. Roth and Peranson’s framing of their own work is the transferable lesson: “This process resembles engineering practice rather than theorem-proving or hypothesis-testing.” Their suspension-bridge analogy — Newtonian mechanics gives you the cable curve, but no bridge is built without metal fatigue, soil mechanics, and wind — is the honest description of what deploying a mechanism looks like. Every design decision they could not settle analytically (sequencing, loop handling) was settled by running variants on five years of real submitted lists.

Adjacent markets adopted the same design. Fellowship matches for individual specialties, many initiated in the 1980s and 1990s after those markets unraveled the way the intern market had, now run through the same machinery. The failure mode reproduces reliably in any entry-level professional market with a fixed start date, which is why the same fix keeps being applied.

Legal exposure is part of the deployment. Roth and Peranson note in a footnote that the DOJ Antitrust Division opened a discovery process concerning these markets in the mid-1990s, resulting in a narrowly focused consent decree involving the Association of Family Practice Residency Directors. A clearinghouse that determines wages and placements for 20,000 people a year is a piece of market infrastructure with antitrust surface area, not merely a piece of software. (Roth’s own paper page also hosts the Jung v. AAMC complaint and the 2004 legislation that followed, though those documents were not fetched for this note.)

Verification discipline. Every quantitative claim in this note that is not a quotation was produced by two independent code paths — deferred acceptance, and an exhaustive enumerator with a separate blocking-pair scanner — and the couples implementation was validated against a published counterexample before being pointed at random data. That ordering is not optional: a blocking-pair definition with couples in it is subtle enough that a plausible-looking wrong version will happily report reasonable-looking numbers.

---

See Also

• Stable Matching — the one-to-one theory this note generalizes: blocking pairs, the lattice, stable roommates, and the exhaustive verification of the Klaus–Klijn couples counterexample
• The Gale-Shapley Algorithm — deferred acceptance itself, its O(n²) bound, and its correctness proofs
• Proposer-Optimality and Strategic Truncation — why the side that proposes wins, which is the theorem the 1990s redesign turned on
• Top Trading Cycles — the one-sided sibling: efficient and strategyproof but not stable, and the direct competitor to deferred acceptance in school choice
• Bipartite Matching — maximum matching: same picture, different problem, no preferences
• Incentive Compatibility — the vocabulary for “applicants cannot gain by lying”
• Impossibility Results — the fences: no stable mechanism is strategyproof for both sides
• Mechanism Design — the general inverse problem this is an instance of
• Games and Strategic Systems in C MOC — the parent MOC; this note is part of stage P5