IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v62y2014i4p713-732.html
   My bibliography  Save this article

Stability in Large Matching Markets with Complementarities

Author

Listed:
  • Itai Ashlagi

    (Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02142)

  • Mark Braverman

    (Computer Science, Princeton University, Princeton, New Jersey 08544)

  • Avinatan Hassidim

    (Computer Science, Bar-Ilan University, Ramat Gan, 52900, Israel)

Abstract

Labor markets can often be viewed as many-to-one matching markets. It is well known that if complementarities are present in such markets, a stable matching may not exist. We study large random matching markets with couples. We introduce a new matching algorithm and show that if the number of couples grows slower than the size of the market, a stable matching will be found with high probability. If however, the number of couples grows at a linear rate, with constant probability (not depending on the market size), no stable matching exists. Our results explain data from the market for psychology interns.

Suggested Citation

  • Itai Ashlagi & Mark Braverman & Avinatan Hassidim, 2014. "Stability in Large Matching Markets with Complementarities," Operations Research, INFORMS, vol. 62(4), pages 713-732, August.
    • Handle: RePEc:inm:oropre:v:62:y:2014:i:4:p:713-732
    DOI: 10.1287/opre.2014.1276
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2014.1276
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2014.1276?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Hatfield, John William & Kojima, Fuhito, 2010. "Substitutes and stability for matching with contracts," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1704-1723, September.
    2. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
    3. Yeon-Koo Che & Fuhito Kojima, 2010. "Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms," Econometrica, Econometric Society, vol. 78(5), pages 1625-1672, September.
    4. Klaus, Bettina & Klijn, Flip, 2005. "Stable matchings and preferences of couples," Journal of Economic Theory, Elsevier, vol. 121(1), pages 75-106, March.
    5. Milgrom,Paul, 2004. "Putting Auction Theory to Work," Cambridge Books, Cambridge University Press, number 9780521536721.
    6. repec:oup:restud:v:84:y::i:1:p:444-463. is not listed on IDEAS
    7. Martin W. Cripps & Jeroen M. Swinkels, 2006. "Efficiency of Large Double Auctions," Econometrica, Econometric Society, vol. 74(1), pages 47-92, January.
    8. Matthew O. Jackson & Jeroen M. Swinkels, 2005. "Existence of Equilibrium in Single and Double Private Value Auctions," Econometrica, Econometric Society, vol. 73(1), pages 93-139, January.
    9. Bettina Klaus & Flip Klijn & Toshifumi Nakamura, 2005. "Corrigendum: Stable Matchings and Preferences of Couples," Working Papers 261, Barcelona School of Economics.
    10. Jackson, Matthew O. & Manelli, Alejandro M., 1997. "Approximately Competitive Equilibria in Large Finite Economies," Journal of Economic Theory, Elsevier, vol. 77(2), pages 354-376, December.
    11. Parag A. Pathak & Alvin E. Roth, 2013. "Matching with Couples: Stability and Incentives in Large Markets," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 128(4), pages 1585-1632.
    12. Roberts, Donald John & Postlewaite, Andrew, 1976. "The Incentives for Price-Taking Behavior in Large Exchange Economies," Econometrica, Econometric Society, vol. 44(1), pages 115-127, January.
    13. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    14. 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, University of Chicago Press, vol. 92(6), pages 991-1016, December.
    15. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    16. Ning Sun & Zaifu Yang, 2006. "Equilibria and Indivisibilities: Gross Substitutes and Complements," Econometrica, Econometric Society, vol. 74(5), pages 1385-1402, September.
    17. Rustichini, Aldo & Satterthwaite, Mark A & Williams, Steven R, 1994. "Convergence to Efficiency in a Simple Market with Incomplete Information," Econometrica, Econometric Society, vol. 62(5), pages 1041-1063, September.
    18. Marek Pycia, 2012. "Stability and Preference Alignment in Matching and Coalition Formation," Econometrica, Econometric Society, vol. 80(1), pages 323-362, January.
    19. Fuhito Kojima & Parag A. Pathak, 2009. "Incentives and Stability in Large Two-Sided Matching Markets," American Economic Review, American Economic Association, vol. 99(3), pages 608-627, June.
    20. Mark A. Satterthwaite & Steven R. Williams, 1989. "The Rate of Convergence to Efficiency in the Buyer's Bid Double Auction as the Market Becomes Large," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 56(4), pages 477-498.
    21. Michael Ostrovsky, 2008. "Stability in Supply Chain Networks," American Economic Review, American Economic Association, vol. 98(3), pages 897-923, June.
    22. Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.
    23. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    2. Chao Huang, 2022. "Firm-worker hypergraphs," Papers 2211.06887, arXiv.org, revised Nov 2023.
    3. Chao Huang, 2021. "Stable matching: an integer programming approach," Papers 2103.03418, arXiv.org, revised Apr 2022.
    4. Hatfield, John William & Kominers, Scott Duke, 2017. "Contract design and stability in many-to-many matching," Games and Economic Behavior, Elsevier, vol. 101(C), pages 78-97.
    5. Thanh Nguyen & Rakesh Vohra, 2014. "Near Feasible Stable Matchings with Complementarities," PIER Working Paper Archive 14-028, Penn Institute for Economic Research, Department of Economics, University of Pennsylvania.
    6. Chen, Yan & Jiang, Ming & Kesten, Onur & Robin, Stéphane & Zhu, Min, 2018. "Matching in the large: An experimental study," Games and Economic Behavior, Elsevier, vol. 110(C), pages 295-317.
    7. Parag A. Pathak & Alvin E. Roth, 2013. "Matching with Couples: Stability and Incentives in Large Markets," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 128(4), pages 1585-1632.
    8. Jiang, Zhishan & Tian, Guoqiang, 2013. "Matching with Couples: Stability and Algorithm," MPRA Paper 57936, University Library of Munich, Germany, revised Jul 2014.
    9. Hatfield, John William & Kojima, Fuhito, 2010. "Substitutes and stability for matching with contracts," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1704-1723, September.
    10. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    11. Fuhito Kojima & Parag A. Pathak, 2009. "Incentives and Stability in Large Two-Sided Matching Markets," American Economic Review, American Economic Association, vol. 99(3), pages 608-627, June.
    12. Chao Huang, 2022. "Two-sided matching with firms' complementary preferences," Papers 2205.05599, arXiv.org, revised May 2022.
    13. Eduardo M Azevedo & Eric Budish, 2019. "Strategy-proofness in the Large," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 86(1), pages 81-116.
    14. Jagadeesan, Ravi & Kominers, Scott Duke & Rheingans-Yoo, Ross, 2018. "Strategy-proofness of worker-optimal matching with continuously transferable utility," Games and Economic Behavior, Elsevier, vol. 108(C), pages 287-294.
    15. Chao Huang, 2021. "Unidirectional substitutes and complements," Papers 2108.12572, arXiv.org.
    16. Tomoya Tajika & Tomoya Kazumura, 2019. "Non-manipulability of uniform price auctions with a large number of objects," International Journal of Game Theory, Springer;Game Theory Society, vol. 48(2), pages 543-569, June.
    17. Hatfield, John William & Kojima, Fuhito & Narita, Yusuke, 2016. "Improving schools through school choice: A market design approach," Journal of Economic Theory, Elsevier, vol. 166(C), pages 186-211.
    18. Kamada, Yuichiro & Kojima, Fuhito, 2017. "Stability concepts in matching under distributional constraints," Journal of Economic Theory, Elsevier, vol. 168(C), pages 107-142.
    19. Péter Biró & Flip Klijn, 2013. "Matching With Couples: A Multidisciplinary Survey," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 15(02), pages 1-18.
    20. Ravi Jagadeesan & Scott Duke Kominers & Ross Rheingans-Yoo, 2020. "Lone wolves in competitive equilibria," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 55(2), pages 215-228, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:62:y:2014:i:4:p:713-732. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.