×

Hard variants of stable marriage. (English) Zbl 1050.68171

Summary: The Stable Marriage Problem and its many variants have been widely studied in the literature, partly because of the inherent appeal of the problem, partly because of the elegance of the associated structures and algorithms, and partly because of important practical applications, such as the National Resident Matching Program [J. Roth, Political Economy 92, 991–1016 (1984)] and similar large-scale matching schemes. Here, we present the first comprehensive study of variants of the problem in which the preference lists of the participants are not necessarily complete and not necessarily totally ordered. We show that, under surprisingly restrictive assumptions, a number of these variants are hard, and hard to approximate. The key observation is that, in contrast to the case where preference lists are complete or strictly ordered (or both), a given problem instance may admit stable matchings of different sizes. In this setting, examples of problems that are hard are: finding a stable matching of maximum or minimum size, determining whether a given pair is stable – even if the indifference takes the form of ties on one side only, the ties are at the tails of lists, there is at most one tie per list, and each tie is of length 2; and finding, or approximating, both an ‘egalitarian’ and a ‘minimum regret’ stable matching. However, we give a 2-approximation algorithm for the problems of finding a stable matching of maximum or minimum size. We also discuss the significant implications of our results for practical matching schemes.

MSC:

68W25 Approximation algorithms
05A05 Permutations, words, matrices
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Canadian Resident Matching Service, How the matching algorithm works, Web document available at; Canadian Resident Matching Service, How the matching algorithm works, Web document available at
[2] Feder, T., A new fixed point approach for stable networks and stable marriages, J. Comput. System Sci., 45, 233-284 (1992) · Zbl 0772.68052
[3] Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Amer. Math. Monthly, 69, 9-15 (1962) · Zbl 0109.24403
[4] Gale, D.; Sotomayor, M., Some remarks on the stable matching problem, Discrete Appl. Math., 11, 223-232 (1985) · Zbl 0596.90054
[5] Gusfield, D., Three fast algorithms for four problems in stable marriage, SIAM J. Comput., 16, 1, 111-128 (1987) · Zbl 0635.68036
[6] Gusfield, D.; Irving, R. W., The Stable Marriage Problem: Structure and Algorithms (1989), MIT Press: MIT Press Cambridge, MA · Zbl 0703.68046
[7] Horton, J. D.; Kilakos, K., Minimum edge dominating sets, SIAM J. Discrete Math., 6, 375-387 (1993) · Zbl 0782.05083
[8] Irving, R. W., An efficient algorithm for the “stable roommates” problem, J. Algorithms, 6, 577-595 (1985) · Zbl 0581.05001
[9] R.W. Irving, On the stable room-mates problem, Tech. Report CSC/86/R5 University of Glasgow, Department of Computing Science, 1986.; R.W. Irving, On the stable room-mates problem, Tech. Report CSC/86/R5 University of Glasgow, Department of Computing Science, 1986.
[10] Irving, R. W., Stable marriage and indifference, Discrete Appl. Math., 48, 261-272 (1994) · Zbl 0796.05078
[11] Irving, R. W., Matching medical students to pairs of hospitals: a new variation on an old theme, (Proc. ESA ’98: the 6th European Symp. on Algorithms, Lecture Notes in Computer Science, vol. 1461 (1998), Springer: Springer Berlin), 381-392 · Zbl 0929.90074
[12] Irving, R. W.; Leather, P.; Gusfield, D., An efficient algorithm for the “optimal” stable marriage, J. Assoc. Comput. Mach., 34, 3, 532-543 (1987)
[13] Irving, R. W.; Manlove, D. F.; Scott, S., The Hospitals/Residents problem with Ties, (Proc. SWAT 2000: the 7th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, vol. 1851 (2000), Springer: Springer Berline), 259-271 · Zbl 0966.91500
[14] Iwama, K.; Manlove, D.; Miyazaki, S.; Morita, Y., Stable marriage with incomplete lists and ties, (Proc ICALP ’99: the 26th Internat. Colloq. on Automata, Languages, and Programming, Lecture Notes in Computer Science, vol. 1644 (1999), Springer: Springer Berlin), 443-452 · Zbl 0948.90155
[15] D.E. Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, CRM Proceedings and Lecture Notes, vol. 10, American Mathematical Society, Providence, RI, 1997. (English translation of Marriages Stables, Les Presses de L’Université de Montréal, 1976).; D.E. Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, CRM Proceedings and Lecture Notes, vol. 10, American Mathematical Society, Providence, RI, 1997. (English translation of Marriages Stables, Les Presses de L’Université de Montréal, 1976).
[16] G.M. Low, Matching medical students to hospital posts in the West of Scotland, Master’s Thesis, University of Glasgow, Department of Computing Science, 1997.; G.M. Low, Matching medical students to hospital posts in the West of Scotland, Master’s Thesis, University of Glasgow, Department of Computing Science, 1997.
[17] D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki, Y. Morita, Hard variants of stable marriage, Tech. Report TR-1999-43, University of Glasgow, Department of Computing Science, September 1999.; D.F. Manlove, R.W. Irving, K. Iwama, S. Miyazaki, Y. Morita, Hard variants of stable marriage, Tech. Report TR-1999-43, University of Glasgow, Department of Computing Science, September 1999. · Zbl 1050.68171
[18] E. Ronn, On the complexity of stable matchings with and without ties, Ph.D. Thesis, Yale University, 1986.; E. Ronn, On the complexity of stable matchings with and without ties, Ph.D. Thesis, Yale University, 1986.
[19] E. Ronn, NP-complete stable matching problemsJ. Algorithms (11) 1990.; E. Ronn, NP-complete stable matching problemsJ. Algorithms (11) 1990. · Zbl 0705.68065
[20] Roth, A. E., The evolution of the labor market for medical interns and residents: a case study in game theory, J. Political Economy, 92, 6, 991-1016 (1984)
[21] Roth, A. E., On the allocation of residents to rural hospitals: a general property of two-sided matching markets, Econometrica, 54, 425-427 (1986)
[22] Roth, A. E.; Sotomayor, M. A.O., Two-sided matching: a study in game-theoretic modeling and analysis, Econometric Society Monographs, vol. 18 (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0726.90003
[23] Yannakakis, M.; Gavril, F., Edge dominating sets in graphs, SIAM J. Appl. Math., 18, 1, 364-372 (1980) · Zbl 0455.05047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.