In Part 1 of this series, I reviewed the early history of the Match and explained how this unusual system evolved. Now, it’s time to get under the hood and see exactly how the residency matching algorithm works.
Fair warning – I’m going to take my time getting there.
See, I had originally envisioned that Part 2 would be a short post covering the nuts and bolts of the NRMP’s algorithm. But in researching this topic, I discovered two fascinating stories that have largely been swept under the rug. So instead of a quick hitter, you’re gonna get a sprawling historical perspective on how – and why – the NRMP’s matching algorithm has changed over time.
First, we’ll cover the original matching algorithm; how it encouraged students to game the system; and the largely-untold story of the medical student rebellion against the Match. Then, in Part 3, we’ll review why the NRMP was forced to change its algorithm again – and finally discuss how matching works today (and whether it’s possible for students to outsmart the current Match algorithm when submitting their rank lists).
When playing matchmaker, the devil’s in the details
In theory, it should be easy to match up applicants with programs, right? You just pair up parties that like each other, and everyone goes home happy.
Of course, the devil’s in the details.
Unless the preferences of applicants and programs are perfectly aligned, someone’s not going to go home happy. (And if their preferences were perfectly aligned, there wouldn’t be any reason to have the Match in the first place.)
The rules used to do the matching matter – and establishing those rules requires both mathematical logic and a value judgment about whose preferences should be favored when desires conflict.
The original matching algorithm
Joe Mullin – the former dean of students at the University of Chicago – came up with the original Match algorithm in 1951. His method was designed to optmize the number of students and programs who both ranked each other #1.
The original Mullin-Stalnaker matching algorithm, from J Med Educ 1951; 26: 341-346. PubMed
As shown above, the system would first Match up all pairs of hospitals and students who had each other ranked at the top of their list (so-called 1-1 matches). Then it would move on to match hospitals’ second choice with students’ first choice (2-1) matches, then to 1-2 pairings, 2-2, 3-1, 3-2, 1-3, 2-3, etc.
Seems fine, right?
Yet from a student’s standpoint, this algorithm is not ideal. When inspected carefully, it becomes clear that assigning matches in this way has the unintended effect of penalizing a student who ranked a “reach” program at the top of their list.
To see why, imagine a situation in which there are three applicants (Students A, B, and C), and three hospitals of varying prestige/desirability (Ivy League Memorial, State U Hospital, and Community General). To keep things simple, let’s assume that each hospital can match only one student.
In this example, I want you to focus on Student B.
Student B is a solid candidate. He thinks he’ll probably match at State U Hospital – but he dreams of training at Ivy League Memorial. He doesn’t really want to match at Community, but figures it’s better than not having a residency at all. So when it comes time to rank programs, he lists puts Ivy League #1, State U #2, and Community #3.
Under the Mullin-Stalnaker algorithm, Student B’s decision to rank a selective program #1 is about to blow up in his face.
So let’s run the algorithm and see what happens.
In round 1, we look for 1-1 matches. There is one – Ivy League Memorial and Student A both ranked each other #1, so they’re matched.
In round 2, we look for 2-1 (hospital-student) matches. Again, we find one – Student C and State U Hospital. So now they’re matched.
In round 3, we look for 1-2 pairs – but there are none to be found. Same goes for round 4 (2-2), round 5 (3-1), round 6 (3-2), and round 7 (1-3). Finally, in round 8, when we search for 2-3 matches, we pair up Student B with Community General.
Whoa.
Matching at Community was Student B‘s last choice. He would have much preferred to match at State U.
And in fact, State U would have preferred Student B to the match they got (Student C). In other words, beyond the fact that it penalized applicants who rank “reach” programs #1, the match assigned by the Mullin-Stalnaker algorithm is unstable – students and programs have an incentive to make deals with each other outside the match, because both parties can get an outcome they prefer to the one the algorithm assigns.
Unsung Hero of the Match, #1
Fortunately, when the match plans were shown to medical students in 1951, these flaws were recognized by a Harvard medical student named W. Hardy Hendren, III.
Dr. Hendren went on to have an illustrious career as a pediatric surgeon, but in 1951 he was just a fourth-year medical student.
In October of 1951, Hendren’s dean, George Packer Berry, gave the fourth year class a lecture on how the upcoming match would work. After working through the algorithm in his head, Hendren recognized the problems noted above and strode to the blackboard to demonstrate how the Mullin-Stalnaker algorithm could disadvantage students who submitted an honest rank list.
The dean was not impressed.
Berry grew visibly angry. As President of the AAMC in 1951-1952, the year of the first intern match, the dean was invested personally in its success. Flawed or not, the plan had been accepted by medical schools and hospital associations. It had taken hundreds of hours of committee work, countless long-distance telephone calls, and a budget of $100,000 – almost $1 million in current value. It was simply too late to make changes in the plan for the upcoming year.
Nevertheless, Hendren persisted. He asked for a show of hands. “Is there anybody in the room who does not agree with what I just said?” he asked – they all did.
It was too much for Berry: “I don’t care if any of you get an internship,” he hissed and stomped out, slamming the door.
–Nakayama DK, Hendren WH 3rd. Surgery 2017; 161: 1728-1734. PubMed
Later, Berry would explicitly threaten Hendren that he would not graduate from medical school if he caused the Match to fail. But Hendren was undeterred, and moved quickly to mobilize students against the Mullin-Stalnaker algorithm.
In just a few weeks – and working without the benefit of the internet or social media – he convened a meeting that included representatives from over half of all medical schools. Together, Hendren and the students worked out an alternative matching algorithm known as the “Boston Pool Plan.”
The Boston Pool Plan was a deferred acceptance algorithm, in which a student was tentatively assigned to a hospital until or unless the student got matched at one of their higher choices.
The algorithm suggested by the students, and later implemented by the NICI (later known as the NIMP/NIRMP/NRMP). Google Scholar
If we re-run the rank list using the students’ algorithm, the results turn out differently.
As shown above, we start by looking for 1-1 matches. There’s one: Student A and Ivy League Memorial.
Next, we look for 2-1 matches. Again, there’s one. Student B ranked State U Hospital #2, and they ranked him #1.
In the next step, we look for 3-1 matches. There are none, so we move on and to the hospital’s second choice (1-2, 2-2, and 3-2 matches), and eventually on to the hospital’s third choice. There, we finally get a hit at the 3-3 position, and match up Student C with Community General.
Not only are the matching results different, they’re different in an extremely important way.
See, unlike the Mullin-Stalnaker algorithm, the students’ plan produced stable matches. (As suggested above, a stable outcome means that there is no pairing of a student and a hospital that both prefer another pairing to the one that they received in the match.).
Still, the National Interassociation Committee on Internships (NICI; today’s NRMP) refused to change their algorithm.
First, they claimed that it was impossible to set up a computer program to run Hendren’s algorithm. Hendren called BS – he had already tested his algorithm using punchcards on the accounting computer at Massachusetts General Hospital. It worked just fine.
So the NICI leadership eventually agreed to meet with Hendren – with the goal of convincing him to go along with their plan.
Thing was, before he went to medical school, Hendren had served in the U.S. Navy during World War II. He was no pushover, and he was not going to compromise.
The meeting started with a lot of foolish talk. The gist of it was that it was too late to change the plan. “After all, there is no way we can change the mechanics of the plan. We would consider it for the following year, but we’ll have to proceed the way it is.”
I said to them quietly and slowly, “If you don’t change the plan, it will be the end of it. I have votes from 95% of the students in the country. The vast majority will go along with the plan only if the obvious mechanical changes that we have proposed are made. These same students have said they’re going to bolt if you don’t change the plan. We’re not going to sacrifice our futures because of the errors you all have made in setting up this plan the way that you have.”
W. Hardy Hendren, III, quoted in Surgery 2017; 161: 1728-1734. PubMed
Sensing what they were up against, the NICI leadership gave in and agreed to implement the students’ algorithm for the 1952 match.
I highlight this story because it’s at once both amazing and disheartening. To recognize that courageous medical students have – at least in the past – overcome corporate stonewalling, foot-dragging, and outright obfuscation to change systems for the better is inspirational. And yet, it’s hard to imagine a repeat against today’s more deeply entrenched bureaucracies (think #EndStep2CS).
Meanwhile, in the world of mathematics…
Around this same time, mathematicians had been working on puzzle called the Stable Marriage problem.
The idea was simple. Suppose you have a certain number of men and women who want to be married, but they have different preferences among their potential partners. Is there a way to pair them up so that there is no pairing of men and women that would be preferred to the pairing assigned?
In 1962, mathematicians David Gale and Lloyd Shapley solved the Stable Marriage problem.
The seminal Gale-Shapley paper has been cited >6000 times and resulted in the 2012 Nobel Prize. (They didn’t know that a group of medical students had found a solution to the Stable Marriage problem a decade before.)
Gale and Shapley were completely unaware of the residency match. They described their work as “mathematical make-believe” that might one day be applied to college admissions.
But after decade of lecturing on the topic and having audience members ask him about the residency match system, Gale finally wrote a letter to the NRMP to inquire whether the NRMP’s algorithm was the ‘optimal’ solution as presented in his 1962 paper.
Correspondence from mathematician David Gale to the NRMP, 1975.
One month later, Gale received a response.
The NRMP’s algorithm was indeed the same as the one proposed by Gale and Shapley… but with one little difference. That difference would spark a 20 year struggle to change the matching algorithm – and will form the basis of Part 3 of this series.
You may also like:
The Match, Part 1: Why do we have a Match?
The Sheriff of Sodium 