Document Open Access Logo

Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space

Authors Jiehua Chen, Sanjukta Roy

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2022.36.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Solution concepts in game theory
  • Theory of computation → Computational geometry
Keywords
  • stable matchings
  • multidimensional stable roommates
  • Euclidean preferences
  • coalition formation games
  • stable cores
  • NP-hardness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

We investigate the Euclidean 𝖽-Dimensional Stable Roommates problem, which asks whether a given set V of 𝖽⋅ n points from the 2-dimensional Euclidean space can be partitioned into n disjoint (unordered) subsets Π = {V₁,…,V_{n}} with |V_i| = 𝖽 for each V_i ∈ Π such that Π is {stable}. Here, {stability} means that no point subset W ⊆ V is blocking Π, and W is said to be {blocking} Π if |W| = 𝖽 such that ∑_{w' ∈ W}δ(w,w') < ∑_{v ∈ Π(w)}δ(w,v) holds for each point w ∈ W, where Π(w) denotes the subset V_i ∈ Π which contains w and δ(a,b) denotes the Euclidean distance between points a and b. Complementing the existing known polynomial-time result for 𝖽 = 2, we show that such polynomial-time algorithms cannot exist for any fixed number 𝖽 ≥ 3 unless P=NP. Our result for 𝖽 = 3 answers a decade-long open question in the theory of Stable Matching and Hedonic Games [Iwama et al., 2007; Arkin et al., 2009; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; Vladimir G. Deineko and Gerhard J. Woeginger, 2013; David F. Manlove, 2013].

Cite As Get BibTex

Jiehua Chen and Sanjukta Roy. Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.36

Author Details

Jiehua Chen
  • TU Wien, Austria
Sanjukta Roy
  • Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
  • TU Wien, Austria

Funding

  • Chen, Jiehua: Vienna Science and Technology Fund (WWTF) grant VRG18-012.
  • Roy, Sanjukta: This work was done when SR was affiliated with TU Vienna, and was supported by Vienna Science and Technology Fund (WWTF) grant VRG18-012.

References

  1. Esther M Arkin, Sang Won Bae, Alon Efrat, Kazuya Okamoto, Joseph SB Mitchell, and Valentin Polishchuk. Geometric stable roommates. Information Processing Letters, 109(4):219-224, 2009. Google Scholar
  2. Giuseppe Di Battista, Giuseppe Liotta, and Francesco Vargiu. Spirality and optimal orthogonal drawings. SIAM Journal on Computing, 27(6):1764-1811, 1998. Google Scholar
  3. Vittorio Bilò, Gianpiero Monaco, and Luca Moscardelli. Hedonic games with fixed-size coalitions. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI '22), 2022. To appear. Google Scholar
  4. Péter Biró and Eric McDermid. Three-sided stable matchings with cyclic preferences. Algorithmica, 58(1):5-18, 2010. Google Scholar
  5. Robert Bredereck, Jiehua Chen, Ugo P. Finnendahl, and Rolf Niedermeier. Stable roommate with narcissistic, single-peaked, and single-crossing preferences. Autonomous Agents and Multi-Agent Systems, 34(53):1-29, 2020. Google Scholar
  6. Robert Bredereck, Klaus Heeger, Dusan Knop, and Rolf Niedermeier. Multidimensional stable roommates with master list. In Proceedings of the 16th International Conference on Web and Internet Economics (WINE '20), volume 12495 of LNCS, pages 59-73, 2020. Google Scholar
  7. Jiehua Chen, Gergely Csáji, Sanjukta Roy, and Sofia Simola. Cores in friend-oriented hedonic games: Verification is surprisingly harder than searching. Technical report, arXiv, 2022. URL: http://arxiv.org/abs/2203.09655.
  8. Jiehua Chen and Sanjukta Roy. Multi-dimensional stable roommates in 2-dimensional Euclidean space. Technical report, arXiv, 2022. URL: http://arxiv.org/abs/2108.03868.
  9. Ágnes Cseh, Tamás Fleiner, and Petra Harján. Pareto optimal coalitions of fixed size. Journal of Mechanism and Institution Design, 4(1):87-108, 2019. Google Scholar
  10. Vladimir G. Deineko and Gerhard J. Woeginger. Two hardness results for core stability in hedonic coalition formation games. Discrete Appllied Mathematics, 161(13-14):1837-1842, 2013. Google Scholar
  11. Dinko Dimitrov, Peter Borm, Ruud Hendrickx, and Shao Chin Sung. Simple priorities and core stability in hedonic games. Social Choice and Welfare, 26:421-433, 2006. Google Scholar
  12. Jacques H. Dréze and Joseph Greenberg. Hedonic coalitions: Optimality and stability. Econometrica, 48(4):98-1003, 1980. Google Scholar
  13. Kimmo Eriksson, Jonas Sjöstrand, and Pontus Strimling. Three-dimensional stable matching with cyclic preferences. Mathematical Social Sciences, 52(1):77-87, 2006. Google Scholar
  14. David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 120(5):386-391, 1962. Google Scholar
  15. Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  16. Chien-Chung Huang. Two’s company, three’s a crowd: Stable family and threesome roommates problems. In Proceedings of the 15th Annual European Symposium (ESA '07), volume 4698 of LNCS, pages 558-569, 2007. Google Scholar
  17. Robert W. Irving. An efficient algorithm for the `stable roommates' problem. Journal of Algorithms, 6(4):577-595, 1985. Google Scholar
  18. Kazuo Iwama, Shuichi Miyazaki, and Kazuya Okamoto. Stable roommates problem with triple rooms. In Proceedings of the 10th KOREA-JAPAN joint workshop on algorithms and computation (WAAC '07), pages 105-112, 2007. Google Scholar
  19. Donald Ervin Knuth. Mariages stables et leurs relations avec d'autres problemes combinatoires: introduction a l'analysis mathematique des algorithmes. Les Presses de l'Université de Montréal, 1976. Google Scholar
  20. Chi-Kit Lam and C Gregory Plaxton. On the existence of three-dimensional stable matchings with cyclic preferences. In Proceedings of the 12th International Symposium on Algorithmic Game Theory (SAGT '19), volume 11801 of LNCS, pages 329-342, 2019. Google Scholar
  21. David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. World Scientific, 2013. Google Scholar
  22. Michael McKay and David F. Manlove. The three-dimensional stable roommates problem with additively separable preferences. In Proceedings of the 14th International Symposium on Algorithmic Game Theory (SAGT '21), volume 12885 of LNCS, pages 266-280, 2021. Google Scholar
  23. Cristopher Moore and J. M. Robson. Hard tiling problems with simple tiles. Discrete & Computational Geometry, 26(4):573-590, 2001. Google Scholar
  24. Kazunori Ohta, Nathanaël Barrot, Anisse Ismaili, Yuko Sakurai, and Makoto Yokoo. Core stability in hedonic games among friends and enemies: Impact of neutrals. In Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI '17), pages 359-365, 2017. Google Scholar
  25. Leslie G. Valiant. Universality considerations in VLSI circuits. IEEE Transactions on Computers, C-30(2):13-140, 1981. Google Scholar
  26. Gerhard J. Woeginger. Core stability in hedonic coalition formation. In Proceedings of the 39th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM '13), volume 7741 of LNCS, pages 33-50, 2013. Google Scholar
  27. Mason Wright and Yevgeniy Vorobeychik. Mechanism design for team formation. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI '15), pages 1050-1056, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact