The fates of thousands of med school students are decided by this Nobel Prize winning algorithm

If you or anyone you know is a senior in medical school, then you know about The Match- the day when graduating doctors are assigned to residency programs by the National Residency Matching Program.

Pairing up applicants to programs is rarely an easy task.

In many situations it is impossible for everyone to be happy. If a residency program has two spaces open, and is the top choice of three applicants, at least one of those applicants is out of luck.

The goal is to come up with some matching between applicants and programs that, in a fair way, makes everyone as happy as possible. The matching program has an intriguing process to achieve this goal.

The Basics Of The Matching Algorithm

The first step in the process is for medical school seniors to apply to various residency programs. After the initial application process, programs interview a number of applicants.

After the interview process, applicants make a list of the programs they interviewed with, ordered by preference. Similarly, programs make a ranked list of interviewed applicants, also ordered by preference.

The key concept is that of a "stable" matching, in which we avoid the following situation. Suppose Alice is assigned to Beth Israel, and Bill is assigned to Lenox Hill, but Alice would rather be at Lenox Hill, and Lenox Hill would rather have Alice than Bill. This matching is "unstable" because Alice and Lenox Hill can cooperate to both improve their situations - Alice can leave Beth Israel, and Lenox Hill can kick out Bill and take in Alice, making both Alice and Lenox Hill happier.

The basic algorithm used to make a matching between applicants and programs is fairly straightforward. An applicant - Alice - starts by applying to her first-choice program. There are three possibilities: the program has an empty space, the program is full but prefers Alice to at least one other applicant it's already tentatively accepted, or the program is full and ranks Alice lower than all the applicants it has on its current acceptance list.

If the program has an empty space, Alice is tentatively accepted.

If the program has already filled all its spaces, but ranks Alice higher than the lowest-ranked applicant it has tentatively accepted - Bill - the program kicks out Bill, and tentatively accepts Alice, with Bill going back to the pool of unmatched applicants.

In the final case, where a program is full and ranks Alice lower than all its tentatively accepted applicants, Alice moves on to her second-choice program, and repeats this process.

This continues until all the applicants are either tentatively matched up with a program, or they have applied to and been rejected by all the programs on their ranking lists. Once this happens, all the tentative matchings become official, and this gives us the actual matching of applicants to programs.

It's A Pretty Good System

The matching that results from this algorithm is stable - there is no program and applicant that are not matched with each other, but would prefer to be matched. Even better, this matching will lead to the best overall outcome for applicants - there will be no other stable matching in which an applicant is at a program they have ranked higher.

This algorithm works very well for a simple market. The actual residency market is slightly more complicated - sometimes couples will make joint ranking lists to make sure they are in the same city, and some applicants are applying to programs for their second year of residency. These special cases have to be treated separately by the algorithm. However, for the vast majority of applicants, the above process works very well to match applicants to programs.

The matching algorithm is so important to residency assignments that the researchers who developed it - Dr. Lloyd Shapely, who came up with the basic algorithm described above, and Dr. Alvin Roth, who refined and modernized the specific algorithm used by the residency matching program - won the 2012 Nobel Prize in Economics for their work.