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

Stable Roommate Problem with Diversity Preferences

Author

Listed:
  • Niclas Boehmer
  • Edith Elkind

Abstract

In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences [Bredereck et al., 2019]: each agent belongs to one of the two types (e.g., juniors and seniors, artists and engineers), and agents' preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem. Moreover, for the classic setting with rooms of size two, we present a linear-time algorithm that computes an outcome that is core and exchange stable as well as Pareto optimal. Many of our results for the stable roommate problem extend to the stable marriage problem.

Suggested Citation

  • Niclas Boehmer & Edith Elkind, 2020. "Stable Roommate Problem with Diversity Preferences," Papers 2004.14640, arXiv.org.
  • Handle: RePEc:arx:papers:2004.14640
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Morrill, Thayer, 2010. "The roommates problem revisited," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1739-1756, September.
    2. Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November.
    3. Ravi Kannan, 1987. "Minkowski's Convex Body Theorem and Integer Programming," Mathematics of Operations Research, INFORMS, vol. 12(3), pages 415-440, August.
    4. Atila Abdulkadiroglu & Tayfun Sönmez, 2003. "School Choice: A Mechanism Design Approach," American Economic Review, American Economic Association, vol. 93(3), pages 729-747, June.
    5. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    6. Ballester, Coralio, 2004. "NP-completeness in hedonic games," Games and Economic Behavior, Elsevier, vol. 49(1), pages 1-30, October.
    7. Marilda Sotomayor, 2011. "The pareto-stability concept is a natural solution concept for discrete matching markets with indifferences," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(3), pages 631-644, August.
    8. Hofbauer, Johannes, 2016. "d-dimensional stable matching with cyclic preferences," Mathematical Social Sciences, Elsevier, vol. 82(C), pages 72-76.
    9. Bogomolnaia, Anna & Jackson, Matthew O., 2002. "The Stability of Hedonic Coalition Structures," Games and Economic Behavior, Elsevier, vol. 38(2), pages 201-230, February.
    10. José Alcalde, 1994. "Exchange-proofness or divorce-proofness? Stability in one-sided matching markets," Review of Economic Design, Springer;Society for Economic Design, vol. 1(1), pages 275-287, December.
    11. Aziz, Haris & Brandt, Felix & Harrenstein, Paul, 2013. "Pareto optimality in coalition formation," Games and Economic Behavior, Elsevier, vol. 82(C), pages 562-581.
    12. Tayfun Sönmez & Suryapratim Banerjee & Hideo Konishi, 2001. "Core in a simple coalition formation game," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 18(1), pages 135-153.
    13. Yuichiro Kamada & Fuhito Kojima, 2015. "Efficient Matching under Distributional Constraints: Theory and Applications," American Economic Review, American Economic Association, vol. 105(1), pages 67-99, January.
    14. Ágnes Cseh & Tamás Fleiner & Petra Harján, 2019. "Pareto Optimal Coalitions of Fixed Size," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 4(1), pages 87-108, 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. Andreas Darmann, 2018. "Stable and Pareto optimal group activity selection from ordinal preferences," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(4), pages 1183-1209, November.
    2. Agnes Cseh & Tamas Fleiner & Petra Harjan, 2020. "Pareto optimal coalitions of fixed size," CERS-IE WORKING PAPERS 2005, Institute of Economics, Centre for Economic and Regional Studies.
    3. Vittorio Bilò & Angelo Fanelli & Michele Flammini & Gianpiero Monaco & Luca Moscardelli, 2018. "Nash Stable Outcomes in Fractional Hedonic Games: Existence, Efficiency and Computation," Post-Print hal-02089363, HAL.
    4. Hakan İnal, 2015. "Core of coalition formation games and fixed-point methods," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 45(4), pages 745-763, December.
    5. Papai, Szilvia, 2004. "Unique stability in simple coalition formation games," Games and Economic Behavior, Elsevier, vol. 48(2), pages 337-354, August.
    6. Peter Biro & Elena Iñarra & Elena Molis, 2014. "A new solution for the roommate problem. The Q-stable matchings," ThE Papers 14/04, Department of Economic Theory and Economic History of the University of Granada..
    7. Aziz, Haris & Brandt, Felix & Harrenstein, Paul, 2013. "Pareto optimality in coalition formation," Games and Economic Behavior, Elsevier, vol. 82(C), pages 562-581.
    8. Andreas Darmann & Edith Elkind & Sascha Kurz & Jérôme Lang & Joachim Schauer & Gerhard Woeginger, 2018. "Group activity selection problem with approval preferences," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(3), pages 767-796, September.
    9. Ana Mauleon & Elena Molis & Vincent Vannetelbosch & Wouter Vergote, 2014. "Dominance invariant one-to-one matching problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 43(4), pages 925-943, November.
    10. Biró, Péter & Iñarra, Elena & Molis, Elena, 2016. "A new solution concept for the roommate problem: Q-stable matchings," Mathematical Social Sciences, Elsevier, vol. 79(C), pages 74-82.
    11. Rothe, Jörg & Schadrack, Hilmar & Schend, Lena, 2018. "Borda-induced hedonic games with friends, enemies, and neutral players," Mathematical Social Sciences, Elsevier, vol. 96(C), pages 21-36.
    12. Jaeok Park, 2017. "Competitive equilibrium and singleton cores in generalized matching problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(2), pages 487-509, May.
    13. Ágnes Cseh & Tamás Fleiner & Petra Harján, 2019. "Pareto Optimal Coalitions of Fixed Size," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 4(1), pages 87-108, November.
    14. Dimitrov, D.A. & Sung, S.C., 2004. "Enemies and Friends in Hedonic Games : Individual Deviations, Stability and Manipulation," Other publications TiSEM c66aeb6a-a601-4927-888f-d, Tilburg University, School of Economics and Management.
    15. Mauleon, Ana & Roehl, Nils & Vannetelbosch, Vincent, 2019. "Paths to stability for overlapping group structures," Journal of Mathematical Economics, Elsevier, vol. 83(C), pages 19-24.
    16. Sung, Shao-Chin & Dimitrov, Dinko, 2010. "Computational complexity in additive hedonic games," European Journal of Operational Research, Elsevier, vol. 203(3), pages 635-639, June.
    17. Dinko Dimitrov & Peter Borm & Ruud Hendrickx & Shao Sung, 2006. "Simple Priorities and Core Stability in Hedonic Games," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 26(2), pages 421-433, April.
    18. Azar Abizada, 2019. "Exchange-stability in roommate problems," Review of Economic Design, Springer;Society for Economic Design, vol. 23(1), pages 3-12, June.
    19. Shao Sung & Dinko Dimitrov, 2007. "On Myopic Stability Concepts for Hedonic Games," Theory and Decision, Springer, vol. 62(1), pages 31-45, February.
    20. Alison Watts, 2006. "Formation of Segregated and Integrated Groups," Working Papers 2006.127, Fondazione Eni Enrico Mattei.

    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:2004.14640. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (arXiv administrators). General contact details of provider: http://arxiv.org/ .

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

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.