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