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 far down could an applicant match in their rank list if the algorithm is run in a different order?).

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.

CodePudding user response：

The answer is given at my repost of this question in the math stackexchange. Namely the stable matching is not necessarily unique, but because the algorithm is run such that the applicants are proposing to the hospitals (and not the other way around), the matching that results is applicant-optimal rather than hospital-optimal.