Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-08T17:34:56.977Z Has data issue: false hasContentIssue false
  • English
  • Français

A General Framework for Stable Roommates Problems using Answer Set Programming

Published online by Cambridge University Press:  22 September 2020

ESRA ERDEM Open the ORCID record for ESRA ERDEM [Opens in a new window] ,
MÜGE FIDAN ,
DAVID MANLOVE  and
PATRICK PROSSER
ESRA ERDEM
Affiliation:
Faculty of Engineering and Natural Sciences, Sabanci University, Istanbul, [email protected], [email protected]
MÜGE FIDAN
Affiliation:
Faculty of Engineering and Natural Sciences, Sabanci University, Istanbul, [email protected], [email protected]
DAVID MANLOVE
Affiliation:
School of Computing Science, University of Glasgow, Glasgow, [email protected], [email protected]
PATRICK PROSSER
Affiliation:
School of Computing Science, University of Glasgow, Glasgow, [email protected], [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

The Stable Roommates problem (SR) is characterized by the preferences of agents over other agents as roommates: each agent ranks all others in strict order of preference. A solution to SR is then a partition of the agents into pairs so that each pair shares a room, and there is no pair of agents that would block this matching (i.e., who prefers the other to their roommate in the matching). There are interesting variations of SR that are motivated by applications (e.g., the preference lists may be incomplete (SRI) and involve ties (SRTI)), and that try to find a more fair solution (e.g., Egalitarian SR). Unlike the Stable Marriage problem, every SR instance is not guaranteed to have a solution. For that reason, there are also variations of SR that try to find a good-enough solution (e.g., Almost SR). Most of these variations are NP-hard. We introduce a formal framework, called SRTI-ASP, utilizing the logic programming paradigm Answer Set Programming, that is provable and general enough to solve many of such variations of SR. Our empirical analysis shows that SRTI-ASP is also promising for applications.

Keywords

stable roommates problemanswer set programmingdeclarative problem solving
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 20 , Issue 6: 36th International Conference on Logic Programming Special Issue II , November 2020 , pp. 911 - 925
Check for updates
Creative Commons
Creative Common License - CCCreative Common License - BY
This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted re-use, distribution, and reproduction in any medium, provided the original work is properly cited
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Footnotes

*

This work has been partially supported by Sabanci University IRP Grant, and the Scottish Informatics and Computer Science Alliance DVF Programme. The third and fourth authors were supported by grants EP/P028306/1 and EP/P026842/1 from the Engineering and Physical Sciences Research Council, respectively.

References

Abraham, D. J., Biró, P., and Manlove, D. F. 2005. “almost stable” matchings in the roommates problem. In International Workshop on Approximation and Online Algorithms. Springer, 1–14.Google Scholar
Amendola, G. 2018. Solving the stable roommates problem using incoherent answer set programs. In Proc. of RiCeRcA.Google Scholar
Arkin, E. M., Bae, S. W., Efrat, A., Okamoto, K., Mitchell, J. S. B., and Polishchuk, V. 2009. Geometric stable roommates. Inf. Process. Lett. 109, 4, 219–224.CrossRefGoogle Scholar
Biró, P., Manlove, D. F., and McDermid, E. J. 2012. “Almost stable” matchings in the roommates problem with bounded preference lists. Theoretical Computer Science 432, 10–20.Google Scholar
Brewka, G., Eiter, T., and Truszczynski, M. 2016. Answer set programming: An introduction to the special issue. AI Magazine 37, 3, 5–6.CrossRefGoogle Scholar
Buccafurri, F., Leone, N., and Rullo, P. 2000. Enhancing disjunctive datalog by constraints. IEEE Trans. Knowl. Data Eng. 12, 5, 845–860.Google Scholar
Cooper, F. 2020. Fair and large stable matchings in the stable marriage and student-project allocation problems. Ph.D. thesis, University of Glasgow.Google Scholar
Cseh, Á., Irving, R. W., and Manlove, D. F. 2019. The stable roommates problem with short lists. Theory of Computing Systems 63, 1, 128–149.Google Scholar
Dantsin, E., Eiter, T., Gottlob, G., and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Comput. Surv. 33, 3, 374–425.Google Scholar
Dung, P. M. 1995. On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games. AIJ 77, 2, 321–357.Google Scholar
Erdem, E. and Lifschitz, V. 2003. Tight logic programs. TPLP 3, 4-5, 499–518.Google Scholar
Erdogan, S. T. and Lifschitz, V. 2004. Definitions in answer set programming. In Proc. of LPNMR.Google Scholar
Erdös, P. and Rényi, A. 1960. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences. 17–61.Google Scholar
Feder, T. 1992. A new fixed point approach for stable networks and stable marriages. Journal of Computer and System Sciences 45, 2, 233–284.Google Scholar
Gai, A.-T., Mathieu, F., de Montgolfier, F., and Reynier, J. 2007. Stratification in P2P networks: Application to BitTorrent. In Proc. of ICDCS. 30.Google Scholar
Gale, D. and Shapley, L. S. 1962. College admissions and the stability of marriage. The American Mathematical Monthly 69, 1, 9–15.Google Scholar
Gebser, M., Kaufmann, B., Kaminski, R., Ostrowski, M., Schaub, T., and Schneider, M. T. 2011. Potassco: The Potsdam Answer Set Solving Collection. AI Communications 24, 2, 107–124.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of ICLP. 1070–1080.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 365–385.Google Scholar
Gusfield, D. and Irving, R. W. 1989. The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge, MA, USA.Google Scholar
Irving, R. W. 1985. An efficient algorithm for the “stable roommates” problem. Journal of Algorithms 6, 4, 577–595.Google Scholar
Irving, R. W. 1994. Stable marriage and indifference. Discrete Applied Mathematics 48, 3, 261–272.CrossRefGoogle Scholar
Irving, R. W. and Manlove, D. F. 2002. The stable roommates problem with ties. Journal of Algorithms 43, 1, 85–105.Google Scholar
Irving, R. W., Manlove, D. F., and O’Malley, G. 2009. Stable marriage with ties and bounded length preference lists. Journal of Discrete Algorithms 7, 2, 213–219.Google Scholar
Knuth, D. 1997. Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms. In Volume 10 of CRM Proc. Mariages Stables (in English), 1976.Google Scholar
Kujansuu, E., Lindberg, T., and Makinen, E. 1999. The stable roomates problem and chess tournament pairings. Divulgaciones Matemáticas 7, 19–28.Google Scholar
Kunysz, A. 2016. The Strongly Stable Roommates Problem. In Proc. of ESA. Vol. 57. 60:1–60:15.Google Scholar
Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In Proc. of ICLP. 23–37.Google Scholar
Manlove, D. 1999. Stable marriage with ties and unacceptable partners.Google Scholar
MatchingToolkit. 2020. http://matwa.optimalmatching.com/.Google Scholar
McCarthy, J. 1998. Elaboration tolerance. In Proc. of CommonSense.Google Scholar
Mertens, S. 2005. Random stable matchings. Journal of Statistical Mechanics: Theory and Experiment 2005, 10, P10008–P10008.Google Scholar
Prosser, P. 2014. Stable roommates and constraint programming. In Proc. of CPAIOR. 15–28.Google Scholar
Ronn, E. 1990. Np-complete stable matching problems. Journal of Algorithms 11, 2, 285–304.Google Scholar
Roth, A. E., Sönmez, T., and Ünver, M. U. 2005. Pairwise kidney exchange. Journal of Economic Theory 125, 2, 151–188.Google Scholar
Scott, S. 2005. A study of stable marriage problems with ties. Ph.D. thesis, University of Glasgow.Google Scholar
Simons, P., Niemelae, I., and Soininen, T. 2002. Extending and implementing the stable model semantics. AIJ 138, 1, 181–234.Google Scholar
SRItoolkit. 2019. http://www.dcs.gla.ac.uk/ pat/roommates/distribution/ (2019-11-21).Google Scholar
Wu, Y., Caminada, M., and Gabbay, D. M. 2009. Complete extensions in argumentation coincide with 3-valued stable models in logic programming. Studia Logica 93, 2-3, 383–403.CrossRefGoogle Scholar