IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v302y2022i1p50-61.html
   My bibliography  Save this article

Stable matching of student-groups to dormitories

Author

Listed:
  • Perach, Nitsan
  • Anily, Shoshana

Abstract

This paper generalizes results of former papers on the assignment of students to dormitories, under an entrance criterion, by allowing students to apply in groups. A group-application means that its applicants ask to be assigned to the same dormitory, and otherwise they prefer living off-campus. The underlying assumption in our model is that the dormitories share a common preference over the student-groups, which is given by a strictly increasing ranking of their credit scores. The definition of a quasi-stable outcome is adjusted in order to incorporate student-group applications, and we prove that such an outcome always exists. Furthermore, a polynomial-time algorithm that finds all the quasi-stable outcomes is proposed. Apparently, not all properties of the single students’ model continue to hold under group-applications. Finally, we consider the incentive compatibility property of the proposed algorithm, and describe a specific quasi-stable outcome for which no subset of student-groups can gain by misrepresenting their preferences over the dormitories.

Suggested Citation

  • Perach, Nitsan & Anily, Shoshana, 2022. "Stable matching of student-groups to dormitories," European Journal of Operational Research, Elsevier, vol. 302(1), pages 50-61.
    • Handle: RePEc:eee:ejores:v:302:y:2022:i:1:p:50-61
    DOI: 10.1016/j.ejor.2021.12.048
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721011048
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.12.048?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. Tayfun Sönmez & Alvin E. Roth & M. Utku Ünver, 2007. "Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences," American Economic Review, American Economic Association, vol. 97(3), pages 828-851, June.
    2. Atila Abdulkadiroğlu & Parag A. Pathak & Alvin E. Roth, 2005. "The New York City High School Match," American Economic Review, American Economic Association, vol. 95(2), pages 364-367, May.
    3. Klaus, Bettina & Klijn, Flip, 2007. "Paths to stability for matching markets with couples," Games and Economic Behavior, Elsevier, vol. 58(1), pages 154-171, January.
    4. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
    5. Klaus, Bettina & Klijn, Flip, 2005. "Stable matchings and preferences of couples," Journal of Economic Theory, Elsevier, vol. 121(1), pages 75-106, March.
    6. Pedro de Araujo & James Murray, 2010. "Estimating the effects of dormitory living on student performance," Economics Bulletin, AccessEcon, vol. 30(1), pages 866-878.
    7. Marco Chiarandini & Rolf Fagerberg & Stefano Gualandi, 2019. "Handling preferences in student-project allocation," Annals of Operations Research, Springer, vol. 275(1), pages 39-78, April.
    8. Bettina Klaus & Flip Klijn & Toshifumi Nakamura, 2005. "Corrigendum: Stable Matchings and Preferences of Couples," Working Papers 261, Barcelona School of Economics.
    9. Lars-Gunnar Svensson, 1999. "Strategy-proof allocation of indivisible goods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 16(4), pages 557-567.
    10. 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.
    11. Pedro de Araujo & James Murray, 2010. "Estimating the Effects of Dormitory Living on Student Performance," CAEPR Working Papers 2010-002, Center for Applied Economics and Policy Research, Department of Economics, Indiana University Bloomington.
    12. Roth, Alvin E., 2003. "The origins, history, and design of the resident match," Scholarly Articles 35059715, Harvard University Department of Economics.
    13. Atila Abdulkadiroğlu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2005. "The Boston Public School Match," American Economic Review, American Economic Association, vol. 95(2), pages 368-371, May.
    14. Nitsan Perach & Uriel Rothblum, 2010. "Incentive compatibility for the stable matching model with an entrance criterion," International Journal of Game Theory, Springer;Game Theory Society, vol. 39(4), pages 657-667, October.
    15. 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.
    16. repec:ebl:ecbull:v:3:y:2004:i:45:p:1-11 is not listed on IDEAS
    17. C. Lockwood Reynolds, 2020. "The Effect of Dormitory Residence during College on Student Outcomes," Journal of Human Capital, University of Chicago Press, vol. 14(2), pages 249-289.
    18. Itai Ashlagi & Peng Shi, 2014. "Improving Community Cohesion in School Choice via Correlated-Lottery Implementation," Operations Research, INFORMS, vol. 62(6), pages 1247-1264, December.
    19. Eric J. McDermid & David F. Manlove, 2010. "Keeping partners together: algorithmic results for the hospitals/residents problem with couples," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 279-303, April.
    20. 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.
    21. Balinski, Michel & Sonmez, Tayfun, 1999. "A Tale of Two Mechanisms: Student Placement," Journal of Economic Theory, Elsevier, vol. 84(1), pages 73-94, January.
    22. David Cantala, 2004. "Matching Markets: the Particular Case of Couples," Economics Bulletin, AccessEcon, vol. 3(45), pages 1-11.
    23. Biró, Péter & van de Klundert, Joris & Manlove, David & Pettersson, William & Andersson, Tommy & Burnapp, Lisa & Chromy, Pavel & Delgado, Pablo & Dworczak, Piotr & Haase, Bernadette & Hemke, Aline & J, 2021. "Modelling and optimisation in European Kidney Exchange Programmes," European Journal of Operational Research, Elsevier, vol. 291(2), pages 447-456.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kong, Qianqian & Peters, Hans, 2023. "Power indices for networks, with applications to matching markets," European Journal of Operational Research, Elsevier, vol. 306(1), pages 448-456.
    2. Eirinakis, Pavlos & Mourtos, Ioannis & Zampou, Eleni, 2022. "Random Serial Dictatorship for horizontal collaboration in logistics," Omega, Elsevier, vol. 111(C).

    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. 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.
    2. Dur, Umut Mert & Wiseman, Thomas, 2019. "School choice with neighbors," Journal of Mathematical Economics, Elsevier, vol. 83(C), pages 101-109.
    3. 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.
    4. Delorme, Maxence & García, Sergio & Gondzio, Jacek & Kalcsics, Joerg & Manlove, David & Pettersson, William, 2021. "Stability in the hospitals/residents problem with couples and ties: Mathematical models and computational studies," Omega, Elsevier, vol. 103(C).
    5. 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.
    6. Morrill, Thayer & Roth, Alvin E., 2024. "Top trading cycles," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    7. Ata Atay & Sylvain Funck & Ana Mauleon & Vincent Vannetelbosch, 2023. "Matching markets with farsighted couples," UB School of Economics Working Papers 2023/445, University of Barcelona School of Economics.
    8. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers halshs-00860931, HAL.
    9. 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.
    10. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers 1327, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.
    11. Eric J. McDermid & David F. Manlove, 2010. "Keeping partners together: algorithmic results for the hospitals/residents problem with couples," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 279-303, April.
    12. Che, Yeon-Koo & Kim, Jinwoo & Kojima, Fuhito, 2015. "Efficient assignment with interdependent values," Journal of Economic Theory, Elsevier, vol. 158(PA), pages 54-86.
    13. 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.
    14. Mustafa Oguz Afacan & Nejat Anbarci & Ozgur Kıbrıs, 2022. "Arbiter Assignment," Department of Economics Working Papers 2022_02, Durham University, Department of Economics.
    15. Dimitrov, Dinko & Lazarova, Emiliya A., 2008. "Coalitional Matchings," Coalition Theory Network Working Papers 37523, Fondazione Eni Enrico Mattei (FEEM).
    16. Zhu, Min, 2014. "College admissions in China: A mechanism design perspective," China Economic Review, Elsevier, vol. 30(C), pages 618-631.
    17. Alvin E. Roth, 2009. "What Have We Learned from Market Design?," Innovation Policy and the Economy, University of Chicago Press, vol. 9(1), pages 79-112.
    18. Takumi Kongo, 2013. "An incompatibility between recursive unanimity and strategy-proofness in two-sided matching problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 40(2), pages 461-478, February.
    19. Aytek Erdil & Haluk Ergin, 2008. "What's the Matter with Tie-Breaking? Improving Efficiency in School Choice," American Economic Review, American Economic Association, vol. 98(3), pages 669-689, June.
    20. Committee, Nobel Prize, 2012. "Alvin E. Roth and Lloyd S. Shapley: Stable allocations and the practice of market design," Nobel Prize in Economics documents 2012-1, Nobel Prize Committee.

    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:ejores:v:302:y:2022:i:1:p:50-61. 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/eor .

    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.