IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2507.07490.html
   My bibliography  Save this paper

Characterizing Stability in Many-to-One Matching with Non-Responsive Couples

Author

Listed:
  • Shashwat Khare
  • Souvik Roy

Abstract

We study many-to-one matching problems between institutions and individuals, where each institution may be matched to multiple individuals. The matching market includes couples, who view pairs of institutions as complementary. Institutions' preferences over sets of individuals are assumed to satisfy responsiveness, whereas couples' preferences over pairs of institutions may violate responsiveness. In this setting, we first assume that all institutions share a common preference ordering over individuals, and we establish: (i) a complete characterization of all couples' preference profiles for which a stable matching exists, under the additional assumption that couples violate responsiveness only to ensure co-location at the same institution, and (ii) a necessary and sufficient condition on the common institutional preference such that a stable matching exists when couples may violate responsiveness arbitrarily. Next, we relax the common preference assumption, requiring institutions to share a common ranking only over the members of each couple. Under this weaker assumption, we provide: (i) a complete characterization of all couples' preferences for which a stable matching exists, and (ii) a sufficient condition on individuals' preferences that guarantees the existence of a stable matching.

Suggested Citation

  • Shashwat Khare & Souvik Roy, 2025. "Characterizing Stability in Many-to-One Matching with Non-Responsive Couples," Papers 2507.07490, arXiv.org.
    • Handle: RePEc:arx:papers:2507.07490
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2507.07490
    File Function: Latest version
    Download Restriction: no
    ---><---

    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. Klaus, Bettina & Klijn, Flip, 2005. "Stable matchings and preferences of couples," Journal of Economic Theory, Elsevier, vol. 121(1), pages 75-106, March.
    3. Bettina Klaus & Flip Klijn, 2005. "Corrigendum: Stable Matchings and Preferences of Couples," UFAE and IAE Working Papers 653.05, Unitat de Fonaments de l'Anàlisi Econòmica (UAB) and Institut d'Anàlisi Econòmica (CSIC).
    4. Dutta, Bhaskar & Masso, Jordi, 1997. "Stability of Matchings When Individuals Have Preferences over Colleagues," Journal of Economic Theory, Elsevier, vol. 75(2), pages 464-475, August.
    5. 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.
    6. Klaus, Bettina & Klijn, Flip & Nakamura, Toshifumi, 2009. "Corrigendum to "Stable matchings and preferences of couples" [J. Econ. Theory 121 (1) (2005) 75-106]," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2227-2233, September.
    7. , & ,, 2006. "A theory of stability in many-to-many matching markets," Theoretical Economics, Econometric Society, vol. 1(2), pages 233-273, June.
    8. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    9. 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.
    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. 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.
    2. Shashwat Khare & Souvik Roy & Ton Storcken, 2025. "Stability in Many-to-One Matching with Couples having Responsive Preferences," Papers 2507.07501, arXiv.org.
    3. 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.
    4. Chao Huang, 2022. "Firm-worker hypergraphs," Papers 2211.06887, arXiv.org, revised Nov 2023.
    5. Khare, Shashwat & Roy, Souvik, 2017. "Stability in Matching with Couples having Non-Responsive Preferences," Research Memorandum 007, Maastricht University, Graduate School of Business and Economics (GSBE).
    6. Itai Ashlagi & Mark Braverman & Avinatan Hassidim, 2014. "Stability in Large Matching Markets with Complementarities," Operations Research, INFORMS, vol. 62(4), pages 713-732, August.
    7. 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.
    8. Chao Huang, 2021. "Stable matching: an integer programming approach," Papers 2103.03418, arXiv.org, revised Apr 2022.
    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. Dur, Umut Mert & Wiseman, Thomas, 2019. "School choice with neighbors," Journal of Mathematical Economics, Elsevier, vol. 83(C), pages 101-109.
    11. Dimitrov, Dinko & Lazarova, Emiliya A., 2008. "Coalitional Matchings," Coalition Theory Network Working Papers 37523, Fondazione Eni Enrico Mattei (FEEM).
    12. 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.
    13. Tello, Benjamín, 2023. "Restricted complementarity and paths to stability in matching with couples," Mathematical Social Sciences, Elsevier, vol. 126(C), pages 60-67.
    14. Tello, Benjamín, 2016. "Matching with contracts, substitutes and two-unit demand," Economics Letters, Elsevier, vol. 146(C), pages 85-88.
    15. Echenique, Federico & Yenmez, M. Bumin, 2007. "A solution to matching with preferences over colleagues," Games and Economic Behavior, Elsevier, vol. 59(1), pages 46-71, April.
    16. Dimitrov, Dinko & Lazarova, Emiliya, 2011. "Two-sided coalitional matchings," Mathematical Social Sciences, Elsevier, vol. 62(1), pages 46-54, July.
    17. Chao Huang, 2025. "Matching to two sides," Papers 2509.10942, arXiv.org.
    18. Chao Huang, 2021. "Unidirectional substitutes and complements," Papers 2108.12572, arXiv.org.
    19. 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.
    20. Klaus, Bettina & Walzl, Markus, 2009. "Stable many-to-many matchings with contracts," Journal of Mathematical Economics, Elsevier, vol. 45(7-8), pages 422-434, July.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:arx:papers:2507.07490. 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: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    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.