zbMATH — the first resource for mathematics

Some things couples always wanted to know about stable matchings (but were afraid to ask). (English) Zbl 1136.91542
Summary: In this note we study the National Resident Matching Program (NRMP) algorithm in the US market for physicians. We report on two problems that concern the presence of couples, a feature explicitly incorporated in the new NRMP algorithm [cf. A. E. Roth and E. Peranson, The redesign of the matching market for American physicians: some engineering aspects of economic design. Am. Econ. Rev. 89, 748–780 (1999)]. First, we show that the new NRMP algorithm may not find an existing stable matching, even when couples’ preferences are ‘responsive’, i.e., when D. Gale and L. S. Shapley [Am. Math. Mon. 69, 9–15 (1962; Zbl 0109.24403)] deferred acceptance algorithm (on which the old NRMP algorithm is based) is applicable. Second, we demonstrate that the new NRMP algorithm may also be anipulated by couples acting as singles.

91B68 Matching models
Full Text: DOI
[1] Checker A (1973) The National Intern and Resident Matching Program, 1966–1972. J Med Educ 48:107–109
[2] Gale D, Shapley LS (1962) College admissions and the stability of marriage. Am Math Monthly 69:9–15 · Zbl 0109.24403 · doi:10.2307/2312726
[3] Klaus B, Klijn F (2005a) Stable matchings and preferences of couples. J Econ Theory 121:75–106 · Zbl 1098.91092 · doi:10.1016/j.jet.2004.04.006
[4] Klaus B, Klijn F (2005b) Corrigendum: stable matchings and preferences of couples. UFAE and IAE Working Paper 653–05, Universitat Autònoma de Barcelona
[5] Ronn E (1990) NP-Complete stable matching problems. J Algorithms 11:285–304 · Zbl 0705.68065 · doi:10.1016/0196-6774(90)90007-2
[6] Roth AE (1984) The evolution of the labor market for medical interns and residents: a case study in game theory. J Polit Econ 92:991–1016 · doi:10.1086/261272
[7] Roth AE (2002) The economist as engineer: game theory, experimentation, and computation as tools for design economics. Econometrica 70:1341–1378 · Zbl 1137.91339 · doi:10.1111/1468-0262.00335
[8] Roth AE, Peranson E (1999) The redesign of the matching market for American physicians: some engineering aspects of economic design. Am Econ Rev 89:748–780 · doi:10.1257/aer.89.4.748
[9] Roth AE, Sotomayor MAO (1990) Two-sided matching: a study in game-theoretic modeling and analysis. Econometric Society Monograph Series. Cambridge University Press, New York · Zbl 0726.90003
[10] Roth AE, Vande Vate JH (1990) Random paths to stability in two-sided matching. Econometrica 58:1475–1480 · Zbl 0731.90007 · doi:10.2307/2938326
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.