Matching with Couples: Stability and Algorithm

Jiang, Zhishan and Tian, Guoqiang (2013): Matching with Couples: Stability and Algorithm.

Abstract

This paper defines a notion of semi-stability for matching problem with couples, which is a natural generalization of, and further identical to, the conventional stability for matching without couples. It is shown that there always exists a semi-stable matching for couples markets with strict preferences, and the set of semi-stable matchings can be partitioned into subsets, each of which forms a distributive lattice. We further prove that a semi-stable matching is stable when couples play reservation strategies. This result perfectly explains the puzzle of NRMP even for finite markets. Moreover, we define a notion of asymptotic stability and present sufficient conditions for a sequential couples market to be asymptotically stable. Another remarkable contribution is that we develop a new algorithm, called Persistent Improvement Algorithm, for finding semi-stable matchings, which is also more efficient than the Gale-Shapley algorithm for finding stable matchings for singles markets. Lastly, this paper investigates the welfare property and incentive issues of semi-stable mechanisms.

• Item Type: MPRA Paper
• Language: English
• Keywords: Matching with couples; stability; semi-stability; asymptotic stability; algorithm
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C78 - Bargaining Theory ; Matching Theory; J - Labor and Demographic Economics > J4 - Particular Labor Markets > J41 - Labor Contracts

References

[1] Abdulkadiroglu, Atila [2005]: “College Admission with Affirmative Action,” International Journal of Game Theory 33, 535-549.

[2] Aldershof, Brian and Olivia M. Carducci [1996]: “Stable Matchings with Couples ” Discrete Applied Mathematics (68)1-2, 203-207.

[3] Birkhoff, Garrett and Saunders Mac Lane [2007]: “A Survey of Modern Algebra,” A K Peters, Ltd. And Posts and Telecom Press, China.

[4] Crawford, Vincent P., and Elsie Marie Knoer [1981]: “Job Matching with Heterogeneous Firms and Workers,” Econometrica 49(2):437-50.

[5] Dubins, L.E., Freedman, D.A. [1981]: “Machiavelli and the Gale-Shapley algorithm,” American Mathematical Monthly 88, 485-494.

[6] Hatfield J. W. and P. R. Milgrom [2005]: “Matching with Contracts,” American Economic Review 95, 913-935.

[7] Gale David and Lloyd S. Shapley [1962]: “College Admissions and the Stability of Marriage,” American Mathematical Monthly 69, 9-15.

[8] Kelso, Alexander S., Jr., and Vincent P. Crawford [1982]: “Job Matching, Coalition Formation, and Gross Substitutes,” Econometrica 50(6):1483-1504.

[9] Klaus Bettina and Flip Klijn [2005]: “Stable Matching and Preferences of Couples,” Journal of Economic Theory 121, 75-106.

[10] Klijn F. and J. Masso [2003]: “Weak Stability and a Bargaining Set for the Marriage Model,” Games and Economic Behavior 42, 91-100.

[11] Knuth, Donald E. [1976]: “Mariages Stables, Montreal,” Les Presses de l’Universite de Montreal.

[12] Kojima F. and P. A. Pathak [2009]: “Incentives and Stability in Large Two-sided Matching Markets,” American Economic Review 99, 608-627.

[13] Kojima F. P. A. Pathak and A. V. Roth [2013]: “Matching with Couples: Stability and Incentives in Large Markets,” Quarterly Journal of Economics 128, 1585-1632.

[14] Martinez, Ruth, Masso, Jordi, Neme, Alejandro, Ovideo, Jorge [2004]: “On group strategyproof mechanisms for many-to-one matching model,” International Journal of Game Theory 33, 115-128.

[15] McVitie, D. G. and L. B. Wilson [1970]: “Stable Marriage Assignments for Unequal Sets,” BIT, 10, 295-309.

[16] Ostrovsky Michael [2008]: “Stability in Supply Chain Networks,” American Economic Re- view 98, 897-923.

[17] Ronn Eytan [1990]: “NP-complete stable matching problems,” Journal of Algorithms 11, 2, June, 285-304.

[18] Roth Alvin E. [1982]: “The economics of matching: stability and incentives,” Mathematics of Operations Research 7, 617-628.

[19] Roth Alvin E. [1982a]: “The Economics of Matching: Stability and Incentives,” Mathe- matics of Operations Research Vol. 7, 617-628.

[20] Roth Alvin E. [1984]: “The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory,” Journal of Political Economy 92, 991-1016.

[21] Roth Alvin E. [1985]: “The College Admissions Problem is not Equivalent to the Marriage Problem,” Journal of Economic Theory 36, 277-288.

[22] Roth Alvin E. [2008]: “Deferred Acceptance Algorithms: History, Theory, Practice, and Open Questions,” International Journal of Game Theory 36, 537-569.

[23] Roth A. E. and E. Peranson [1999]: “The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design,” American Economic Review 89, 748-780.

[24] Roth A. E. and M. A. O. Sotomayor [1990]: “Two-Sided Matching: A Study in Game Theoretic Modeling and Analysis,” Econometric Society Monograph Series, Cambridge University Press New York, 1990.

[25] Roth A. E. and Vande Vate John H. [1990]: “Random Paths to Stability in Two-Sided Matching,” Econometrica 58, 1475-1480.

[26] S¨onmez, Tayfun [1997]: “Manipulation via Capacities in Two-Sided Matching Markets,” Journal of Economic Theory 77, 197-204.

[27] Ning Sun and Zaifu Yang [2006]: “Equilibria and Indivisibilities: Gross Substitutes and Complements,” Econometrica 74, 1385-1402.

[28] Ning Sun and Zaifu Yang [2009]: “Double-Track Adjustment Process for Discrete Markets with Substitutes and Complements,” Econometrica 77, 933-952.

[29] Zhou L. [1994]: “A New Bargaining Set of an N-person Game and Endogenous Coalition Formation,” Games and Economic Behavior 6, 512-526.