IDEAS home Printed from https://ideas.repec.org/a/eee/gamebe/v142y2023icp508-526.html
   My bibliography  Save this article

Stable matching with multilayer approval preferences: Approvals can be harder than strict preferences

Author

Listed:
  • Bentert, Matthias
  • Boehmer, Niclas
  • Heeger, Klaus
  • Koana, Tomohiro

Abstract

We study stable matching problems where agents have multilayer preferences: There are ℓ layers each consisting of one preference order for each agent. Recently, Chen et al. [EC '18] studied such problems with strict preferences, establishing four multilayer adaptations of classical notions of stability. We follow up on their work by analyzing the computational complexity of stable matching problems with multilayer approval preferences, which leads to problems that are incomparable to the previously studied ones. We consider eleven stability notions derived from three well-established stability notions for stable matchings with ties and the four adaptations proposed by Chen et al. For each stability notion, we show that the problem of finding a stable matching is either polynomial-time solvable or NP-hard. Furthermore, we examine the influence of the number of layers and the desired “degree of stability” on the problems' complexity.

Suggested Citation

  • Bentert, Matthias & Boehmer, Niclas & Heeger, Klaus & Koana, Tomohiro, 2023. "Stable matching with multilayer approval preferences: Approvals can be harder than strict preferences," Games and Economic Behavior, Elsevier, vol. 142(C), pages 508-526.
    • Handle: RePEc:eee:gamebe:v:142:y:2023:i:c:p:508-526
    DOI: 10.1016/j.geb.2023.09.001
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0899825623001380
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.geb.2023.09.001?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Shuichi Miyazaki & Kazuya Okamoto, 2019. "Jointly stable matchings," Journal of Combinatorial Optimization, Springer, vol. 38(2), pages 646-665, August.
    2. Haris Aziz & Anna Bogomolnaia & Hervé Moulin, 2019. "Fair Mixing: the Case of Dichotomous Preferences," Post-Print hal-03047451, HAL.
    3. Bredereck, Robert & Komusiewicz, Christian & Kratsch, Stefan & Molter, Hendrik & Niedermeier, Rolf & Sorge, Manuel, 2019. "Assessing the computational complexity of multilayer subgraph detection," Network Science, Cambridge University Press, vol. 7(2), pages 215-241, June.
    4. Anna Bogomolnaia & Herve Moulin, 2004. "Random Matching Under Dichotomous Preferences," Econometrica, Econometric Society, vol. 72(1), pages 257-279, January.
    5. Suksompong, Warut, 2018. "Approximate maximin shares for groups of agents," Mathematical Social Sciences, Elsevier, vol. 92(C), pages 40-47.
    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. Xiaohui Bei & Xinhang Lu & Warut Suksompong, 2021. "Truthful Cake Sharing," Papers 2112.05632, arXiv.org, revised Feb 2022.
    2. Pasin Manurangsi & Warut Suksompong, 2020. "Closing Gaps in Asymptotic Fair Division," Papers 2004.05563, arXiv.org.
    3. Federico Echenique & Sumit Goel & SangMok Lee, 2022. "Stable allocations in discrete exchange economies," Papers 2202.04706, arXiv.org, revised Feb 2024.
    4. Xiaohui Bei & Guangda Huzhang & Warut Suksompong, 2018. "Truthful Fair Division without Free Disposal," Papers 1804.06923, arXiv.org, revised Apr 2020.
    5. Xiaohui Bei & Guangda Huzhang & Warut Suksompong, 2020. "Truthful fair division without free disposal," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 55(3), pages 523-545, October.
    6. Haris Aziz & Alexander Lam & Barton E. Lee & Toby Walsh, 2021. "Strategyproof and Proportionally Fair Facility Location," Papers 2111.01566, arXiv.org, revised Nov 2023.
    7. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    8. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2014. "Egalitarian equivalence and strategyproofness in the queueing problem," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 425-442, June.
    9. Efthymios Athanasiou & Juan D. Moreno-Ternero & Shlomo Weber, 2015. "Language learning and communicative benefits," Working Papers 15.09, Universidad Pablo de Olavide, Department of Economics.
    10. Tommy ANDERSSON & Lars EHLERS & Lars-Gunnar SVENSSON, 2014. "Transferring Ownership of Public Housing to Existing Tenants : A Mechanism Design Approach," Cahiers de recherche 09-2014, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    11. Karla Atkins & Achla Marathe & Chris Barrett, 2007. "A computational approach to modeling commodity markets," Computational Economics, Springer;Society for Computational Economics, vol. 30(2), pages 125-142, September.
    12. Bogomolnaia, Anna & Moulin, Herve & Stong, Richard, 2005. "Collective choice under dichotomous preferences," Journal of Economic Theory, Elsevier, vol. 122(2), pages 165-184, June.
    13. Andersson, Tommy & Csehz, Ágnes & Ehlers, Lars & Erlanson, Albin, 2018. "Organizing Time Banks: Lessons from Matching Markets," Working Papers 2018:19, Lund University, Department of Economics, revised 08 Mar 2019.
    14. Youngsub Chun & Boram Park, 2017. "A graph theoretic approach to the slot allocation problem," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 133-152, January.
    15. Ortega, Josué, 2020. "Multi-unit assignment under dichotomous preferences," Mathematical Social Sciences, Elsevier, vol. 103(C), pages 15-24.
    16. Chang, Hee-In & Chun, Youngsub, 2017. "Probabilistic assignment of indivisible objects when agents have the same preferences except the ordinal ranking of one object," Mathematical Social Sciences, Elsevier, vol. 90(C), pages 80-92.
    17. Karol Flores-Szwagrzak, 2016. "The replacement principle in networked economies with single-peaked preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(4), pages 763-789, December.
    18. Andrew McLennan & Shino Takayama & Yuki Tamura, 2024. "An Efficient, Computationally Tractable School Choice Mechanism," Discussion Papers Series 668, School of Economics, University of Queensland, Australia.
    19. Jérémy Picot, 2012. "Random aggregation without the Pareto principle," Review of Economic Design, Springer;Society for Economic Design, vol. 16(1), pages 1-13, March.
    20. Okumura, Yasunori, 2017. "A one-sided many-to-many matching problem," Journal of Mathematical Economics, Elsevier, vol. 72(C), pages 104-111.

    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:eee:gamebe:v:142:y:2023:i:c:p:508-526. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622836 .

    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.