Friday, October 26, 2012

How the NRMP Match algorithm works

Are you curious how the Nobel Prize-winning NRMP Match algorithm works? Here's my example highlighting the story of three students:


Students Alice, Ben, and Carlos apply to various numbers of IM programs through ERAS. Alice gets ten interviews, Ben gets zero, and Carlos gets two. Again, the NRMP has no idea how many. Alice has some good and some bad interviews, but decides to rank all programs. Ben ranks a dozen programs that he wants to go to, even though none of them interviewed him. Carlos only ranks one program (which happens to be a program that both Alice and Ben have ranked).

The IM program at Tufts will hire five residents, and ranks fifty applicants who interviewed there. Among other people, it ranks Alice at number 6, Carlos at number 14, and doesn't rank Ben at all (unsurprisingly since they didn't interview him). Alice ranked Tufts at number 4, Ben ranked it at number 2, and Carlos ranked it at number 1.

Match algorithm time. Ben has only ranked programs that don't have him on their lists. No matter how many he tries to rank, there's no possibility of a corresponding match, so he ends up unmatched.

The algorithm tries to match every applicant to their top choice and does not "count" how many programs they actually ranked. If an applicant's top choice has an open slot immediately, the match happens. Because Carlos has 13 people ahead of him at Tufts fighting for those five slots, there's no way that the first iteration will work for him. Alice also fails to match at her top choice (Harvard), and let's say that all of the spots there were instantly filled.

On the second algorithm iteration, Alice's top choice of Harvard is completely blocked. Her #2 choice (Stanford) automatically becomes her new #1...the program will not try to match her at Harvard again because it's impossible. It tries and failed to match her this time, but not all Stanford spots are full, so hope isn't lost yet. Concurrently, the algorithm tries to match Carlos to Tufts. He doesn't get matched this time either, but he's moved up to #12, since one person higher than him near the top of the Tufts list matched to her own top choice somewhere else. Interestingly, Alice is now at #5 on the Tufts list, which means the spot is potentially hers, but the algorithm hasn't tried matching her there yet.

A few algorithm iterations later, and Alice's second choice is full without her matching there, Tufts has matched three people out of five, and all of our heroes are still waiting...though it's just been a few microseconds.

A few more iterations and Alice's third choice (UCSF) is full. Carlos moved up a couple of spots. Tufts has matched its original first, second, and fourth choices, with the third matching elsewhere. Alice and the person originally in the ninth rank now have spots "held" for them due to the original fifth, seventh, and eighth on the list matching elsewhere, and the two of them moving up the ladder.

On the next iteration, Alice matches to Tufts. It's her fourth choice, but it was "virtually" her top choice since the three programs above it filled and she had no chance of matching there. She takes the fourth spot. 

A couple more iterations later and the fifth spot is filled (that man had ranked another program higher, and his spot at Tufts was "held" for him while that other match tried and failed to happen). Carlos is unmatched since Tufts was the only program he ranked. Interestingly, the other program he interviewed at had ranked him quite highly, and he would have matched there if he had bothered to rank it. Ben never had a chance of matching since he didn't interview and no programs ranked him. Both men can try to find a spot through the Scramble/SOAP.

And thus concludes a *very* realistic scenario. The NRMP has their own sample scenario on their website if you want to read it.


My congratulations go out to the creators of the current NRMP Match algorithm, who recently won the 2012 Nobel Prize in Economics! Click here for a short and accessible description of this achievement, and click here for the full journal article about the algorithm's history and development.