Are the results of the medical residency match algorithm unique? Variant of the stable marriage problem

Question

Every year, applicants to medical residency programs each submit a strict ordering of a subset of available programs called a "rank order list" or "rank list" to the National Resident Matching Program (NRMP) that reflects each of their preferences. Residency programs similarly each submit rank lists of applicants to the NRMP. The NRMP then runs an algorithm that attempts to match applicants to their most preferred programs. Programs vary in the number of positions they need to fill.

While the algorithm apparently produces a matching that is stable (i.e., after the match, there does not exist a pair of applicants $x_1$ and $x_2$ who would prefer to switch the programs they got matched to), there is no public information that I can find as to whether the results of this algorithm are unique. As a current applicant, I would like to know if an algorithm exists that would ensure that the results are unique, or if not, to what extent the results may not be unique (i.e. how farther down could an applicant match in their rank list if the algorithm is re-run in a different order or with different parameters?).

I read the paper by Clark (http://pareto.uab.es/jmasso/pdf/ClarkCTE2006.pdf) which gives a sufficient condition for the uniqueness of stable matchings in the classic stable marriage problem, but I could not find anything regarding the NRMP Match variant of the stable marriage problem.

Answer 1

The criterion you give for the stability of a matching is incomplete. The matching is stable if there doesn't exist a blocking pair of assignments of a student $\ x_1\ $ to residency program $\ p_1\ $ and student $\ x_2\ $ to residency program $\ p_2\ $. For the assignments to constitute a blocking pair it isn't sufficient merely for the two students to prefer the program that the other has been assigned to. It's necessary also for the two residency programs to prefer the other student to the one who has been assigned to it.

The matching problem in the simple form you've described it is known variously as the "college admissions problem", the "hospital/residents problem", or the "rural hospital problem". Although it isn't quite as simple as the stable marriage problem (which is a special case of it), the Gale-Shapley algorithm will nevertheless still always produce a unique stable matching for it. This doesn't mean that there exists only one stable matching, but I understand that the one produced by the Gale-Shapley algorithm has some particularly nice properties.

The problem which the NRMP tries to solve is somewhat more complicated than a simple vanilla college admissions problem, however, and it now uses the Roth-Peranson algorithm, a modified version of Gale-Shapley developed by Alvin Roth and Elliott Peranson, and described by them in this paper. A Google search on "Roth-Peranson algorithm" will return links to a lot of literature on it.