IEOR 156/256 Lecture 4: National Residency Matching Program
(NRMP)
Based on slides by Anil Aswani, UC Berkeley
1 Notations & Algorithms
1.1 Definitions
Stability: Matches between applicants and programs are such that no matches can be broken so that a new
match is made where an applicant and program prefers the new match over the broken one.
Strategy-proof (or truthful): Market is strategy-proof it is optimal for the participants to report their
true preferences, or in other words no advantage can be gained by lying about preferences.
1.2 Notations
• Residency programs
– Total of m residency programs
– Denote j-th program as pj
– Let sj be number of open positions in pj
• Applicants
– Total of n applicants
– Denote i-th applicant as vi
• Preferences are a list from most to least preferred
• Preferences in a list are unique (i.e., no ties allowed)
• Preferences of i-th applicant vi
– Suppose ai applicants are ranked by vi
– Ranking list is (pvi[1], pvi[2], . . . , pvi[ai])
• Preferences of j-th program pj
– Suppose bj applicants are ranked by pj
– Ranking list is (vpj [1], vpj [2], . . . , vpj [bj ])
1
1.3 Algorithm (Gale-Shapley)
Let I = (1, 2, . . . , n) be a list
1. While I is nonempty, remove the first element of I
(a) For j = 1, . . . , ai, attempt to place vi into pvi[j]
• If pvi[j] has an empty spot and pvi[j] has vi in its list of preferences, then denote vi ↔ pvi[j]
a tentative match.
• If pvi[j] does not have an empty spot, but there is a “least-preferred” tentative match vk ↔
pvi[j] such that vi is preferred over vk by pvi[j]; then remove the tentative match vk ↔ pvi[j],
add the tentative match vi ↔ pvi[j], and append k to I.
2. Once I is empty, finalize the matches.
2 Example
We illustrate the algorithm in the following example.
Question: Match applicants to residency programs and show intermediate steps of the algorithm.
The applicants’ preferences are given by:
John David Emily Sarah
Hopkins General General Temple
General Hopkins Temple Hopkins
Temple Temple Hopkins General
Each residency program has one open position, and their preferences are given by:
General Hopkins Temple
Emily Sarah Sarah
Sarah David Emily
John Emily John
David John David
Solution:
General Hopkins Temple
David John Sarah
Emily David
Explaination:
Let’s assume you always go from left to right.
For John, it goes to Hopkins which is empty initially. Then David goes to General. Emily wants to go
to General and General currently has David assigned but it prefers Emily so Emily precedes David. Now
David is unassigned. Sarah goes to Temple.
Now, for unassigned applicant David, the second choice he has is Hopkins which has John occupied right
now. But Hopkins ranks David over John so David will replace.
Now John is unassigned, but he cannot replace anyone for his other options. The algorithm terminates.
2