The NRMP matching algorithm revisited: theory versus practice. National Resident Matching Program.

The authors examine the algorithm used by the National Resident Matching Program (NRMP) in its centralized matching of applicants to U.S. residency programs ("the Match"). Their goal is to evaluate the current NRMP matching algorithm to determine whether it still fulfills its intended purpose adequately and whether changes could be made that would improve the Match. They describe the basic NRMP algorithm and many of the variations of the matching process ("match variations") incorporated over the last 20 years to meet participants' requirements. An overview of the current state of the theory of preference matching is presented, including descriptions of the characteristics of stable matches in general, program-optimal and applicant-optimal matchings, and strategies for formulating preference lists. The characteristics of the current NRMP algorithm are then compared with the theoretical findings. Research conducted long after the original NRMP algorithm was devised has shown that an algorithm that produces stable matches is the best approach for matching applicants to positions. In the absence of requirements to satisfy match variations, the NRMP's deferred-acceptance algorithm produces a program-optimal stable match. When match variations, such as those handled by the NRMP, must be introduced, it is possible that no stable matching exists, and the resulting matching produced by the NRMP algorithm may not be program-optimal. The question of program-optimal versus applicant-optimal matchings is discussed. Theoretical and empirical evidence currently available suggest that differences between these two kinds of matchings are likely to be small. However, further tests and research are needed to assess the real differences in the results produced by different stable matching algorithms that produce program-optimal or applicant-optimal stable matches.(ABSTRACT TRUNCATED AT 250 WORDS)