Understanding The Match

As I’m personally preparing to participate in The Match this coming fall, I wanted to learn more about how process actually works. For those that are unfamiliar, the Match is where medical student applicants apply to different training programs for residency and then rank programs based on their interest. Similarly, programs rank the applicants that they’re also interested in. Using these “rank lists,” the National Resident Matching Program (NRMP) assigns applicants to residency programs. Given how high-stakes this whole process is, there have been a lot of resources that help explain how it works; for example, check out this Youtube video or this Reddit thread.

If you’re like me though, you might feel that some of these resources might be a bit “hand-wavy.” To better understand exactly how the Match works, I wanted to see if we could implement it as a computer program.

The NRMP is fundamentally a (highly sophisticated, optimized) variant of Gale and Shapley’s deferred acceptance algorithm from 1962, extended by Al Roth and Elliott Peranson in their 1999 redesign of the algorithm. (Roth would later share the 2012 Nobel Prize in Economics in part for this work). In this article, I’m hoping to dive into the C implementation of their algorithm. For those that want to jump straight to the source code, here’s my GitHub repo to explore.

Each year, the Match can be defined by a finite set of applicants and a finite set of residency programs. Each residency program has some integer capacity that limits how many applicants it can accept; for example, a program that takes 10 first-year residents each year would have a capacity of 10. In the Match, each applicant submits a ranked list of programs they would be willing to attend, and each program submits a ranked list of applicants they would be willing to accept.

The goal is to produce a matching: an assignment that pairs each applicant with at most one program, and each program with at most as many applicants as its capacity allows. A lot of possible matchings exist; for example, we could trivially “match” everyone to nobody and return all unmatched, or randomly assign people to programs that ranked them.

Why don’t we just give everyone their #1 choice and call it a day? The hard part is that applicants and programs have competing preferences. Two applicants might rank the same program first, and two programs might both want the same applicant. This begs the question of how we can define a “good” match.

Roth and Shapley proposed that a good match is fair as defined by the notion of the stability of a match. Formally, a matching is unstable if there exists some applicant a and some program p such that both of the following statements are true:

1. a would rather be at p than where they’re currently matched; and

2. p would rather have a than at least one of the other applicants they currently have (or p simply has an open slot).

This makes sense - in such a scenario, we should have just matched applicant a at program p since there’s nothing logistically stopping us and both the applicant and program prefer this counterfactual scenario. This pair (a, p) is called a blocking pair.

Our goal is ultimately to find some matching where no blocking pairs exist. We call this a stable matching: every applicant is at the best program that wants them given everyone else’s preferences. Gale and Shapley proved in 1962 that a stable matching always exists, regardless of what the preferences look like.

Now that we know a stable matching exists, how can we actually find it? This is where the Roth-Peranson algorithm comes in - it’s a method that takes applicant and program rank lists as inputs and produces a stable matching. At a high level, the algorithm is as follows:

1. Every applicant “proposes” to their top-ranked program.

2. Each program looks at its current proposals. If a program is under capacity, it tentatively holds all of its proposals. If it’s over capacity, it tentatively keeps its top-ranked applicants up to its capacity, and rejects the rest.

3. Rejected applicants propose to their next-ranked program.

4. Programs again tentatively hold their top-ranked applicants. This includes any new proposers, who can displace previously-held applicants if they rank higher.

5. Repeat steps 1-4 until nobody is being rejected anymore.

The “deferred” in “deferred acceptance” is the key idea: programs never commit to an applicant until the algorithm terminates. They just keep their best options on tentative hold while applicants continue to propose. This means a program can always upgrade if a better applicant comes along later in the process. In C, this core logic looks like the following:

Our implementation maintains a queue of applicants. For each applicant a, we get their next preferred program on their rank list using the get_next_preference() function, and then attempt to place that applicant at that program. This placement attempt results in one of two scenarios: either

1. place(p, a, &displaced, match) succeeds, meaning a has been successfully placed into the program. This means that another applicant might have been displaced in the process; if that’s the case, we place the applicant displaced back into the queue.

2. place(p, a, &displaced, match) fails, meaning a was unable to match into their preferred program p. In this case, we place the applicant a back into the queue to try to place them at a different program further down on their rank list later on.

This place() function itself is similarly direct: walk through the program’s currently-held applicants, find an empty slot or the worst-ranked current match, and decide whether to accept or reject the new proposer based on rank. Check out our implementation here if you’re interested.

One thing that struck me was that the algorithm doesn’t require any particular “cleverness” such as priority queues, graph algorithms, or other fancy optimization techniques that one might expect with your typical matching problems. The whole thing is just a careful bookkeeping exercise around proposals, tentative holds, and displacements. This is partially why our core implementation only requires a few lines of C above.

Some cool things that I noticed while writing this implementation:

• The algorithm is guaranteed to terminate. Each applicant’s proposal pointer only ever moves further down their rank list. Every iteration, somebody either gets newly placed or moves further down their list. Because we assume that both applicant and program rank lists involve strict total orderings (i.e., no two applicants or two programs can be ranked “the same” by any program or applicant, respectively), there are only finitely many proposals possible, so the algorithm has to finish in finite time.

• The algorithm is guaranteed to propose a stable matching. Suppose at the end, some applicant a would rather be at program p than where they ended up. By construction, a must have already proposed to p at some earlier iteration (since a proposes in rank order). Furthermore, p must have rejected a - which means p was holding applicants ranked higher than a. Programs only ever upgrade, so p still holds applicants ranked higher than a at the end. Therefore p doesn’t actually want a over its current matches, meaning we have a contradiction and (a, p) is actually not a blocking pair.

• The algorithm is applicant-favoring. This is the part that’s probably most relevant to applicants. There are two versions of this algorithm: applicant-proposing and program-proposing. Both produce stable matches, but they don’t produce the same stable match. Roth showed in his 1986 paper that the applicant-proposing version produces the applicant-optimal stable matching, which is the matching where every applicant gets the best program they could possibly get under any stable matching. The program-proposing version is correspondingly program-optimal, which might be non-optimal for applicants.1

The actual NRMP algorithm has two important factors that I didn’t include in our toy implementation:

1. Couples matching: Real applicants who match as couples (e.g., medical school partners who want to train in the same city) submit a joint rank list of program pairs, and have to be placed together or both go unmatched. Adding couples to deferred acceptance is much harder than it sounds - in fact, Kojima, Pathak, and Roth (2013) showed that with couples, a stable match is no longer guaranteed to exist. The actual NRMP algorithm uses a heuristic that works in practice the vast majority of the time, but is not theoretically guaranteed to find a stable match (or even any match at all).

2. SOAP: After the main match ends, NRMP runs a Supplemental Offer and Acceptance Program (SOAP) where unmatched applicants and unfilled programs negotiate directly in real time. SOAP doesn’t run on deferred acceptance; it’s much closer to a regular job market with rolling offers. Our implementation just stops after the main match, leaving any unmatched applicants unmatched.

There are also some implementation choices in my C code that aren’t optimal. For those that are interested in the specifics, I do a linear scan through applicants to look up an applicant by UUID, which means the worst-case time complexity ends up scaling with the product of the total number of proposals across all applicants and the total number of programs. Using a hash map improves this time complexity to scale only with the total number of proposals across all applicants. I mostly chose the former because I think it’s easier to understand from a code-reading perspective.

For most physicians, The Match is something that happens to us, not something we have to think about. But the design of the algorithm has substantial downstream effects on how applicants strategize, how programs build their rank lists, and ultimately how trainees end up where they do.

Echoing many other sources across the Internet, although now equipped with the technical knowledge to back this up, the most important practical takeaway from the algorithm’s design is that the applicant-optimal property means you should always rank programs in your true order of preference. There is no strategic benefit to ranking a “safety” program above a “reach” program, because the algorithm is designed to give you the best program that wants you out of all stable possibilities. Gaming your rank list by ranking programs in some order other than your honest preferences can only ever hurt you.

I also think there’s something quietly remarkable about the fact that a process so consequential to so many people rests on an algorithm that fits in a few hundred lines of code. The math is beautiful, the implementation is short, and the result is a system that has run reliably for decades. It’s one of my favorite examples of an academic idea finding its way into a real institution that touches every American physician’s career.

If you enjoyed this content, consider subscribing! I’m an MD-PhD candidate at Penn and hope to share advancements in AI research as they pertain to internal medicine and pediatrics.