THE NRMP MATCHING ALGORITHM REVISITED - THEORY VERSUS PRACTICE

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. Any future changes in the NRMP algorithm should be based on the outcomes of such research, on philosophical questions about the matching process, and on practical considerations for incorporating match variations. Current research shows no indication that there is a better strategy for Match participants to follow than to submit their true preferences; without full information about the preferences submitted by other Match participants, doing otherwise would be dangerous. The authors discuss the question of submitting longer or shorter rank-order lists of preferences, the kinds of risks involved, the lack of empirical evidence available on this issue, and the best strategy for applicants to follow. The authors conclude that the algorithm selected to carry out the NRMP Match has contributed significantly to the success of the NRMP for many years. Nevertheless, some aspects of the process merit further study. To this end, the NRMP is exploring practical ways to address these issues as part of its ongoing responsibility to ensure that the Match participants continue to be well served.