DIMACS TR: 2002-34

Stable Matchings in Three-Sided Systems with Cyclic Preferences



Authors: Endre Boros, Vladimir Gurvich, Steven Jaslar and Daniel Krasner

ABSTRACT

We consider generalizations of the Gale-Shapley (1962) Stable Marriage Problem to three-sided families. Alkan (1988) gave an example which shows that in this case stable matchings do not always exist. Here we provide a simpler example demonstrating this fact. Danilov (2001) proved that stable matchings always exist for the special case of certain acyclic preferences and he raised the problem for another special case involving cyclic preferences. Here we show that the answer is still negative by constructing a three-sided system with lexicographically cyclic preferences for which no stable matching exists. Finally, we also consider possible generalizations to $m$-sided families, for $m>3$.

Keywords: Gale-Shapley Theorem, stable matching, stable marriage, cyclic preferences.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-34.ps.gz


DIMACS Home Page