×

A new solution concept for the roommate problem: \(\mathcal{Q}\)-stable matchings. (English) Zbl 1347.91200

Summary: The aim of this paper is to propose a new solution concept for the roommate problem with strict preferences. We introduce maximum irreversible matchings and consider almost stable matchings [D. J. Abraham et al., Lect. Notes Comput. Sci. 3879, 1–14 (2006; Zbl 1125.68425)] and maximum stable matchings [J. J. M. Tan, BIT 30, No. 4, 631–640 (1990; Zbl 0711.68051); Int. J. Comput. Math. 39, No. 1–2, 11–20 (1991; Zbl 0742.68047)]. These solution concepts are all core consistent. We find that almost stable matchings are incompatible with the other two concepts. Hence, to solve the roommate problem we propose matchings that lie at the intersection of the maximum irreversible matchings and maximum stable matchings, which we call \(\mathcal{Q}\)-stable matchings. We construct an efficient algorithm for computing one element of this set for any roommate problem. We also show that the outcome of our algorithm always belongs to an absorbing set [the second author et al., Games Econ. Behav. 81, 165–178 (2013; Zbl 1282.91231)].

MSC:

91B68 Matching models
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abraham, D. J.; Biró, P.; Manlove, D. F., “Almost stable” matchings in the roommates problem, (Approximation and Online Algorithms, vol. 3879 (2006)), 1-14 · Zbl 1125.68425
[2] Abraham, D. J.; Manlove, D. F., Pareto optimality in the roommates problem, (Technical Report No. TR-2004-182 (2004), The Computing Science Department of Glasgow University)
[4] Biró, P.; Cechlárová, K.; Fleiner, T., The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems, Internat. J. Game Theory, 36, 333-352 (2008) · Zbl 1145.91041
[6] Bogomolnaia, A.; Jackson, M. O., The stability of hedonic coalition structures, Games Econom. Behav., 38, 201-230 (2002) · Zbl 1013.91011
[7] Can, B.; Klaus, B., Consistency and population sensitivity properties in marriage and roommate markets, Soc. Choice Welf., 41, 835-862 (2013) · Zbl 1288.91151
[8] Cechlárová, K.; Ferková, S., The stable crews problem, Discrete Appl. Math., 140, 1-17 (2004) · Zbl 1069.90086
[9] Chung, K. S., On the existence of stable roommate matchings, Games Econom. Behav., 33, 206-230 (2000) · Zbl 1047.91012
[10] Diamantoudi, E.; Miyagawa, E.; Xue, L., Random paths to stability in the roommate problem, Games Econom. Behav., 48, 18-28 (2004) · Zbl 1093.91046
[12] Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Amer. Math. Monthly, 69, 9-15 (1962) · Zbl 0109.24403
[13] Gudmundsson, J., When do stable roommate matchings exist? A review, Rev. Econ. Des., 18, 151-161 (2014) · Zbl 1302.91155
[14] Gusfield, D.; Irving, R. W., The Stable Marriage Problem: Structure and Algorithms, Vol. 54 (1989), MIT press: MIT press Cambridge · Zbl 0703.68046
[15] Inarra, E.; Larrea, C.; Molis, E., Random paths to P-stability in the roommate problem, Internat. J. Game Theory, 36, 461-471 (2008) · Zbl 1149.91047
[16] Inarra, E.; Larrea, C.; Molis, E., Absorbing sets in roommate problems, Games Econom. Behav., 81, 165-178 (2013) · Zbl 1282.91231
[17] Jackson, M. O.; Watts, A., On the formation of interaction networks in social coordination games, Games Econom. Behav., 41, 265-291 (2002) · Zbl 1037.91017
[18] Kalai, E.; Pazner, E. A.; Schmeidler, D., Admissible outcomes of social bargaining processes as collective choice correspondence, Econometrica, 63, 299-325 (1976) · Zbl 0342.90001
[19] Klaus, B.; Klijn, F., Smith and Rawls share a room: stability and medians, Soc. Choice Welf., 35, 647-667 (2010) · Zbl 1232.91530
[20] Klaus, B.; Klijn, F.; Walzl, M., Stochastic stability for roommate markets, J. Econom. Theory, 145, 2218-2240 (2010) · Zbl 1203.91202
[21] Kujansuu, E.; Lindberg, T.; Makinen, E., The stable roommates problem and chess tournament pairings, Divulg. Mat., 7, 19-28 (1999) · Zbl 0940.05065
[22] Manlove, D. F., Algorithms of Matching Under Preferences (2013), World Scientific Publishing
[23] Morrill, T., The roommates problem revisited, J. Econom. Theory, 145, 1739-1756 (2010) · Zbl 1245.91071
[24] Özkal-Sanver, İ., Impossibilities for roommate problems, Math. Social Sci., 59, 360-363 (2010) · Zbl 1230.91147
[25] Pittel, B. G.; Irving, R. W., An upper bound for the solvability probability of a random stable roommates instance, Random Struct. Algorithms, 5, 465-486 (1994) · Zbl 0805.60010
[26] Roth, A. E.; Sönmez, T.; Ünver, M. U., Pairwise kidney exchange, J. Econom. Theory, 125, 151-188 (2005) · Zbl 1081.92023
[27] Roth, A. E.; Vande Vate, J. H.V., Random paths to stability in two-sided matching, Econometrica, 58, 1475-1480 (1990) · Zbl 0731.90007
[28] Sönmez, T.; Ünver, M. U., Market design for kidney exchange, (Oxford Handbook of Market Design (2010), Oxford University Press)
[29] Sotomayor, M., The pareto-stability concept is a natural solution concept for discrete matching markets with indifferences, Internat. J. Game Theory, 40, 631-644 (2011) · Zbl 1220.91025
[30] Tan, J. J., A maximum stable matching for the roommates problem, BIT, 30, 631-640 (1990) · Zbl 0711.68051
[31] Tan, J. J., A necessary and sufficient condition for the existence of a complete stable matching, J. Algorithms, 12, 154-178 (1991) · Zbl 0715.68069
[32] Tan, J. J., Stable matchings and stable partitions, Int. J. Comput. Math., 39, 11-20 (1991) · Zbl 0742.68047
[33] Tan, J. J.; Hsueh, H.-C., A generalization of the stable matching problem, Discrete Appl. Math., 59, 87-102 (1995) · Zbl 0827.90120
[34] Toda, M., Monotonicity and consistency in matching markets, Internat. J. Game Theory, 34, 13-31 (2006) · Zbl 1151.91664
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.