×

Local search approaches in stable matching problems. (English) Zbl 1461.05163

Summary: The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical formulation, \(n\) men and \(n\) women express their preferences (via a strict total order) over the members of the other sex. Solving an SM problem means finding a stable marriage where stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. We consider both the classical stable marriage problem and one of its useful variations (denoted SMTI (Stable Marriage with Ties and Incomplete lists)) where the men and women express their preferences in the form of an incomplete preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists, and we try to find a stable matching that marries as many people as possible. Whilst the SM problem is polynomial to solve, the SMTI problem is NP-hard. We propose to tackle both problems via a local search approach, which exploits properties of the problems to reduce the size of the neighborhood and to make local moves efficiently. We empirically evaluate our algorithm for SM problems by measuring its runtime behavior and its ability to sample the lattice of all possible stable marriages. We evaluate our algorithm for SMTI problems in terms of both its runtime behavior and its ability to find a maximum cardinality stable marriage. Experimental results suggest that for SM problems, the number of steps of our algorithm grows only as \(O(n \log(n))\), and that it samples very well the set of all stable marriages. It is thus a fair and efficient approach to generate stable marriages. Furthermore, our approach for SMTI problems is able to solve large problems, quickly returning stable matchings of large and often optimal size, despite the NP-hardness of this problem.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
91B68 Matching models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gusfield, D.; Irving, R.W.; ; The Stable Marriage Problem: Structure and Algorithms: Boston, MA 1989; . · Zbl 0703.68046
[2] Gale, D.; Shapley, L.S.; College admissions and the stability of marriage; Am. Math. Mon.: 1962; Volume 69 ,9-15. · Zbl 0109.24403
[3] Roth, A.E.; On the allocation of residents to rural hospitals: A general property of two-sided matching markets; Econometrica: 1986; Volume 54 ,425-427.
[4] Manlove, D.F.; Irving, R.W.; Iwama, K.; Miyazaki, S.; Morita, Y.; Hard variants of stable marriage; Theor. Comput. Sci.: 2002; Volume 276 ,261-279. · Zbl 1050.68171
[5] Knuth, D.E.; ; Marriages Stables: du l’Universitè de Montrèal 1976; . · Zbl 0358.68057
[6] Gent, I.P.; Prosser, P.; An empirical study of the stable marriage problem with ties and incomplete lists; Proceedings of ECAI 2002: ; ,141-145.
[7] Gelain, M.; Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Local search algorithms on the stable marriage problem: Experimental studies; Proceedings of ECAI 2010: ; ,1085-1086.
[8] Gelain, M.; Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Local search for stable marriage problems with ties and incomplete lists; Proceedings of PRICAI 2010, LNCS 6230: ; ,64-75.
[9] Gelain, M.; Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Procedural fairness in stable marriage problems; Proceedings of AAMAS 2011: ; ,1209-1210.
[10] Gusfield, D.; Three fast algorithms for four problems in stable marriage; SIAM Journal on Computing: 1987; Volume 16 ,111-128. · Zbl 0635.68036
[11] Irving, R.W.; Leather, P.; Gusfield, D.; An efficient algorithm for the “optimal” stable marriage; J. ACM: 1987; Volume 34 ,532-543.
[12] Roth, A.E.; Vate, J.H.V.; Random paths to stability in two-sided matching; Econometrica: 1990; Volume 58 ,1475-1480. · Zbl 0731.90007
[13] Halldórsson, M.M.; Irving, R.W.; Iwama, K.; Manlove, D.; Miyazaki, S.; Morita, Y.; Scott, S.; Approximability results for stable marriage problems with ties; Theor. Comput. Sci.: 2003; Volume 306 ,431-447. · Zbl 1060.68085
[14] Scott, S.; A study of stable marriage problems with ties; Ph.D. Thesis: Glasgow, UK 2005; .
[15] Halldórsson, M.M.; Iwama, K.; Miyazaki, S.; Yanagisawa, H.; Randomized Approximation of the Stable Marriage Problem; Proceedings of COCOON 2003, LNCS 2697: ; ,339-350. · Zbl 1276.68173
[16] Halldórsson, M.M.; Iwama, K.; Miyazaki, S.; Yanagisawa, H.; Improved approximation results for the stable marriage problem; ACM Trans. Alg.: 2007; Volume 3 . · Zbl 1192.68903
[17] Iwama, K.; Miyazaki, S.; Okamoto, K.; A (2-c(log N/N))-Approximation Algorithm for the Stable Marriage Problem; Proceedings of Algorithm Theory—SWAT 2004, LNCS 3111: ; ,349-361. · Zbl 1095.68749
[18] Iwama, K.; Miyazaki, S.; Yanagisawa, H.; A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties; Algorithmica: 2012; . · Zbl 1287.68181
[19] Manlove, D.; Irving, R.W.; Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems; J. Comb. Optim: 2008; Volume 16 ,279-292. · Zbl 1165.91442
[20] Iwama, K.; Miyazaki, S.; Yamauchi, N.; A 1.875: approximation algorithm for the stable marriage problem; Proceedings of SODA 2007: ; ,288-297. · Zbl 1302.68319
[21] Király, Z.; Better and Simpler Approximation Algorithms for the Stable Marriage Problem; Algorithmica: 2011; Volume 60 ,3-20. · Zbl 1216.68341
[22] McDermid, E.; A 3/2-approximation algorithm for general stable marriage; Proceedings of ICALP 2009, LNCS 5555: ; Volume Volume 1 ,689-700. · Zbl 1248.68564
[23] Manlove, D.F.; ; Algorithmics of Matching Under Preferences: Singapore 2013; . · Zbl 1283.68018
[24] Downey, R.G.; Fellows, M.R.; ; Parametrized Complexity: New York, NY, USA 1999; .
[25] Marx, D.; Schlotter, I.; Parameterized complexity and local search approaches for the stable marriage problem with ties; Algorithmica: 2010; Volume 58 ,170-187. · Zbl 1204.68148
[26] Marx, D.; Local search; Parameterized Complexity News: 2008; Volume 3 ,7-8.
[27] Marx, D.; Schlotter, I.; Stable assignment with couples: Parameterized complexity and local search; Discrete Optimization: 2011; Volume 8 ,25-40. · Zbl 1248.90058
[28] Laburthe, F.; Choco, a constraint programming kernel for solving combinatorial optimization problems; ; .
[29] Gent, I.P.; Prosser, P.; Smith, B.M.; Walsh, T.; Sat encodings of the stable marriage problem with ties and incomplete lists; Proceedings of SAT 2002: ; ,133-140.
[30] Brito, I.; Meseguer, P.; Distributed stable matching problems with ties and incomplete lists; Proceedings of CP 2006, LNCS 4204: ; ,675-679.
[31] Irving, R.W.; Manlove, D.F.; Finding large stable matchings; J. Exp. Algorithmics: 2009; Volume 14 ,1.2:1-1.2:30. · Zbl 1284.68670
[32] Biró, P.; Manlove, D.F.; Mittal, S.; Size versus stability in the marriage problem; Theo. Com. Sci.: 2010; Volume 411 ,1828-1841. · Zbl 1190.90155
[33] Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Manipulation and gender neutrality in stable marriage procedures; Proceedings of AAMAS 2009: ; Volume Volume 1 ,665-672.
[34] Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Manipulation complexity and gender neutrality in stable marriage procedures; J. Aut. Agents Multi-Agent Sys.: 2011; Volume 22 ,183-199.
[35] Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Stability in Matching Problems with Weighted Preferences; Proceedings of ICAART 2011: ; ,45-53. · Zbl 1461.05170
[36] Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Weights in stable marriage problems increase manipulation opportunities; Proceedings of TARK 2011: ; ,200-204.
[37] Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Stability and Optimality in Matching Problems with Weighted Preferences; Agents and Artificial Intelligence 2011 - ICAART 2011 - Revised Selected Papers, CCIS 271: Roma, Italy 2012; ,319-333.
[38] Gelain, M.; Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Male optimal and unique stable marriages with partially ordered preferences; Proceedings of CARE 2009/2010, LNAI 6066: 2010; ,44-55.
[39] Gelain, M.; Pini, M.S.; Rossi, F.; Venable, K.B.; Walsh, T.; Male optimality and uniqueness in stable marriage problems with partial orders - Extended abstract; Proceedings of AAMAS 2010: ; ,1387-1388.
[40] Bhatnagar, N.; Greenberg, S.; Randall, D.; Sampling stable marriages: why spouse-swapping won’t work; Proceedings of SODA 2008: ; ,1223-1232. · Zbl 1192.91157
[41] Iwama, K.; Manlove, D.F.; Miyazaki, S.; Morita, Y.; Stable marriage with incomplete lists and ties; Proceedings of ICALP 1999, LNCS 1644: ; ,443-452. · Zbl 0948.90155
[42] Hoos, H.H.; Tsang, E.; Local search methods; Handbook of Constraint Programming: New York, NY, USA 2006; .
[43] Guilbauld, G.T.; Les théories de l’intérêt général et le problème logique de l’agrégation; Économie Appliquée: 1952; Volume 5 ,501-584.
[44] Cheng, C.T.; Understanding the generalized median stable matching; Algorithmica: 2010; Volume 58 ,34-51. · Zbl 1204.68142
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.