Stable matchings in three-sided systems with cyclic preferences
作者： Endre Boros , Vladimir Gurvich , Steven Jaslar , Daniel Krasner
DOI: 10.1016/J.DISC.2004.08.012
关键词:
摘要: We consider generalizations of the Gale-Shapley (Amer. Math. Monthly 69 (1962) 9) Stable Marriage Problem to three-sided families. Alkan (Math. Social Sci. 16 (1988) 207) gave an example which shows that in this case stable matchings do not always exist. Here we provide a simpler demonstrating fact. Danilov (NATO Advanced Research Workshop on Mathematical Theory Allocation Discrete Resources: Equilibria, Matching, Mechanisms, Sabanci University, Istanbul, Turkey, 16-19 December 2001; 46(2) (2003) 145) proved exist for special certain acyclic preferences and he raised problem another involving cyclic preferences. show answer is still negative by constructing system with lexicographically no matching exists. Finally, also possible s-sided families, s>3.
core.ac.uk
elsevier.com
sci-hub.se 参考文章(10)
V.I Danilov, Existence of stable matchings in some three-sided systems Mathematical Social Sciences. ,vol. 46, pp. 145- 148 ,(2003) , 10.1016/S0165-4896(03)00073-8
D. G. McVitie, L. B. Wilson, The stable marriage problem Communications of the ACM. ,vol. 14, pp. 486- 490 ,(1971) , 10.1145/362619.362631
F. Galvin, The list chromatic index of a bipartite multigraph Journal of Combinatorial Theory, Series B. ,vol. 63, pp. 153- 158 ,(1995) , 10.1006/JCTB.1995.1011
Ahmet Alkan, NONEXISTENCE OF STABLE THREESOME MATCHINGS Mathematical Social Sciences. ,vol. 16, pp. 207- 209 ,(1988) , 10.1016/0165-4896(88)90053-4
L. E. Dubins, D. A. Freedman, Machiavelli and the Gale-Shapley Algorithm American Mathematical Monthly. ,vol. 88, pp. 485- 494 ,(1981) , 10.1080/00029890.1981.11995301
D. Gale, L. S. Shapley, College Admissions and the Stability of Marriage American Mathematical Monthly. ,vol. 69, pp. 9- 15 ,(1962) , 10.1080/00029890.1962.11989827
Dan Gusfield, Robert W. Irving, The Stable Marriage Problem: Structure and Algorithms ,(1989)
Endre Boros, Vladimir Gurvich, Perfect graphs are kernel solvable Discrete Mathematics. ,vol. 159, pp. 35- 55 ,(1996) , 10.1016/0012-365X(95)00096-F
Alvin E. Roth, The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory Journal of Political Economy. ,vol. 92, pp. 991- 1016 ,(1984) , 10.1086/261272
College Admissions and the Stability of Marriage The American Mathematical Monthly. ,vol. 69, pp. 9- None ,(1962) , 10.2307/2312726