University of Vermont

The Matchmakers

Chris Cahill, Class of 2013

Thank goodness for the Match.  As medical students from Vermont to Vegas took deep breaths and crossed their fingers after certifying their rank order lists on February 20th, I hope they remembered to thank their lucky stars that they were asked to make a rank list.  Fourth year students have not only benefitted from the work of a myriad of doctors, students, and staff at the National Residency Matching Program (NRMP), but also from clever mathematicians, economists, and even Ralph Nader (though just for a little bit).

The Main Residency Match (known as the Match) is the clearinghouse in which student preferences from a 16,000 US senior allopathic students and 15,000 osteopathic, Canadian, and foreign medical graduates are matched to residency preferences for the 24,000 available US residency positions.  It is also the practical application of what is known as the “stable marriage problem” by game theorists.   If you are like me and the approximately 60% of the class of 2013 currently in a committed relationship, the mathematical moniker has a certain ironic weight that underlies the solution’s importance.

As explained by Harvard mathematics PhD student Emily Riehl in an excellent 24-minute YouTube video on the subject, the goal is to create “marriages” (or matches, when applied to residencies and students) that are stable.  This means that after everyone is assigned a “mate”, there are no other potential pairings available that any man and woman (or a medical student and residency) would prefer more than the one they are assigned.  As a side note, the stable marriage problem requires marriages between a man and a woman not as a social statement, but because of a need to match unlike groups.  Allowing for man-man or woman-woman partnering actually makes the problem much more challenging (see the “stable roommates problem”).

To put a stable “marriage” in an example, say two matches are created: Alvin at Johns Hopkins and Bob at Stanford.  These matches are unstable if Stanford wanted Alvin first and Alvin wanted Stanford first.  If these unstable marriages or ”blocking pairs” occur, the assumption is people would take themselves out of the market and “elope” with programs of their choosing.  This type elopement, driven by loss of trust in the market, is precisely why the Match was started in the first place.

The Match began in 1951 after a “market failure” ended the previous system of decentralized matching that worked similarly to the college admissions process today, but with far worse results.  In order to get the best students, programs were driven to “lock down” potential residents earlier and earlier.   Programs that waited for students to be farther along in their training would find the most desirable students already gobbled up by faster-acting programs.  Students that waited would find all spots filled in competitive residencies.  As a result, residencies often asked students to sign committing contracts at the end of their 2nd year of medical school.  This made residencies and students gamble with their choices, hoping their decisions made off of limited information would pay off 2 years later.

When I try to imagine what this would be like for me, I think of the end of my second year, when I grappled with the decision between surgical subspecialties and medical ones.  This choice was embryonic compared to decision to apply to Pediatrics residencies over a year later and the rank order list I submitted a couple weeks ago.  If I was asked to sign a contract at the end of my second year, I fear I would have been making a career-defining decision based on a wild guess.

Back in the pre-Match era, the strain of making the right decision quickly changed the way students and residencies found each other.  Both groups increasingly chose to circumvent the slower apply-and-interview market and instead turned to personal connections to make matches.   The more the old market was circumvented, the less value it had, further reinforcing the need for people and programs to leave that market.  In addition, because students were forced to make decisions so quickly by binding contracts, many students broke their contracts when the received offers from more preferred residencies.  This old market had failed, and from this the Match was born.

The solution to the stable marriage problem - and the basis for the Match - is also known as the Gale-Shapely problem for the mathematicians who first solved it.  The simple version of algorithm is written below, and it is a close approximation of the more complicated Match, but does not include couples matching or supplementary decision making.

(1) Both residencies and medical students make rank order lists.

(2) Every medical student “proposes” to their top choice.

(3) Every residency tentatively “accepts” all of the “proposals” they have space for.

(4) If a residency has more “proposals” than spaces, they reject their least favored proposals until they have the appropriate number.

(5) All medical students who are not tentatively accepted “propose” again to their next highest choice.  This cycle repeats until every student has either been matched or has been rejected from every program on their match list. *

In the end, this algorithm does some amazing things.  First, it terminates – it does not get caught in loops or runs on infinitely.  Second, all matches are indeed “stable”.  Third, every student has their best possible stable match.  Fourth – and this was not known until decades after the original theorem was published - the residencies get their worst possible stable match.

The key to who gets their best possible stable match and who gets their worst possible stable match is who proposes.  The proposers always get their best possible match in a simple matching problem, and are favored to get their best possible match in a complex matching problem like the Match.  The very boiled down explanation for this is that there are many potential stable marriage configurations, and since the proposers start at the top of their list and work down and the acceptors start low on their lists and work their way up, the first configuration they will come to is always the best possible for the proposer and the worst possible for the acceptor.

When this became well known among medical students in the 1990s (~20 years after it was proven mathematically), it caused a great uproar among students because in the 4 decades since the Match’s inception, the residencies were the proposers.  As a result, some savvy students were changing their ranking behaviors to try to game the system.  One way students could do this was by ranking less-preferred programs higher than highly competitive but preferred ones.  This would cause the applicant to make a rejection they would not have made if they ranked their true preference.  This untruthful rejection would create a vacancy, which would lead to another student getting into that program, which would create another vacancy and so on and so forth.

The propagation of this “vacancy chain” could potentially lead to the point when the untruthful applicant could receive a proposal from a residency that he would not have received if they were truthful in their rank order list.  Though the chances of successfully implementing this strategy were relatively low, and such behavior had the potential to harm applicants, it still generated confusion and anxiety among students, and graduate advisors began noting increasing number of students who tried to doctor their rank order lists to game the system.  This, coupled with the realization that the Match at that time benefited residencies rather than students, prompted a large student outcry.

AMSA, the AMA-medical student section, and even Ralph Nader, consumer advocate and the often third-party presidential candidate, pushed the NRMP to change their matching algorithm.  Their arguments focused on the difference in welfare for a student matching lower versus residencies.  One lower match rank for a student might mean moving across the country or living far from supportive family and friends, whereas one lower match rank for a residency often meant little change.  The NRMP, remembering the loss of confidence in the market that led to the Match’s existence in the first place, listened very carefully.

Enter Alvin Roth and Elliott Peranson.   Their task was to change the Match to favor students while maintaining changes that had been made in the ‘80s (which included couples matching and second year programs) that made the Match a very complex market.   They were responsible for creating the “Applicant-proposing algorithm” that favors students over programs.  They detailed their changes and a comparison to the existing Residency-proposing system in a wonderful paper published in 1999.

When Roth and Peranson ran their Applicant-proposing algorithm against the old NRMP algorithm, their effect size turned out to be small.  Only 0.1% of students (14-21 per year) were affected by their changes.  Only 0.5% of residencies (15-23) were affected as well.  For the students, most received better matches under the Applicant-proposing system.  The opposite was true for the residencies in 3 of the 5 years the comparisons were run.  For students, the magnitude of this change was relatively small, with most only changing 1 rank with a maximum of 9 ranks.  For residencies, differences in rank were also most often small; most changes were less than 16 ranks, but could be as high as 191.

Though this may seem like a bum deal for residencies, remember the earlier protest revolved around how a residency could cope with a lower-ranked match more easily than a student.  Roth’s Applicant-proposing algorithm was soon accepted by the NRMP and the first Match using the new system took place in 1998.  With the exception of a failed law suit in 2002 claiming the Match allows hospitals to keep resident and fellow wages low and therefore is a conspiracy in violation of the Sherman Antitrust Act, the newest version of the Match has been well-accepted and has been adopted by over 3 dozen other labor markets.

While the applicant-proposing system created a small but potent improvement for applicants, the switch dramatically changed how students make their rank lists.  Students today can be safely advised to rank in the order of their true preference, listing as many programs as they want.  The alterations in medical students made to their rank lists in the early 1990s are no longer the best strategy, and the confusion surrounding how to make a best possible rank order list is much improved.  Though Roth and Peranson admit there are still ways to game the system, the opportunities are more rare and far more difficult to execute.

Interestingly, the same is true for programs.  Roth and Peranson noted that if a residency wished to game the system successfully, the programs must have perfect knowledge of all applicant and residency rank lists or risk negative consequences.  Even if residencies were to have a perfect knowledge of all other rank order lists, Roth and Peranson, through some complicated logic and math that I must admit I do not fully understand, showed the Applicant-proposing system had  similar or fewer numbers of residencies that could benefit from “strategic maneuvering”.  In the end, because of the uncertainties and risks inherent to strategic maneuvering, it appears that residencies are best off if they rank what they truly feel.

If you’re reading this article and are starting to feel like you should have been writing thank you notes to Mr. Roth, Peranson, Shapely, and Gale (and maybe Nader), you are not alone.  Besides the many other labor markets using the same algorithm as the Match, similar algorithms have been developed by Roth and other game theorists to help clearinghouses involving outcomes that are either invaluable or that have an extremely high value.  One such example is for organ transplant, which work very similarly to couples matching in cases involving chains of donations.  The best example of this is one that allowed 60 patients and 30 kidneys to be transplanted thanks to matching algorithms like the one used by the NRMP.

But before you break out the leftover residency application thank you notes, you should know that at least Roth and Shapley (the man who first solved the “stable marriage problem”) have received very public recognition for their work.  Both men were awarded the Nobel prize in economics in 2012.  For all that it is worth, I think that was certainly well deserved. 


* The additions to the more complicated NRMP algorithm that allow for couples matching and supplementary positions are as follows:  In the case of couples matching, if a student who is couples matching is “rejected”, then their partner is also “rejected” from that program, and they propose to the next combination on their list.  In addition, various “loop detectors” are built into the system because when complex additions like couples matching and supplemental positions are added into the system, the algorithm could get locked in a never-ending cycle.  When loops are found, they are resolved by randomizing which students are added into the algorithm when or by more in depth review if that does not solve the problem.  Unstable matches are also possible under complex conditions but are “very rare” according to Mr. Roth’s paper.  I am not sure if the NRMP has a system in place to deal with this.  For those of you who watched Emily Riehl’s video and made it to the unsettling part where she talks about how the NRMP match is NP-Complete when couples matching is involved, this is how the NRMP algorithm deals with such issues.