Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-18T12:48:26.800Z Has data issue: false hasContentIssue false
  • English
  • Français

Solving stable matching problems using answer set programming

Published online by Cambridge University Press:  07 March 2016

SOFIE DE CLERCQ ,
STEVEN SCHOCKAERT ,
MARTINE DE COCK  and
ANN NOWE
SOFIE DE CLERCQ
Affiliation:
Department of Applied Mathematics, Computer Science & Statistics, Ghent University, Ghent, Belgium (e-mail: [email protected])
STEVEN SCHOCKAERT
Affiliation:
School of Computer Science & Informatics, Cardiff University, Cardiff, UK (e-mail: [email protected])
MARTINE DE COCK
Affiliation:
Center for Data Science, UW Tacoma, Tacoma, US Deparment of Applied Mathematics, Computer Science & Statistics, Ghent University, Ghent, Belgium (e-mail: [email protected])
ANN NOWE
Affiliation:
Computational Modeling Lab, Vrije Universiteit Brussel, Brussels, Belgium (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Since the introduction of the stable marriage problem (SMP) by Gale and Shapley (1962), several variants and extensions have been investigated. While this variety is useful to widen the application potential, each variant requires a new algorithm for finding the stable matchings. To address this issue, we propose an encoding of the SMP using answer set programming (ASP), which can straightforwardly be adapted and extended to suit the needs of specific applications. The use of ASP also means that we can take advantage of highly efficient off-the-shelf solvers. To illustrate the flexibility of our approach, we show how our ASP encoding naturally allows us to select optimal stable matchings, i.e. matchings that are optimal according to some user-specified criterion. To the best of our knowledge, our encoding offers the first exact implementation to find sex-equal, minimum regret, egalitarian or maximum cardinality stable matchings for SMP instances in which individuals may designate unacceptable partners and ties between preferences are allowed.

Keywords

Answer set programmingLogic rulesStable marriage problemOptimal stable matchings
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 16 , Special Issue 3: Special Issue on the International Web Rule Symposia 2012-2014 , May 2016 , pp. 247 - 268
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Baral, C. 2003. Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, New York, USA.CrossRefGoogle Scholar
Biró, P. and McDermid, E. 2010. Three-sided stable matchings with cyclic preferences. Algorithmica 58, 1, 5–18.CrossRefGoogle Scholar
Brewka, G., Eiter, T. and Truszczyński, M. 2011. Answer set programming at a glance. Communications of the ACM 54, 12, 92–103.CrossRefGoogle Scholar
De Clercq, S., Schockaert, S., De Cock, M. and Nowé, A. 2013. Modeling stable matching problems with answer set programming. In Proc. RuleML 2013. Morgenstern, L., Stefaneas, P., Lévy, F., Wyner, A. and Paschke, A., Eds. Lecture Notes in Computer Science, Springer Berlin Heidelberg, Berlin, Heidelberg, vol. 8035. 68–83.Google Scholar
Dung, P. 1995. An argumentation-theoretic foundation for logic programming. The Journal of Logic Programming 22, 2, 151–177.CrossRefGoogle Scholar
Eiter, T. and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Annals of Mathematics and Artificial Intelligence 15, 3–4, 289–323.CrossRefGoogle Scholar
Erdem, E. and Lifschitz, V. 2003. Tight logic programs. Theory and Practice of Logic Programming 3, 499–518.CrossRefGoogle Scholar
Faber, W., Pfeifer, G., Leone, N., Dell'Armi, T. and Ielpa, G. 2008. Design and implementation of aggregate functions in the DLV system. Theory and Practice of Logic Programming 8, 5–6, 545–580.CrossRefGoogle Scholar
Gale, D. and Shapley, L. 1962. College admissions and the stability of marriage. The American Mathematical Monthly 69, 1, 9–15.CrossRefGoogle Scholar
Gale, D. and Sotomayor, M. 1985. Some remarks on the stable matching problem. Discrete Applied Mathematics 11, 223–232.CrossRefGoogle Scholar
Gärdenfors, P. 1975. Match making: Assignments based on bilateral preferences. Behavioral Science 20, 3, 166–173.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. ICLP/SLP, Kowalski, R. and Bowen, K., Eds. MIT Press, Cambridge, vol. 88. 1070–1080.Google Scholar
Gusfield, D. 1987. Three fast algorithms for four problems in stable marriage. SIAM Journal on Computing 16, 1, 111–128.CrossRefGoogle Scholar
Irving, R. 1994. Stable marriage and indifference. Discrete Applied Mathematics 48, 3, 261–272.CrossRefGoogle Scholar
Irving, R. 2003. Greedy matchings. Tech. Rep. TR-2003-136, Dept. of Computing Science, University of Glasgow. April.Google Scholar
Irving, R. 2007. The cycle roommates problem: A hard case of kidney exchange. Information Processing Letters 103, 1, 1–4.CrossRefGoogle Scholar
Irving, R., Leather, P. and Gusfield, D. 1987. An efficient algorithm for the “optimal” stable marriage. Journal of the ACM 34, 3, 532–543.CrossRefGoogle Scholar
Iwama, K. and Miyazaki, S. 2008. A survey of the stable marriage problem and its variants. In Proc. of the Interntional Conference on Informatics Education and Research for Knowledge-Circulating Society. Kurohashi, S., Sumi, Y., Nakamura, Y. and Tanaka, K., Eds. ICKS'08. IEEE Computer Society, IEEE Computer Society Washington, DC, USA, 131–136.Google Scholar
Iwama, K., Miyazaki, S. and Yanagisawa, H. 2010. Approximation algorithms for the sex-equal stable marriage problem. ACM Transactions on Algorithms (TALG) 7, 1, 2.Google Scholar
Janhunen, T. 2004. Representing normal programs with clauses. In Proc. of the 16th European Conference on Artificial Intelligence. López De Mántaras, R., and Saitta, L., Eds. IOS Press, Amsterdam, 358–362.Google Scholar
Knuth, D. 1976. Mariages Stables. Les Presses de L'Université de Montréal, Montréal.Google Scholar
Manlove, D. 2013. Algorithmics of Matching under Preferences. Series on Theoretical Computer Science, vol. 2. World Scientific Publishing, Singapore.CrossRefGoogle Scholar
Manlove, D., Irving, R., Iwama, K., Miyazaki, S. and Morita, Y. 2002. Hard variants of stable marriage. Theoretical Computer Science 276, 1–2, 261–279.CrossRefGoogle Scholar
Marek, V., Nerode, A. and Remmel, J. 1990. A theory of nonmonotonic rule systems I. Annals of Mathematics and Artificial Intelligence 1, 241–273.CrossRefGoogle Scholar
McDermid, E. and Irving, R. 2014. Sex-equal stable matchings: Complexity and exact algorithms. Algorithmica 68, 3, 545–570.CrossRefGoogle Scholar
Ng, C. and Hirschberg, D. 1991. Three-dimensional stable matching problems. SIAM Journal on Discrete Mathematics 4, 245–252.CrossRefGoogle Scholar
Roth, A., Sömnez, T. and Ünver, M. 2005. Pairwise kidney exchange. Journal of Economic Theory 125, 2, 151–188.CrossRefGoogle Scholar
Roth, A. and Sotomayor, M. 1990. Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Xu, H. and Li, B. 2011. Egalitarian stable matching for VM migration in cloud computing. In Proc. Computer Communications Workshops (INFOCOM WKSHPS), 2011 IEEE Conference on. IEEE, 631–636.Google Scholar
Supplementary material: PDF

de Clercq supplementary material

Online Appendix

Download de Clercq supplementary material(PDF)
PDF 284.1 KB