Advanced Search
Article Contents
Article Contents

Finding all stable matchings with couples

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 91B68; Secondary: 91A12.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


    A. Abdulkadiroǧlu and T. Sönmez, School choice: A mechanism design approach, American Economic Review, 93 (2003), 729-747.


    H. Adachi, On a characterization of stable matchings, Economics Letters, 68 (2000), 43-49.doi: 10.1016/S0165-1765(99)00241-4.


    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.


    E. M. Azevedo and J. W. Hatfield, Complementarity and multidimensional heterogeneity in matching markets, 2012, Mimeo.


    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.


    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.


    P. Biró, T. Fleiner and R. Irving, Matching couples with scarf's algorithm, Institute of Economics, Hungarian Academy of Sciences.


    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.


    P. Biró and F. Klijn, Matching with couples: A multidisciplinary survey, International Game Theory Review, 15 (2013), 1340008, 18 pp.doi: 10.1142/S0219198913400082.


    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.


    Y.-K. Che, J. Kim and F. Kojima, Stable Matching in Large Economies, Technical report, mimeo, 2013.


    Y.-K. Che and F. Kojima, Asymptotic equivalence of probabilistic serial and random priority mechanisms, Econometrica, 78 (2010), 1625-1672.doi: 10.3982/ECTA8354.


    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.


    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.


    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.


    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.


    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.


    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.


    T. Fleiner, A fixed-point approach to stable matchings and some applications, Mathematics of Operations Research, 28 (2003), 103-126.doi: 10.1287/moor.


    D. Fragiadakis and P. Troyan, Market design under distributional constraints: Diversity in school choice and other applications, 2014, Mimeo.


    D. Fragiadakis, A. Iwasaki, P. Troyan, S. Ueda and M. Yokoo, Strategyproof matching with minimum quotas, mimeo.


    D. Gale and L. S. Shapley, College admissions and the stability of marriage, American Mathematical Monthly, 69 (1962), 9-15.doi: 10.2307/2312726.


    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.


    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.


    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.


    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/).


    J. Hatfield and P. Milgrom, Matching with contracts, American Economic Review, 95 (2005), 913-935.doi: 10.1257/0002828054825466.


    J. W. Hatfield and F. Kojima, Matching with contracts: Comment, American Economic Review, 98 (2008), 1189-1194.doi: 10.1257/aer.98.3.1189.


    J. W. Hatfield and S. D. Kominers, Contract design and stability in matching markets, Harvard University and Stanford University working paper.


    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.


    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.


    Y. Kamada and F. Kojima, General theory of matching under distributional constraints, 2014, Mimeo.


    Y. Kamada and F. Kojima, Stability concepts in matching with distributional constraints, 2014, Mimeo.


    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.


    O. Kesten, School choice with consent, The Quarterly Journal of Economics, 125 (2010), 1297-1348.doi: 10.1162/qjec.2010.125.3.1297.


    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.


    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.


    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.


    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.


    F. Kojima, A. Tamura and M. Yokoo, Designing matching mechanisms under constraints: An approach from discrete convex analysis, 2015, Mimeo.


    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.


    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.


    D. G. McVitie and L. Wilson, Stable marriage assignments for unequal sets, BIT, 10 (1970), 295-309.doi: 10.1007/BF01934199.


    T. Nguyen and R. Vohra, Near feasible stable matchings with complementarities, PIER Working Paper, 2014.doi: 10.2139/ssrn.2500824.


    M. Ostrovsky, Stability in supply chain networks, American Economic Review, 897-923.


    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.


    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.


    M. Pycia, Stability and preference alignment in matching and coalition formation, Econometrica, 80 (2012), 323-362.doi: 10.3982/ECTA7143.


    E. Ronn, Np-complete stable matching problems, Journal of Algorithms, 11 (1990), 285-304.doi: 10.1016/0196-6774(90)90007-2.


    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.


    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.


    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.


    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.


    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.


    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.


    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.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(294) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint