In 1952, the National Residency Program (NRMP) was established as a non-profit organization to match medical students and residency programs. However, by the 1990s, the system was under serious strain. With thousands of students attempting to match across dozens of specialties and thousands of residency programs, there was concern that hospital preference was favored over that of applicants’. Further, more applicants were trying to match as a couple, something the current system could not handle, causing students to opt out of the process. The NRMP hired Al Roth to design an algorithm that would lead to more desirable outcomes and encourage applicants to opt into the process.
Today, the NRMP uses Roth’s adaptation of the Gale-Shapley algorithm to produce “stable” matches, that ultimately favor applicants. It considers their preferences first, then the hospitals’. It also can do joint matching for couples. Beyond residency programs, this algorithm has applications from matching students to public high schools in NYC and to organ donor matching. In 2012, Alvin Roth and Lloyd Shapely won a Nobel Prize in economics for the algorithm’s application across markets that require choice from both sides of the market, and where price is not a factor.
The algorithm works by having both students and hospitals rank their preferences after an interview process. Both applicants and hospitals simultaneously submit their preferences in rank order. Then, the algorithm considers the first student and determines if that student has ranked a given hospital, if not, it moves on. If she has ranked the hospital, then the algorithm determines if the hospital has ranked the student. If so, then they are “tentatively matched”. The algorithm goes to the second student, looking at the same hospital. If it is a mutual match, then it determines 1) if the hospital has a spot remaining and 2) if the ranking is higher or lower than the previous student already “tentatively matched”. If higher than the previous match, then the previous match is demoted. If not, and all spots are filled, then the algorithm considers the student’s second choice. This process occurs across dozens of specialties, thousands of global applicants and thousands of residency positions.
In 2017 Match, 30,478 students matched, or ~71% of registrants, an all-time high. Unfilled positions were placed in the Match Week Supplemental Offer and Acceptance Program, ultimately leading to a 99.4% fill rate. Couples are increasingly satisfied with the new algorithm – 95.4% matched in 2017. The previous methodology would not have been able to handle this volume and level of complexity at this speed, about 17 seconds. Literature exists to refine the algorithm, but there are no commercially viable alternatives as most agree with the “stable marriage” approach to this process. Considering how adaptable the algorithm is, it is unlikely any competing approach will exist in the short-term.
The process is imperfect. Both students and hospitals attempt to influence the other party’s rankings by over-embellishing their true preferences. Trust in the process and concerns about whether applicant preferences are taken into account remain.
To maintain trust, the NRPM is not currently changing the algorithm. However, there are other methods of engendering trust – such as continuing data transparency. In not adjusting the algorithm, the NRMP loses any opportunity to improve upon it. Significant time and money is also spent in the interview process itself.
This algorithm could be expanded to other industries that have many companies with similar offerings targeting a specific pool of candidates. Example industries are investment banking, consulting, and law. This process could also expand globally, for example NRMP has licensed the algorithm to the Canadian Resident Matching Service. It also could be used for other professions such as matching law students to firms, though Dr. Roth indicated this only would work if there was a demand for a market to be created.
This type of algorithm could be used in any two-sided market with uncomplicated preferences (firms or people or a combination of both) and where money is not a deciding factor. Evolving the algorithm to handle complicated preferences is necessary to further commercialize to other markets where price is not a reasonable arbiter to set supply and demand.