TR-2007-11

The stable roommates problem with choice functions

Tamás Fleiner

Published in:
Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science Volume 5035, 2008, pp 385-400



Abstract

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:

@techreport{egres-07-11,
AUTHOR = {Fleiner, Tam{\'a}s},
TITLE = {The stable roommates problem with choice functions},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2007},
NUMBER = {TR-2007-11}
}


Last modification: 21.9.2017. Please email your comments to Tamás Király!