Gale-Shapley deferred acceptance matching medical graduates to residency programs — the NRMP Main Residency Match
Every year, tens of thousands of medical graduates and thousands of residency programs each submit a confidential, ranked list of preferences to the National Resident Matching Program (NRMP). Neither side ever sees the other's list. What happens next is not a negotiation, an auction, or a lottery — it is the deterministic execution of a mathematical algorithm proven, in 2012, to be Nobel Prize-worthy economics.
An applicant's Rank Order List (ROL) is a strict, total ordering of every program they interviewed with, from most to least preferred — informed by location, specialty reputation, culture, research opportunities, and countless interview-day impressions. A program's ROL is a strict ordering of every applicant it interviewed, typically built from USMLE Step scores, letters of recommendation, clerkship grades, research output, and interview performance, often via a weighted composite scoring rubric.
Critically, ROLs are submitted once, in secret, before the algorithm ever runs. There is no back-and-forth. This is what economists call a "one-shot mechanism": both sides commit to their true preferences (in theory) and a centralized clearinghouse computes the outcome. The quality of the resulting match depends entirely on the honesty and completeness of these lists — which is why the algorithm's incentive properties (discussed in Stage 2) matter enormously.
Before 1952, US medical students received residency offers directly from hospitals, often accompanied by exploding deadlines: "accept within 12 hours or the offer disappears." This created a destructive unraveling — hospitals extended offers earlier and earlier, sometimes years before graduation, to beat competitors, while students were pressured into decisions without complete information.
The NRMP was founded in 1952 to centralize this process into a single annual clearinghouse. Economists Alvin Roth later showed formally (1984) that the original NRMP algorithm was mathematically equivalent to the Gale-Shapley deferred acceptance procedure — discovered independently by the market's designers years before Gale and Shapley published their 1962 paper "College Admissions and the Stability of Marriage."
A matching is stable if there is no "blocking pair" — no applicant A and program P who are not matched to each other but who would both prefer to be. If such a pair existed, A could call P directly, and both would abandon their current assignments — the match would unravel. Gale and Shapley proved that a stable matching always exists for any set of preferences, and that their deferred-acceptance algorithm always finds one, terminating in a finite number of rounds.
This single property — stability — is the entire reason the NRMP algorithm has survived unchanged in its core logic for over 70 years: a matching mechanism without it is not self-enforcing, and participants have an incentive to circumvent it.
In 2012, the Royal Swedish Academy of Sciences awarded the Nobel Memorial Prize in Economic Sciences jointly to Lloyd Shapley and Alvin Roth "for the theory of stable allocations and the practice of market design." Shapley's half of the prize rested on the pure mathematics of the 1962 Gale-Shapley paper; Roth's half rested on his empirical work showing that real-world matching markets — including the NRMP — succeed or fail based on exactly the stability property Gale and Shapley had characterized decades earlier.
At the moment the algorithm runs, every applicant simultaneously "proposes" to the single program at the top of their rank-order list. Programs receive a wave of proposals, sort them alongside any applicants already tentatively held, and keep only their most-preferred candidates up to capacity. Everyone else is provisionally — never permanently — rejected.
Each round proceeds in two synchronized steps:
1. Every free (unmatched) applicant proposes to the highest-ranked program on their list that has not yet rejected them. 2. Every program that received at least one new proposal pools it with any applicants it is already tentatively holding, re-sorts the combined pool by its own preference order, and keeps the top C (its capacity). Everyone below the cutoff — including previously held applicants who are now outranked — is rejected and becomes free again.
This is why the algorithm is called "deferred acceptance": a program never issues a final "yes." Every acceptance is tentative and can be revoked by a stronger later proposal, right up until the very last round.
A subtle but crucial invariant holds throughout the run: once a program tentatively holds a set of applicants, the quality of its held set (by its own preferences) never decreases round over round. Each round, a program either keeps its current holds or replaces its weakest held applicant with a more-preferred proposer. Programs are therefore never made worse off by continuing to run more rounds — hence the process is guaranteed to converge to something programs are weakly happy with.
Applicants experience the mirror image: each rejection forces them down their own list, so an applicant's prospects (by their own preferences) never improve round over round. This asymmetric monotonicity — programs improve or hold steady, applicants hold steady or worsen — is the mathematical engine that proves termination.
Gale and Shapley proved a striking asymmetry: whichever side does the proposing ends up with the best stable matching achievable from its own perspective — the "proposer-optimal" stable matching — while the receiving side gets its worst stable matching among all stable options. The original NRMP algorithm (1952-1997) had programs proposing to applicants, which was later shown to be systematically program-favorable.
A 1995 controversy, sparked by a mathematical critique from economist Alvin Roth showing the incumbent algorithm could disadvantage applicants and was even manipulable, led the NRMP to commission a redesign. Roth and Elliott Peranson built the current applicant-proposing algorithm, adopted in 1998, guaranteeing that among all valid stable matchings, applicants receive the one that is best for them collectively.
A single rejection rarely stays contained. When a program bumps a previously-held applicant in favor of a stronger proposer, that displaced applicant immediately proposes to their next-ranked program — which may in turn bump someone else. These rejection chains ripple through the entire market until every applicant is either held somewhere or has exhausted their full list.
Consider applicant A, tentatively held by program P after round 3. In round 7, applicant B — ranked higher by P — proposes to P for the first time. P must now choose: it re-sorts its combined pool of {existing holds + B} by its own preference order and keeps only the top C. If B outranks A, A is displaced. A then proposes to the next program on A's own list in round 8, potentially displacing someone there, and so on.
Because every rejection permanently removes one applicant-program pair from future consideration (a rejected applicant never re-proposes to the same program), the total number of possible proposals across the entire run is bounded by (number of applicants) × (number of programs) — which is exactly what guarantees the algorithm terminates in finite time rather than cycling forever.
The classical Gale-Shapley proof assumes each participant has a strict, independent preference ordering. Medical couples applying together break this assumption: a couple submits a single joint rank-order list of program *pairs* (one slot for each partner), because "Program X for me and Program Y for my partner in the same city" is preferred as a unit, not as two independent placements.
With couples in the mix, a stable matching is not guaranteed to exist in the pure theoretical sense — pathological preference cycles can, in principle, cause the algorithm to loop. The NRMP's production algorithm (Roth-Peranson) handles this with a modified procedure that processes couples as linked units and includes cycle-breaking logic; empirically, across decades of real preference data, it has always converged, but the theoretical guarantee that exists for single applicants does not strictly extend to couples.
The formal termination proof rests on two monotone sequences running in opposite directions:
• Applicant welfare (by their own ranking) is weakly decreasing round over round — every rejection pushes an applicant further down their list, never back up. • Program welfare (by its own ranking) is weakly increasing round over round — a program's held set only ever improves or stays the same as stronger proposers arrive.
Both sequences are bounded (an applicant's list has finite length; a program's capacity is fixed), so both must stabilize after finitely many rounds. Once no applicant is rejected in a round, the process has converged — there are no more moves to make, and the matching is final.
| Product | Indication | Trial Design | Key Result |
|---|---|---|---|
| Main Residency Match | ~45,000 applicants / ~6,000 programs | Applicant-proposing deferred acceptance (Roth-Peranson, since 1998) | Applicant-optimal among all stable matchings |
| Couples Match | ~1,300 linked applicant pairs | Joint rank-order list of program-pairs, processed as a single linked unit | Keeps partners geographically coordinated |
| SOAP | Unmatched applicants + unfilled seats | Compressed 4-round offer cycle over ~1 week before Match Day | Fills remaining seats in days, not months |
| Specialty / Fellowship Matches | Ophthalmology, urology, sub-specialty fellowships | Same deferred-acceptance core, run by separate matching services (e.g. SF Match) | Same stability guarantee outside the Main Match |
When a round passes with zero new proposals, the algorithm halts and every tentative hold becomes permanent. What has actually been proven, mathematically, is stronger than "everyone got assigned somewhere" — it is that the resulting matching cannot be improved upon by any applicant-program pair acting outside the system.
For any given set of preferences, there can be many different stable matchings — not just one. Remarkably, Gale and Shapley proved that the set of all stable matchings forms a mathematical lattice: there exists an applicant-optimal stable matching (every applicant likes it at least as well as any other stable matching) and, simultaneously, a program-optimal stable matching at the opposite end of that lattice — and the two rarely coincide.
Applicant-proposing deferred acceptance always lands exactly on the applicant-optimal end. This is a deep structural fact, not a coincidence of implementation: whichever side proposes ends up strictly favored among all valid stable outcomes.
To confirm a matching is stable, you check every applicant-program pair that is not currently matched together, and verify at least one of two conditions holds: either the applicant prefers their current assignment (or would rather stay unmatched) to that program, or the program prefers everyone it currently holds to that applicant. If both conditions fail for any pair, that pair is "blocking" — they would defect together — and the matching is not stable.
Deferred acceptance guarantees this check passes for every single pair at termination, essentially by construction: any applicant who might want to defect to a given program already tried proposing there earlier in the run and was rejected, meaning that program already held applicants it preferred.
Alvin Roth proved in 1982 that applicant-proposing deferred acceptance is strategy-proof for the proposing side: no applicant can ever obtain a better outcome by submitting a rank-order list that misrepresents their true preferences. Honesty is a dominant strategy for applicants — a foundational reason NRMP guidance simply tells applicants to "rank programs in your true order of preference."
The same guarantee does not extend to programs. In principle, a program could occasionally benefit from strategically truncating or reordering its list. Roth also proved (1982) that no mechanism can be simultaneously strategy-proof for both sides of a two-sided matching market — a fundamental impossibility result, not a flaw specific to the NRMP's implementation.
Because deferred acceptance is provably strategy-proof for applicants, "gaming" your rank-order list by ranking a "safety" program higher than your true preference can never help — and can only hurt — your outcome. The single dominant strategy is to rank programs in genuine order of preference.
On the third Friday of March each year, at 12:00 noon Eastern Time, tens of thousands of medical students across the United States open an envelope — or, increasingly, a portal notification — simultaneously. For the small fraction who did not match, and for programs left with unfilled positions, the story does not end there: SOAP begins the week before Match Day and races to fill remaining seats before it.
Match Week begins on Monday, when applicants privately learn only whether they matched (a binary yes/no, with program details withheld). The full results — which specific program each applicant matched to — are released together on Match Day itself. Many US medical schools stage elaborate envelope-opening ceremonies, a tradition dating to when results genuinely arrived by physical mail; today it is largely symbolic theater layered on top of an already-computed, purely algorithmic result.
The drama is real even though the outcome was fixed days earlier: the algorithm runs once, centrally, and the "reveal" is a scheduling and communications event, not a live computation.
Applicants who do not match, and programs that do not fill, are identified during Match Week and immediately enter the Supplemental Offer and Acceptance Program. Eligible unmatched applicants can apply to any program with unfilled positions using a standardized application; programs then extend offers in up to four scheduled rounds, each with a roughly two-hour applicant response window, over the course of just a few days.
SOAP replaced the earlier, more chaotic "Scramble" (pre-2012), in which unmatched applicants cold-called programs by phone in an unstructured free-for-all. SOAP imposes the same discipline the Main Match brought to the primary process — structured offers, defined windows, no exploding informal deals — onto the leftover seats.
Unmatched status is driven overwhelmingly by market imbalance in specific specialties and applicant categories, not primarily by algorithm mechanics — the algorithm faithfully finds a stable matching from whatever preferences and capacities exist; it cannot manufacture seats that do not exist. International medical graduates (IMGs) and applicants to the most competitive specialties historically face materially higher non-match rates than US MD seniors applying broadly.
Because deferred acceptance is applicant-optimal, an applicant who goes unmatched under this algorithm would also go unmatched under literally every other stable matching consistent with the same submitted preferences — the algorithm is not the bottleneck; the ratio of applicants to available, mutually-acceptable seats is.
The Match has faced real scrutiny. In Jung v. Association of American Medical Colleges (2002), a group of former residents alleged the NRMP process suppressed resident salaries in violation of antitrust law. Congress responded in 2004 with legislation exempting graduate medical education matching programs from certain antitrust claims, and the case was ultimately dismissed — but the episode sparked lasting debate over whether a single, mandatory, centralized clearinghouse concentrates too much power over new physicians' working conditions.
Separately, researchers continue to study whether couples matching, specialty-specific sub-markets, and the sheer scale of the modern Match (tens of thousands of participants) introduce edge cases the original 1962 theory did not fully anticipate — an active area of market-design research descended directly from Gale and Shapley's original paper.
Despite these debates, the core deferred-acceptance mechanism has not been replaced in over 25 years of production use — a rare case of a single 1962 mathematics paper directly governing a real market that places tens of thousands of people into their careers every year.