|
Published in:
The stable marriage theorem of Gale and Shapley states that for n men and
n women there always exists a stable marriage scheme, that is, a set of
marriages such that no man and woman exists that mutually prefer one
another to their partners. The stable marriage theorem was generalized in
two directions: the stable roommates problem is the "one-sided" version,
where any two agents on the market can form a partnership. The
generalization by Kelso and Crawford is in the "two-sided" model, but on
one side of the market agents have a so-called substitutable choice
function, and stability is interpreted in a natural way. It turned out that
even if both sides of the market have these substitutable choice functions,
there still exists a stable assignment. This latter version contains the
"many-to-many" model where up to a personal quota, polygamy is allowed
for both men and women in the two-sided market.
The goal of this work is to solve the stable partnership problem, a
generalization of the one-sided model with substitutable choice functions.
We do not quite reach that: besides substitutability, we also need the
increasing property for the result. Luckily, choice functions in well-known
stable matching theorems comply with this property. The main result is a
generalization of Irving's algorithm, that is the first efficient method to
solve the stable roommates problem. This general algorithm allows us to
deduce a generalization of Tan's result on characterizing the existence of
a stable matching and to prove a generalization of the so-called splitting
property of many-to-many stable matchings. We show that our algorithm is
linear-time in some sense and indicate that for general (i.e.\ not
necessary increasing) substitutable choice functions the stable partnership
problem is NP-complete.
Bibtex entry:
| AUTHOR | = | {Fleiner, Tam{\'a}s}, |
| TITLE | = | {The stable roommates problem with choice functions}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2007}, |
| NUMBER | = | {TR-2007-11} |