Confetto

Residency Match Algorithm and the 2012 Nobel Prize

Practice the residency interview now

Free, no sign-up to start.

How the Gale-Shapley and Roth-Peranson algorithms power the NRMP residency match, why they won the 2012 Nobel Prize, and what it means for applicants.

Practice the residency interview now

Free, no sign-up to start.

The residency match algorithm won the 2012 Nobel Prize in Economic Sciences for economists Alvin E. Roth and Lloyd S. Shapley. According to the Royal Swedish Academy of Sciences, Shapley co-created the 1962 deferred acceptance formula, and Roth redesigned the U.S. residency match in 1995. Adopted in 1997, this applicant-proposing system helps the National Resident Matching Program fill more than 40,000 clinical training positions each year. Sources: The Nobel Prize: The Prize in Economic Sciences 2012 Summary, The Nobel Prize: The Prize in Economic Sciences 2012 Press Release, The Nobel Prize: The Prize in Economic Sciences 2012 Popular Information. Last checked November 12, 2026.

Why the residency match algorithm won the 2012 Nobel Prize

On October 15, 2012, the Royal Swedish Academy of Sciences awarded the Nobel Memorial Prize in Economic Sciences to Alvin E. Roth and Lloyd S. Shapley. They shared the SEK 8 million award equally, worth $1.2 million according to the Stanford Report, for stable allocations theory and market design.

Standard economic models assume that rising or falling prices will balance supply and demand on their own. Matching markets work differently because money alone cannot decide who gets a hospital residency, a public school seat, or a donated organ. You cannot simply pick the training spot you want. The hospital or school must also choose you.

Shapley, a mathematician at the University of California, Los Angeles, built the cooperative game theory behind stable matching in the 1950s and 1960s. Working with mathematician David Gale in 1962, with partial funding from the Office of Naval Research per the University of California, he created the deferred acceptance algorithm. Gale passed away in 2008 and was ineligible for the 2012 award, while Shapley died on March 12, 2016.

Roth, who earned his Stanford Ph.D. in 1974 and taught at Illinois, Pittsburgh, Harvard, and Stanford, connected Shapley's abstract math to real institutions. Although the two laureates never collaborated directly, Roth proved why the U.S. medical match succeeded and rebuilt its formula for modern applicants. If you are preparing for healthcare school or residency interviews, Confetto runs AI mock interviews with realistic follow-up questions. Start your free week.

From 1940s exploding offers to the 1952 clearinghouse

Before centralized matching existed, U.S. hospitals hired medical interns in an open, uncoordinated labor market. During the 1940s, fierce competition for scarce medical students pushed hospitals to extend internship offers earlier every year. Eventually, hospitals and students were signing post-graduation training contracts two full years before medical school graduation.

Economists call this breakdown market unraveling. Students had to commit before seeing their own clinical grades or knowing which branch of medicine they wanted to practice. Worse, hospitals issued exploding offers with strict, short reply deadlines so they could chase other candidates if turned down. Students had to accept or reject offers blind, without knowing whether a preferred hospital would call the next day.

To end the pressure, the National Resident Matching Program, or NRMP, was established in 1952 at the request of medical students. Instead of scattered early contracts, applicants and program directors completed interviews first and then submitted confidential rank order lists to a central clearinghouse.

Ten years after the clearinghouse launched, Gale and Shapley published their 1962 paper, College Admissions and the Stability of Marriage, in the American Mathematical Monthly. Neither group knew about the other's work at the time. In a 1984 paper, Roth analyzed the NRMP's 1950s clearinghouse rules and proved they were essentially equivalent to Gale and Shapley's deferred acceptance algorithm.

Roth tested whether stability truly mattered in 1990 and 1991 by studying regional medical clearinghouses in Britain's National Health Service. British regions like Edinburgh that used stable matching rules survived, while regions like Newcastle and Birmingham that used unstable mechanisms collapsed. Laboratory experiments published in 2000 by Roth and John Kagel confirmed that the algorithm rules caused that split.

How deferred acceptance works: applicant-proposing vs. program-proposing

A match is mathematically stable when it produces zero blocking pairs. A blocking pair occurs if you prefer another hospital over where you matched, and that hospital also prefers you over one of its matched applicants. When blocking pairs exist, dissatisfied doctors and hospitals have a direct incentive to break their matches and make side deals.

The deferred acceptance algorithm eliminates blocking pairs by keeping every match tentative until all rank lists are processed. In the NRMP's step-by-step guide, the system first tries to place Applicant A into the top-ranked program on Applicant A's rank order list. If that program also ranked Applicant A and has an unfilled slot, Applicant A gets a tentative match.

If the program's slots are already filled, the algorithm checks whether the program prefers Applicant A over a currently held candidate, Applicant B. When Applicant A ranks higher on the program's list, Applicant A takes the tentative spot and Applicant B is bumped. The algorithm then returns to Applicant B's rank order list and tries Applicant B's next preferred choice.

Gale and Shapley proved mathematically that this cycle always stops at a stable matching for every participant. Still, who proposes first matters whenever more than one stable outcome exists. Whichever side proposes systematically receives its best possible stable match, while the receiving side gets its worst stable match.

Trace the worked example below written by our team, expanding the three-doctor illustration from the Nobel Prize popular information report. Three applicants and three single-seat hospitals submit identical lists under both versions. Applicant 1 ranks A, B, C. Applicant 2 ranks A, B, C. Applicant 3 ranks A, C, B. Meanwhile, Hospital A ranks 1, 2, 3, Hospital B ranks 3, 2, 1, and Hospital C ranks 2, 3, 1.

Both outcomes in the table are 100 percent stable, with zero blocking pairs in either column. Switching the right to propose from hospitals to applicants lifts both Applicant 2 and Applicant 3 from their third choice to their second choice.

Worked example by our team: Applicant-proposing vs. hospital-proposing deferred acceptance
StageApplicant-Proposing (Modern NRMP, 1997 onward)Hospital-Proposing (Pre-1997 NRMP)
Round 1 proposalsApplicants 1, 2, and 3 all propose to Hospital A.Hospital A proposes to 1, Hospital B proposes to 3, and Hospital C proposes to 2.
Round 1 holds and rejectionsHospital A tentatively holds Applicant 1 and rejects Applicants 2 and 3.Applicants 1, 2, and 3 each receive one offer and tentatively hold it.
Round 2 proposalsApplicant 2 proposes to second choice B, and Applicant 3 proposes to second choice C.No rejections happened in Round 1, so no Round 2 is needed.
Final binding match1 matches at A, 2 matches at B, and 3 matches at C.1 matches at A, 2 matches at C, and 3 matches at B.
Distributional resultApplicants 2 and 3 get second choices, while Hospitals B and C get second choices.Hospitals A, B, and C all get first choices, while Applicants 2 and 3 drop to third choices.

The 1995 Roth-Peranson redesign, couples, and truth-telling

Until the mid-1990s, the NRMP ran a hospital-proposing version of the clearinghouse. Student advocates criticized the system once economists showed that hospital proposals systematically favored hospitals over doctors. At the same time, growing female medical school enrollment meant many more dual-doctor couples needed two residencies in the same geographic region.

Because the older clearinghouse could not coordinate two linked careers well, couples increasingly arranged jobs outside the Match, threatening market stability. In 1995, NRMP director Bob Beran asked Alvin Roth to direct a redesign alongside consultant Elliott Peranson, supported by the National Science Foundation. The NRMP adopted their applicant-proposing Roth-Peranson algorithm in 1997.

Accommodating couples meant tackling a hard mathematical limit. In a market of solo applicants, at least one stable outcome is always guaranteed to exist. As Roth explained in his Nobel biography, once two-career couples rank pairs of jobs together, the set of stable matchings can theoretically be empty.

Roth and Peranson built a specialized algorithm that resolves potential instabilities sequentially while treating a couple's linked rank order lists as a single unit. Any two applicants can participate in the Main Residency Match as a couple, per the Association of American Medical Colleges.

Switching to applicant proposals also protected honest ranking for individual candidates. In 1981 and 1982 papers, Lester Dubins, David Freedman, and Alvin Roth proved two game-theory rules on strategic incentives. First, no stable matching mechanism can make stating true preferences a dominant strategy for every employer and every worker at the same time.

Second, under applicant-proposing deferred acceptance, ranking your true preferences is a dominant strategy for solo applicants. Under the older hospital-proposing design, students could sometimes game better matches by rejecting preferred early offers. Under the modern NRMP algorithm, ranking a reach program first never hurts your chances at a backup program. Roth's computer simulations also verified that hospitals gained no practical benefit from strategic manipulation in real residency markets.

Beyond residency: public schools, kidney chains, and SOAP

Show details

The market engineering tested in graduate medical education soon fixed broken allocation systems in urban public schools and organ transplantation. In both areas, law or ethics barred cash bidding, yet thousands of families and patients needed fair matches.

Until 2003, New York City let more than 90,000 prospective high school students rank only five schools while principals made separate offers. About 30,000 students each year ended up assigned to schools they never listed, and over a third of eighth graders skipped the process. Because schools favored applicants who listed them first, families had to hide true favorites and rank safer options at the top.

In 2003, Roth, Parag Pathak, and Atila Abdulkadiroglu rebuilt New York City's admissions process using student-proposing deferred acceptance. Unlisted administrative placements fell by 90 percent, and eighth-grade participation rose to 93 percent. Boston Public Schools soon worked with Roth, Pathak, Abdulkadiroglu, and Tayfun Sonmez to redesign its school choice algorithm as well.

Kidney transplantation posed a one-sided matching puzzle because organs do not rank recipients, and U.S. law has prohibited buying or selling human organs since 1984. Shapley and Herbert Scarf studied cashless swaps in 1974 using David Gale's top trading cycles model for trading indivisible goods.

In 2004, Roth, Sonmez, and Utku Unver adapted cyclic exchanges and chains for incompatible donor-recipient pairs, helping establish the New England Program for Kidney Exchange. Before 2004, fewer than 20 people yearly got living-donor kidneys this way, while roughly 5,500 U.S. patients yearly now get living-donor kidneys. In August 2011, one altruistic donor sparked a coordinated chain of 60 kidney transplants across the United States.

Inside medicine, market design also modernized Match Week and expanded to other professions. In 2012, the NRMP introduced the Supplemental Offer and Acceptance Program, or SOAP, replacing phone, fax, and email scrambles for unfilled residency slots. Meanwhile, Elliott Peranson adapted the Roth-Peranson algorithm for specialty fellowships and other health professions, including clinical psychology.

How Nobel Prize matching designs compare across three markets
MarketCore AlgorithmProblem SolvedMeasured Outcome
U.S. Residency Match (NRMP)Roth-Peranson applicant-proposing deferred acceptance (1997)1940s early exploding offers, hospital bias, and dual-doctor couplesPlaces candidates across more than 40,000 clinical training positions yearly
NYC Public High SchoolsStudent-proposing deferred acceptance (2003)Five-school rank limit, strategic gaming, and 30,000 unlisted placements yearly90 percent drop in unlisted placements and 93 percent student participation
Paired Kidney ExchangeTop trading cycles and donor chains (2004)Blood or tissue incompatibility between willing living donors and loved onesRose from under 20 paired transplants yearly before 2004 to roughly 5,500 living-donor transplants yearly

How the algorithm matters for health program applications and interviews

For residency candidates and applicants to medical, dental, PA, pharmacy, and nursing schools, Match rules shape both ranking strategy and interviews. Beyond the Main Residency Match and more than 70 NRMP fellowship subspecialties, separate matches run for urology and U.S. military programs.

For residency applicants, the algorithm's math governs how you build your Rank Order List in the NRMP Registration, Ranking, and Results system. Standard registration costs $85 and covers up to 20 unique program codes on your primary list and 20 on supplemental lists. Extra ranks cost $30 per code up to 300 ranks, plus $50 to $200 in length fees starting at 100 ranks.

Couples pay an extra $45 per partner, and registering after January 29 adds a $50 late fee. Fellowship Match registration is $70, increasing to $85 for matches opening after January 1, 2027. Every list must be certified with your password before 9:00 p.m. Eastern Time on the Rank Order List Certification Deadline. Certifying creates a legally binding commitment to train at any program where you match.

During residency interviews, program directors judge clinical readiness and fit to build their rank list, since programs do not rank uninterviewed applicants. Under NRMP policy, program directors and faculty are not permitted to ask which other programs you applied to or how you plan to rank them. If someone fishes for a ranking promise, express genuine enthusiasm for specific features of their training without disclosing rank order.

In health school admissions interviews, matching markets appear in policy and ethics stations, like those in our MMI practice questions with answers. Committees test workforce policy knowledge, including the 1997 freeze on Medicare-funded residency slots, with teaching hospitals funding more than 13,000 extra positions. According to the AAMC Report on Residents, 54.2% of doctors finishing residency from 2008 through 2017 practiced where they trained. That link makes residency slot allocation a direct driver of rural and underserved care.

  • Rank strictly by true preference. Put dream reach programs first, followed by realistic matches and at least one safety program.
  • Leave unacceptable programs off your list. Never rank a program where you did not interview or would be unhappy training under a binding contract.
  • Save and re-certify every edit. Changing a certified list requires clicking Certify List again before the 9:00 p.m. Eastern Time deadline.
  • Know NRMP communication boundaries. You may send a voluntary note of interest, while programs cannot ask how you will rank them.
  • Separate sorting from supply in policy interviews. Algorithms match existing seats fairly, whereas solving clinician shortages requires funding new training slots.

How to talk about the Match and resource allocation in an interview

If an interviewer asks about the residency Match, organ exchange, or clinician shortages, skip the abstract game-theory terms. Name the human problem first, such as early pressure on students or incompatible living organ donors.

Next, explain in one plain sentence why a stable, cashless rule protects trust for patients and trainees. Close by naming the practical limit that lawmakers or hospitals must still solve outside the algorithm, as shown in the practice example below.

To practice policy, ethics, and residency fit prompts out loud, Confetto runs AI mock interviews with realistic follow-up questions and rubric feedback. Start your free week.

Practice question

The U.S. uses centralized algorithms with strict ethical rules to allocate medical residency slots and donated kidneys, rather than letting money decide. Where does a system like the Match work well, and what healthcare problem can an algorithm alone not solve?

See an example answer

An allocation algorithm works best when fairness depends on mutual fit or medical need rather than who can pay the most. In residency matching, the deferred acceptance system stops early pressure tactics and lets students rank programs honestly without fear of losing a backup spot. Paired kidney exchange solves a similar problem by linking incompatible donor and patient pairs so more people receive transplants within ethical laws. Still, an algorithm can only sort the slots or organs that already exist. It cannot create new training positions in underserved areas on its own. When I volunteered at a rural clinic two hours from the nearest hospital, patients waited months to see a specialist. Federal Medicare funding for residency slots has been capped since 1997, even though where doctors train strongly shapes where they stay to practice. A fair matching formula makes sure existing seats go to mutual matches, which protects students and hospitals. Fixing rural shortages, however, takes public funding for new community residency tracks and stronger support for clinicians after graduation. Example answer written by our team. The applicant is invented.

It answers both halves of the prompt in plain language without reciting game-theory jargon. First, it explains how centralized matching protects student honesty and organ donation ethics. Then it uses a rural clinic story and the 1997 Medicare cap to separate fair sorting from workforce supply.

Frequently asked questions

Why did the residency match algorithm win a Nobel Prize?

Alvin E. Roth and Lloyd S. Shapley won the 2012 Nobel Memorial Prize in Economic Sciences for stable allocations theory and market design. Shapley co-developed the 1962 deferred acceptance algorithm, and Roth used it in 1995 to redesign the National Resident Matching Program.

Why didn't David Gale win the 2012 Nobel Prize with Lloyd Shapley?

Mathematician David Gale co-wrote the foundational 1962 paper on stable matching with Lloyd Shapley. Gale passed away in 2008, which made him ineligible when the prize was awarded in 2012.

Is the NRMP algorithm applicant-proposing or program-proposing?

The NRMP algorithm has been applicant-proposing since 1997, following the redesign by Alvin Roth and Elliott Peranson. It starts by trying to place you into the first choice on your rank order list, which systematically favors applicants over programs.

Should I rank safety residency programs higher to improve my chances of matching?

No, ranking a less competitive program higher does not improve your overall chance of matching. Because the algorithm is applicant-proposing, if your reach program cannot hold you, the system checks your next choice without penalty.

How does the Couples Match change the NRMP algorithm?

Two applicants can link their rank order lists for an extra $45 per partner so the algorithm evaluates program pairs as one unit. Couples can mathematically eliminate guaranteed stable outcomes, which is why Roth and Peranson built a specialized procedure to process paired lists.

How much does it cost to rank programs in the NRMP Main Residency Match?

The standard NRMP registration fee is $85, which covers up to 20 unique program codes on your primary rank order list. Ranking extra programs costs $30 per code up to 300 ranks, plus tiered length fees starting at $50 once a list reaches 100 ranks.

Sources