Finding all stable matchings with couples

Fuhito  Kojima

doi:10.3934/jdg.2015008

Article Contents

2015, Volume 2, Issue 3&4: 321-330. Doi: 10.3934/jdg.2015008

This issue Previous Article Externality effects in the formation of societies Next Article Why do stable clearinghouses work so well? - Small sets of stable matchings in typical environments, and the limits-on-manipulation theorem of Demange, Gale and Sotomayor

Finding all stable matchings with couples

Fuhito Kojima^1,

1.
Department of Economics, Stanford University, 579 Serra Mall, Stanford, CA 94305

Received: March 31, 2015

Revised: April 30, 2015

Published: June 2015

Abstract Related Papers Cited by

Abstract

In two-sided matching markets in which some doctors form couples, a stable matching does not necessarily exist.Wecharacterize the set of stable matchings as the fixed points of a function that is reminiscent of a tâtonnement process. Then we show that this function ismonotone decreasing with respect to a certain partialorder. Based on these results,wepresent an algorithm that finds all the stable matchings wheneverone exists, and otherwise demonstrates that there is no stable matching.

Keywords:

Mathematics Subject Classification: Primary: 91B68; Secondary: 91A12.

Citation:

Related Papers

Cited by

References

[1]	A. Abdulkadiroglu, Y.-K. Che and Y. Yasuda, Resolving conflicting preferences in school choice: The 'boston' mechanism reconsidered, American Economic Review, (2009), 399-410.doi: 10.2139/ssrn.1465293.
[2]	A. Abdulkadiroglu, P. A. Pathak and A. E. Roth, Strategy-proofness versus efficiency in matching with indifferences: Redesigning the new york city high school match, American Economic Review, 99 (2009), 1954-1978.
[3]	A. Abdulkadiroǧlu and T. Sönmez, School choice: A mechanism design approach, American Economic Review, 93 (2003), 729-747.
[4]	H. Adachi, On a characterization of stable matchings, Economics Letters, 68 (2000), 43-49.doi: 10.1016/S0165-1765(99)00241-4.
[5]	I. Ashlagi, M. Braverman and A. Hassidim, Stability in large matching markets with complementarities, Operations Research, 62 (2014), 713-732.doi: 10.1287/opre.2014.1276.
[6]	E. M. Azevedo and J. W. Hatfield, Complementarity and multidimensional heterogeneity in matching markets, 2012, Mimeo.
[7]	M. Balinski and T. Sönmez, A tale of two mechanisms: student placement, Journal of Economic Theory, 84 (1999), 73-94.doi: 10.1006/jeth.1998.2469.
[8]	P. Biró, T. Fleiner, R. W. Irving and D. F. Manlove, The college admissions problem with lower and common quotas, Theoretical Computer Science, 411 (2010), 3136-3153.doi: 10.1016/j.tcs.2010.05.005.
[9]	P. Biró, T. Fleiner and R. Irving, Matching couples with scarf's algorithm, Institute of Economics, Hungarian Academy of Sciences.
[10]	P. Biró, R. W. Irving and I. Schlotter, Stable matching with couples: an empirical study, Journal of Experimental Algorithmics (JEA), 16 (2011), Article 1.2, 27 pp.doi: 10.1145/1963190.1963191.
[11]	P. Biró and F. Klijn, Matching with couples: A multidisciplinary survey, International Game Theory Review, 15 (2013), 1340008, 18 pp.doi: 10.1142/S0219198913400082.
[12]	P. Biró, D. F. Manlove and I. McBride, The hospitals/residents problem with couples: Complexity and integer programming models, in Experimental Algorithms, Springer, 2014, 10-21.
[13]	Y.-K. Che, J. Kim and F. Kojima, Stable Matching in Large Economies, Technical report, mimeo, 2013.
[14]	Y.-K. Che and F. Kojima, Asymptotic equivalence of probabilistic serial and random priority mechanisms, Econometrica, 78 (2010), 1625-1672.doi: 10.3982/ECTA8354.
[15]	B. Dutta and J. Masso, Stability of matchings when individuals have preferences over colleagues, Journal of Economic Theory, 75 (1997), 464-475.doi: 10.1006/jeth.1997.2291.
[16]	F. Echenique, Finding all equilibria in games with strategic complements, Journal of Economic Theory, 135 (2007), 514-532.doi: 10.1016/j.jet.2006.06.001.
[17]	F. Echenique and J. Oviedo, Core many-to-one matchings by fixed point methods, Journal of Economic Theory, 115 (2004), 358-376.doi: 10.1016/S0022-0531(04)00042-1.
[18]	F. Echenique and J. Oviedo, A theory of stability in many-to-many matching, Theoretical Economics, 1 (2006), 233-273.doi: 10.2139/ssrn.691443.
[19]	F. Echenique and M. B. Yenmez, A solution to matching with preferences over colleagues, Games and Economic Behavior, 59 (2007), 46-71.doi: 10.1016/j.geb.2006.07.003.
[20]	A. Erdil and H. Ergin, What's the matter with tie-breaking? improving efficiency in school choice, American Economic Review, 98 (2008), 669-689.doi: 10.1257/aer.98.3.669.
[21]	T. Fleiner, A fixed-point approach to stable matchings and some applications, Mathematics of Operations Research, 28 (2003), 103-126.doi: 10.1287/moor.28.1.103.14256.
[22]	D. Fragiadakis and P. Troyan, Market design under distributional constraints: Diversity in school choice and other applications, 2014, Mimeo.
[23]	D. Fragiadakis, A. Iwasaki, P. Troyan, S. Ueda and M. Yokoo, Strategyproof matching with minimum quotas, mimeo.
[24]	D. Gale and L. S. Shapley, College admissions and the stability of marriage, American Mathematical Monthly, 69 (1962), 9-15.doi: 10.2307/2312726.
[25]	D. Gale and M. A. O. Sotomayor, Ms. machiavelli and the stable matching problem, American Mathematical Monthly, 92 (1985), 261-268.doi: 10.2307/2323645.
[26]	D. Gale and M. A. O. Sotomayor, Some remarks on the stable matching problem, Discrete Applied Mathematics, 11 (1985), 223-232.doi: 10.1016/0166-218X(85)90074-5.
[27]	M. Goto, N. Hashimoto, A. Iwasaki, Y. Kawasaki, S. Ueda, Y. Yasuda and M. Yokoo, Strategy-proof matching with regional minimum quotas, in AAMAS2014, 2014.
[28]	M. Goto, A. Iwasaki, Y. Kawasaki, Y. Yasuda and M. Yokoo, Improving fairness and efficiency in matching markets with regional caps: Priority-list based deferred acceptance mechanism, Mimeo (the latest version is available at http://mpra.ub.uni-muenchen.de/53409/).
[29]	J. Hatfield and P. Milgrom, Matching with contracts, American Economic Review, 95 (2005), 913-935.doi: 10.1257/0002828054825466.
[30]	J. W. Hatfield and F. Kojima, Matching with contracts: Comment, American Economic Review, 98 (2008), 1189-1194.doi: 10.1257/aer.98.3.1189.
[31]	J. W. Hatfield and S. D. Kominers, Contract design and stability in matching markets, Harvard University and Stanford University working paper.
[32]	N. Immorlica and M. Mahdian, Marriage, honesty, and stability, Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, (electronic), ACM, New York, (2005), 53-62.
[33]	Y. Kamada and F. Kojima, Stability and strategy-proofness for matching with constraints: A problem in the japanese medical match and its solution, American Economic Review P&P, 102 (2012), 366-370.doi: 10.1257/aer.102.3.366.
[34]	Y. Kamada and F. Kojima, General theory of matching under distributional constraints, 2014, Mimeo.
[35]	Y. Kamada and F. Kojima, Stability concepts in matching with distributional constraints, 2014, Mimeo.
[36]	Y. Kamada and F. Kojima, Efficient matching under distributional constraints: Theory and applications, American Economic Review, 105 (2015), 67-99.doi: 10.1257/aer.20101552.
[37]	O. Kesten, School choice with consent, The Quarterly Journal of Economics, 125 (2010), 1297-1348.doi: 10.1162/qjec.2010.125.3.1297.
[38]	B. Klaus and F. Klijn, Stable matchings and preferences of couples, Journal of Economic Theory, 121 (2005), 75-106.doi: 10.1016/j.jet.2004.04.006.
[39]	B. Klaus, F. Klijn and J. Masso, Some things couples always wanted to know about stable matchings (but were afraid to ask), Review of Economic Design, 11 (2007), 175-184.doi: 10.1007/s10058-006-0017-9.
[40]	F. Kojima and P. A. Pathak, Incentives and stability in large two-sided matching markets, American Economic Review, 99 (2009), 608-627.doi: 10.1257/aer.99.3.608.
[41]	F. Kojima, P. A. Pathak and A. E. Roth, Matching with couples: Stability and incentives in large markets, Quarterly Journal of Economics, 128 (2013), 1585-1632.doi: 10.1093/qje/qjt019.
[42]	F. Kojima, A. Tamura and M. Yokoo, Designing matching mechanisms under constraints: An approach from discrete convex analysis, 2015, Mimeo.
[43]	H. Konishi and U. Unver, Credible group stability in multi-partner matching problems, Journal of Economic Theory, 129 (2006), 57-80.doi: 10.1016/j.jet.2005.02.001.
[44]	E. J. McDermid and D. F. Manlove, Keeping partners together: algorithmic results for the hospitals/residents problem with couples, Journal of Combinatorial Optimization, 19 (2010), 279-303.doi: 10.1007/s10878-009-9257-2.
[45]	D. G. McVitie and L. Wilson, Stable marriage assignments for unequal sets, BIT, 10 (1970), 295-309.doi: 10.1007/BF01934199.
[46]	T. Nguyen and R. Vohra, Near feasible stable matchings with complementarities, PIER Working Paper, 2014.doi: 10.2139/ssrn.2500824.
[47]	M. Ostrovsky, Stability in supply chain networks, American Economic Review, 897-923.
[48]	P. A. Pathak and T. Sönmez, Leveling the playing field: Sincere and sophisticated players in the boston mechanism, The American Economic Review, 98 (2008), 1636-1652.doi: 10.1257/aer.98.4.1636.
[49]	P. A. Pathak and T. Sönmez, School admissions reform in chicago and england: Comparing mechanisms by their vulnerability to manipulation, American Economic Review, 103 (2013), 80-106.doi: 10.1257/aer.103.1.80.
[50]	M. Pycia, Stability and preference alignment in matching and coalition formation, Econometrica, 80 (2012), 323-362.doi: 10.3982/ECTA7143.
[51]	E. Ronn, Np-complete stable matching problems, Journal of Algorithms, 11 (1990), 285-304.doi: 10.1016/0196-6774(90)90007-2.
[52]	A. E. Roth, The evolution of the labor market for medical interns and residents: A case study in game theory, Journal of Political Economy, 92 (1984), 991-1016.doi: 10.1086/261272.
[53]	A. E. Roth, On the allocation of residents to rural hospitals: A general property of two-sided matching markets, Econometrica, 54 (1986), 425-427.doi: 10.2307/1913160.
[54]	A. E. Roth, A natural experiment in the organization of entry-level labor markets: regional markets for new physicians and surgeons in the united kingdom, The American economic review, 415-440.
[55]	A. E. Roth and E. Peranson, The redesign of the matching market for american physicians: Some engineering aspects of economic design, American Economic Review, 89 (1999), 748-780.doi: 10.1257/aer.89.4.748.
[56]	A. E. Roth and M. A. Sotomayor, Two-sided Matching: A Study in Game-Theoretic Modeling and Analysis, Econometric Society monographs, Cambridge, 1990.doi: 10.1017/CCOL052139015X.
[57]	T. Sönmez and M. U. Ünver, Course bidding at business schools, International Economic Review, 51 (2010), 99-123.doi: 10.1111/j.1468-2354.2009.00572.x.
[58]	M. A. O. Sotomayor, A non-constructive elementary proof of the existence of stable marriages, Games and Economic Behavior, 13 (1996), 135-137.doi: 10.1006/game.1996.0029.
[59]	M. A. O. Sotomayor, Three remarks on the many-to-many stable matching problem, Mathematical social sciences, 38 (1999), 55-70.doi: 10.1016/S0165-4896(98)00048-1.
[60]	M. A. O. Sotomayor, Implementation in the many-to-many matching market, Games and Economic Behavior, 46 (2004), 199-212.doi: 10.1016/S0899-8256(03)00047-2.