The NRMP Match Algorithm
Matching algorithms are widely used in many applications. One of which is the NRMP Match. This algorithm uses rank order lists submitted by applicants, who are medical students, and medical residency programs listing their preferences of programs and applicants respectively. Initially, each applicant is matched with his or her first-choice program. If the program does not also prefer the applicant, the applicant is then matched with the second-choice program. This process is repeated until the applicant ends up with their “tentative match” or the applicant doesn’t have any choices left. This results in a set of applicants who have been tentatively matched who fall into two conditions: 1. The applicant (Applicant A) is matched to a program that has space to add him or her or 2. The program does not have space for Applicant A. In the second case, if a different applicant (Applicant B) that has been matched with the program is less preferred, then Applicant A would replace Applicant B. When Applicant B is displaced, the algorithm makes another pass through his or her rank order list and attempts to re-match the applicant [1,2].
This problem can be arranged as a bipartite graph where one set of nodes represents applicants, and the other group represents residency programs. However, there is a slight modification to the auction-based matching covered in class. This is because, in this case, both the programs and the applicants have valuations for the members of the other group. In this set up, the objective is to create a “stable” matching. This refers to a matching in which there are no applicant-program pairs in which both the applicant and program prefer to be matched with each other more than to the match they are assigned by the completion of the algorithm [3].
The dominant strategy is for both applicants and programs to submit their true preferences in their rank order lists. Under the current Match, this means that applicants are guaranteed to be matched with the most preferred residency program available. Also, 99.9% of residency programs get optimal results. However, there are various reasons for both applicants and programs to create dishonest rank order lists. Applicants may be advised to create realistic ranked lists such that they rank programs they think they’re more likely to be admitted to higher. This may lead them to match into less preferred programs. On the other hand, programs are incentivized to rank students they think prefer their program higher. This results in programs receiving a less preferred student. This is a symmetric case to the applicant’s dishonest rank order list. It could be mitigated by having programs submit their rank order list of applicants before they communicate with applicants and judge whether applicants prefer their program [4].
- https://www.nrmp.org/intro-to-the-match/how-matching-algorithm-works/
- https://www.ou.edu/tulsa/community_medicine/currrent-students/current-students/guidetothematch/how-the-nrmp-works-
- http://stanford.edu/~alroth/jama.html
- https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3399603/#i1949-8357-4-2-142-Roth2