How Long Does the Residency Match Algorithm Take To Run?

The Problem

The problem of matching residency programs with applicants is basically a generalization of the stable marriage problem in computer science, which is the problem of trying to find stable pairings between two sets of people (i.e., men and women who want to get married). A set of pairings is considered stable if there is no pair that prefers each other to their assigned matches. In other words, we don’t want any two people to have the incentive to elope. Each person creates a preference list, ranking the members of the other set from most preferred to least preferred, and these lists are used to calculate stable matches.

Unstable matches are bad news.

The Solution

In 1962, David Gale and Lloyd Shapley published an algorithm to solve the stable marriage problem. The algorithm works by a number of “rounds”. The process begins with each member of one group—say, the women— “proposing” to the member of the other group—in this case, the man—that she likes best. Each man then reviews the proposals he received, tentatively holds on to the best proposal and rejects the rest. In the next round, the rejected women propose to their next best choice, and the men again retain the best proposal and reject the rest. This process continues until there are no more women left to propose, at which point the men accept the best proposals among those they’ve held onto. Assuming an equal number of men and women in the problem, everyone will have been paired up. Gale and Shapley proved mathematically that the matches created by this method would always be stable. This method is called “deferred acceptance”.

Alvin Roth accepting the Nobel Prize in 2012.

The Experiment

Since the NRMP hasn’t made their algorithm’s code public, I used my own version of the Gale-Shapley algorithm adapted from an implementation by Rob W. Irving. In order to run my simulation, I generated a dataset closely mirroring the 2014 Main Resident Match. I created 34,270 applicants, each having a rank list with an average of 10 programs. I also generated 4,735 residency programs having a total number of 29,671 positions, and ranking an average of 60 applicants each. At this point, I had a database representing the entire US residency match, and I was ready to run the algorithm.

So there you have it. The fate of every medical student’s life may very well be decided in less than a half a minute!

You can watch my simulation run below! Note that printing everything out to the screen does slow things down a little bit.

  1. What determines the time it takes for an algorithm to run?

References

  1. Gale, D and L. S. Shapley. “College Admissions and the Stability of Marriage,” American Mathematics Monthly, 69:9–14, 1962.
  2. Gusfield, D and R.W. Irving. “The Stable Marriage Problem: Structure and Algorithms.” MIT Press, Boston, Mass., 1989.
  3. Roth, Alvin E. “The Economics of Matching: Stability and Incentives,” Mathematics of Operations Research, 7:617–628, 1982.
  4. Roth, Alvin E. “The National Residency Matching Program as a Labor Market,” Journal of the American Medical Association, April 3, 1996, Vol. 275, No. 13, pages 1054–1056.

--

--

Physician & Software Developer

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store