Name
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 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 substitutable choice functions, there still exists a stable assignment. The 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 for the result the so called increasing property (or, in other terminology, the law of aggregate demand). Luckily, choice functions in well-known stable matching theorems comply with this property. The main result is a generalization of Irving’s algorithm, the first efficient method to solve the stable roommates problem. We deduce from the algorithm a generalization of Tan’s result on characterizing the existence of a stable matching and prove a generalization of the rural hospital theorem and 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 necessarily increasing) substitutable choice functions the stable partnership problem is NP-complete. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/978-3-540-68891-4_27 | Algorithmica |
Keywords | DocType | Volume |
Stable matching,Stable roommates problem,Choice function,Irving’s algorithm | Journal | 58 |
Issue | ISSN | ISBN |
1 | 0178-4617 | 3-540-68886-2 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tamás Fleiner | 1 | 241 | 27.45 |