Matching doctors to residencies and the Gale-Shapley algorithm
The 2012 Nobel Prize in Economic Science was awarded to Alvin Roth and Lloyd Shapley for their work in matching markets and stable allocations. Their work has been a great contributor to the development of the NRMP. The NRMP (National Residency Matching Program) is used to match fresh medical graduates to the optimum residency position. Prior to the development of the new theory, the NRMP used the Gale-Shapley algorithm, originally designed in the 1960s, employing concepts of game theory for the matching process. The Gale-Shapley algorithm as applied to the residency matching situation is as follows:
- Initially, all doctors rank hospitals based on preference, and the hospitals do the same with doctors.
- Each doctor presents an offer to his/her first choice.
- If any hospital has multiple offers, the hospital chooses its first choice and rejects the rest.
- Each of the rejected doctors then presents an offer to his/her next choice.
- Go back to step 3 and continue.
- The hospitals pick their first choice and the rejected men continue presenting offers to their next choice until every doctor is matched up to a hospital.
The same algorithm can be applied to hospitals presenting offers to doctors as well. However, Roth’s adaptation of the algorithm took into account the fact that applicants can lie about their preferences to achieve a better outcome. For example, a doctor could deliberately rank a third tier hospital as his/her first choice to guarantee at least one match because the third tier hospital will have fewer offers. Roth, through his theoretical papers, showed that student misrepresentation can have a great effect on the overall process.
Additionally, the previous implementation of the NRMP could not accommodate couples trying to get residencies in the same area (part of misrepresentation) and was also heavily criticized for favoring hospitals over doctors. Following the development of this theory, Roth, with the help of Elliott Peranson, worked on tweaking the algorithm for more accurate matching results. This algorithm is now used to match medical students to residencies all over the United States.
LINK: http://www.nobelprize.org/nobel_prizes/economic-sciences/laureates/2012/popular-economicsciences2012.pdf