Document Open Access Logo

How Hard Is It to Satisfy (Almost) All Roommates?

Authors Jiehua Chen, Danny Hermelin, Manuel Sorge, Harel Yedidsion

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.35.pdf
  • Filesize: 0.6 MB
  • 15 pages

Document Identifiers

Author Details

Jiehua Chen
  • Ben-Gurion University of the Negev, Beer Sheva, Israel
Danny Hermelin
  • Ben-Gurion University of the Negev, Beer Sheva, Israel
Manuel Sorge
  • Ben-Gurion University of the Negev, Beer Sheva, Israel
Harel Yedidsion
  • Ben-Gurion University of the Negev, Beer Sheva, Israel

Cite As Get BibTex

Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion. How Hard Is It to Satisfy (Almost) All Roommates?. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.35

Abstract

The classic Stable Roommates problem (the non-bipartite generalization of the well-known Stable Marriage problem) asks whether there is a stable matching for a given set of agents, i.e. a partitioning of the agents into disjoint pairs such that no two agents induce a blocking pair. Herein, each agent has a preference list denoting who it prefers to have as a partner, and two agents are blocking if they prefer to be with each other rather than with their assigned partners.
Since stable matchings may not be unique, we study an NP-hard optimization variant of Stable Roommates, called Egal Stable Roommates, which seeks to find a stable matching with a minimum egalitarian cost gamma, i.e. the sum of the dissatisfaction of the agents is minimum. The dissatisfaction of an agent is the number of agents that this agent prefers over its partner if it is matched; otherwise it is the length of its preference list. We also study almost stable matchings, called Min-Block-Pair Stable Roommates, which seeks to find a matching with a minimum number beta of blocking pairs. Our main result is that Egal Stable Roommates parameterized by gamma is fixed-parameter tractable, while Min-Block-Pair Stable Roommates parameterized by beta is W[1]-hard, even if the length of each preference list is at most five.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Algorithmic game theory
  • Mathematics of computing → Combinatorial optimization
Keywords
  • NP-hard problems Data reduction rules Kernelizations Parameterized complexity analysis and algorithmics

Metrics

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

Related Versions

References

  1. National resident matching program website. URL: http://www.nrmp.org.
  2. Scottish foundation allocation scheme website. URL: http://www.nes.scot.nhs.uk/sfas.
  3. Atila Abdulkadiroǧlu, Parag A. Pathak, and Alvin E. Roth. The Boston public school match. American Economic Review, 95(2):368-–371, 2005. Google Scholar
  4. Atila Abdulkadiroǧlu, Parag A. Pathak, and Alvin E. Roth. The New York City high school match. American Economic Review, 95(2):364-367, 2005. Google Scholar
  5. David Abraham, Ning Chen, Vijay Kumar, and Vahab S. Mirrokni. Assignment problems in rental markets. In Proceedings of the Second International Workshop on Internet and Network Economics (WINE '06), pages 198-213, 2006. Google Scholar
  6. David J. Abraham, Péter Biró, and David Manlove. "Almost stable" matchings in the roommates problem. In Proceedings of the Third International Workshop on Approximation and Online Algorithms (WAOA '05), pages 1-14, 2005. URL: http://dx.doi.org/10.1007/11671411_1.
  7. Mourad Baïou and Michel Balinski. Student admissions and faculty recruitment. Theoretical Computer Science, 322(2):245-265, 2004. Google Scholar
  8. Péter Biró and Sofya Kiselgof. College admissions with stable score-limits. Central European Journal of Operations Research, 23(4):727-741, 2015. URL: http://dx.doi.org/10.1007/s10100-013-0320-9.
  9. Péter Biró, David Manlove, and Eric McDermid. "Almost stable" matchings in the Roommates problem with bounded preference lists. Theoretical Computer Science, 432:10-20, 2012. Google Scholar
  10. Péter Biró, David Manlove, and Shubham Mittal. Size versus stability in the marriage problem. Theoretical Computer Science, 411(16-18):1828-1841, 2010. Google Scholar
  11. Nader H. Bshouty. Linear time Constructions of some d-Restriction Problems. In Proceedings of the 9th International Conference on Algorithms and Complexity (CIAC '15), volume 9079 of Lecture Notes in Computer Science, pages 74-88. Springer, 2015. Google Scholar
  12. Nader H. Bshouty and Ariel Gabizon. Almost Optimal Cover-Free Families. In Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC '17), volume 10236 of Lecture Notes in Computer Science, pages 140-151. Springer, 2017. Google Scholar
  13. Leizhen Cai, Siu Man Chan, and Siu On Chan. Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems. In Proceedings of the Second International Workshop on Parameterized and Exact Computation (IWPEC '06), pages 239-250. Springer, 2006. Google Scholar
  14. Jiehua Chen, Danny Hermelin, Manuel Sorge, and Harel Yedidsion. How hard is it to satisfy (almost) all roommates? Technical report, arXiv:1707.04316 [cs.CC], 2018. Google Scholar
  15. Jiehua Chen, Rolf Niedermeier, and Piotr Skowron. Stable marriage with multi-modal preferences. Technical report, arXiv:1801.02693 [cs.MA,cs.DS], 2018. Google Scholar
  16. Yan. Chen and Tayfun Sönmez. Improving efficiency of on-campus housing: An experimental study. American Economic Review, 92(5):1669–-1686, 2002. Google Scholar
  17. Ágnes Cseh, Robert W. Irving, and David F. Manlove. The stable roommates problem with short lists. In Proceedings of the 9th International Symposium on Algorithmic Game Theory (SAGT '16), pages 207-219, 2016. Google Scholar
  18. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  19. Kimmo Eriksson and Olle Häggström. Instability of matchings in decentralized markets with various preference structures. International Journal of Game Theory, 36(3):409-420, 2008. Google Scholar
  20. Tomás Feder. A new fixed point approach for stable networks and stable marriages. Journal of Computer and System Sciences, 45(2):233-284, 1992. Google Scholar
  21. Anh-Tuan Gai, Dmitry Lebedev, Fabien Mathieu, Fabien de Montgolfier, Julien Reynier, and Laurent Viennot. Acyclic preference systems in P2P networks. In Proceedings of the 13th International Euro-Par Conference, pages 825-834, 2007. Google Scholar
  22. D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 120(5):386-391, 2013. URL: http://dx.doi.org/10.4169/amer.math.monthly.120.05.386.
  23. Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Balanced stable marriage: How close is close enough? Technical report, arXiv:1707.09545 [cs.DS], 2017. Google Scholar
  24. Dan Gusfield and Robert W. Irving. The Stable marriage problem-Structure and algorithms. Foundations of computing series. MIT Press, 1989. Google Scholar
  25. Magnús M. Halldórsson, Robert W. Irving, Kazuo Iwama, David Manlove, Shuichi Miyazaki, Yasufumi Morita, and Sandy Scott. Approximability results for stable marriage problems with ties. Theoretical Computer Science, 306(1-3):431-447, 2003. URL: http://dx.doi.org/10.1016/S0304-3975(03)00321-9.
  26. Koki Hamada, Kazuo Iwama, and Shuichi Miyazaki. An improved approximation lower bound for finding almost stable maximum matchings. Information Processing Letters, 109(18):1036-1040, 2009. Google Scholar
  27. Aanund Hylland and Richard Zeckhauser. The efficient allocation of individuals to positions. Journal of Political Economy, 87(2):293-314, 1979. Google Scholar
  28. Robert W. Irving. An efficient algorithm for the `stable roommates' problem. Journal of Algorithms, 6(4):577-595, 1985. Google Scholar
  29. Robert W. Irving. Optimal stable marriage. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 1470-1473. Springer, 2016. URL: http://dx.doi.org/10.1007/978-1-4939-2864-4_271.
  30. Robert W. Irving. Stable marriage. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pages 2060-2064. Springer, 2016. URL: http://dx.doi.org/10.1007/978-1-4939-2864-4_393.
  31. Robert W. Irving, Paul Leather, and Dan Gusfield. An efficient algorithm for the `optimal' stable marriage. Journal of the ACM, 34(3):532-543, 1987. URL: http://dx.doi.org/10.1145/28869.28871.
  32. Donald Knuth. Mariages Stables. Les Presses de L'Université de Montréal, 1976. Google Scholar
  33. Eija Kujansuu, Tuukka Lindberg, and Erkki Mäkinen. The Stable Roommates problem and chess tournament pairings. Divulgaciones Matemáticas, 7(1):19-28, 1999. Google Scholar
  34. Dmitry Lebedev, Fabien Mathieu, Laurent Viennot, Anh-Tuan Gai, Julien Reynier, and Fabien de Montgolfier. On using matching theory to understand P2P network design. In Proceedings of the International Network Optimization Conference (INOC 2007), pages 1-7, 2007. Google Scholar
  35. David Manlove. Hospitals/residents problem. In Ming-Yang Kao, editor, Encyclopedia of Algorithms. Springer, 2008. Google Scholar
  36. David Manlove, Robert W. Irving, Kazuo Iwama, Shuichi Miyazaki, and Yasufumi Morita. Hard variants of stable marriage. Theoretical Computer Science, 276(1-2):261-279, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00206-7.
  37. David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. WorldScientific, 2013. URL: http://dx.doi.org/10.1142/8591.
  38. David F. Manlove and Gregg O'Malley. Paired and altruistic kidney donation in the UK: Algorithms and experimentation. ACM Journal of Experimental Algorithmics, 19(1), 2014. URL: http://dx.doi.org/10.1145/2670129.
  39. Dániel Marx and Ildikó Schlotter. Parameterized complexity and local search approaches for the stable marriage problem with ties. Algorithmica, 58(1):170-187, 2010. URL: http://dx.doi.org/10.1007/s00453-009-9326-z.
  40. Dániel Marx and Ildikó Schlotter. Stable assignment with couples: Parameterized complexity and local search. Discrete Optimization, 8(1):25-40, 2011. URL: http://dx.doi.org/10.1016/j.disopt.2010.07.004.
  41. D. G. McVitie and L. B. Wilson. The Stable Marriage problem. Communications of the ACM, 14(7):486-490, 1971. Google Scholar
  42. Kitty Meeks and Baharak Rastegari. Solving hard stable matching problems involving groups of similar agents. Technical report, arXiv:1708.04109 [cs.GT], 2017. Google Scholar
  43. Matthias Mnich and Ildikó Schlotter. Stable marriage with covering constraints-A complete computational trichotomy. In Proceedings of the 10th International Symposium on Algorithmic Game Theory (SAGT '17), pages 320-332, 2017. URL: http://dx.doi.org/10.1007/978-3-319-66700-3_25.
  44. M. Naor, L. J. Schulman, and A. Srinivasan. Splitters and near-optimal derandomization. In Proceedings of 36th Annual IEEE Symposium on Foundations of Computer Science, pages 182-191, 1995. Google Scholar
  45. Muriel Niederle and Alvin E. Roth. Market culture: How norms governing exploding offers affect market performance. Working Paper 10256, National Bureau of Economic Research, February 2004. Google Scholar
  46. Boris Pittel and Robert W. Irving. An upper bound for the solvability of a random stable roommates instance. Random Structures and Algorithms, 5(3):465-487, 1994. Google Scholar
  47. Eytan Ronn. NP-complete stable matching problems. Journal of Algorithms, 11(2):285-304, 1990. URL: http://dx.doi.org/10.1016/0196-6774(90)90007-2.
  48. Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver. Pairwise kidney exchange. Journal of Economic Theory, 125(2):151-188, 2005. URL: http://dx.doi.org/10.1016/j.jet.2005.04.004.
  49. Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver. Efficient kidney exchange: Coincidence of wants in markets with compatibility-based preferences. American Economic Review, 97(3):828-851, 2007. Google Scholar
  50. Alvin E. Roth and Marilda A. Oliveira Sotomayor. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, 1992. Part of Econometric Society Monographs. Google Scholar
  51. Chung-Piaw Teo and Jay Sethuraman. On a cutting plane heuristic for the stable roommates problem and its applications. European Journal of Operational Research, 123(1):195-205, 2000. 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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact