Extension to the Stable Marriage Problem ?

Question

This may sound more like a social sciences question more than a TCS one, but it is not. When reading "Randomized Algorithms" which describes the Stable Marriage Problem, one can read the following (p54)

" It can be shown that for every choice of preference lists there exist at least one stable marriage. (Curiously enough, this is not the case in a homosexual monogamous society with even number of inhabitants)...."

Are there any very simple extensions of the Stable Marriage Problem that allows some type of steady state that includes a homosexual monogamous society, or a society in which a certain subset of the population follow a different set of rules than the larger set ?

In the affirmative, are there algorithms that perform such a matching ?

Answer 1

There is an open conjecture regarding 3 types of people. Suppose you have men women and dogs so that men have preference lists on women, women have preference lists on dogs, and dogs have preference lists on man. Is there always a stable marriage?

(For other preference structures on 3-types society the answers are known to be negative).

Another comment is that stable marriage represent a non empty core and there is a well known condition by Scarf that implies the existence of nonempty core. It is known that Scarf conditions are satisfied for the original stable marriage problemand for the house allocation problem. (But failed for the men/women/dogs problem).

Some references:

• A reference to Scarf's paper: H.E. Scarf, The core of an $N$ person game, Econometrica 35 (1967) 50--69.
• A paper showing various applications for Scarf's crucial lemma and quote quite a few others: (In particular, a fractional version of Gale-Shapley theorem for hypergraphs by Aharoni and Holzman is described): R. Aharoni, and T. Fleiner, On a lemma of Scarf, J. Combin. Theory Ser. B 87 (2003), 72--80.
• A solution of the men-women-dogs problem when there are at most 4 of each gender appears in a paper by Eriksson et al (Math Soc Sci 2006).

Answer 2

What you are asking is no longer called "Stable Marriage Problem." In contrast, it's called "Stable Roommates Problem." According to Wikipedia:

In mathematics, especially in the fields of game theory and combinatorics, the stable roommate problem (SRP) is the problem of finding a stable matching — a matching in which there is no pair of elements, each from a different matched set, where each member of the pair prefers the other to their match. This is different from the stable marriage problem in that the stable roommates problem does not require that a set is broken up into male and female subsets. Any person can prefer anyone in the same set.

It is commonly stated as:

In a given instance of the Stable Roommates problem (SRP), each of 2n participants ranks the others in strict order of preference. A matching is a set of n disjoint (unordered) pairs of participants. A matching M in an instance of SRP is stable if there are no two participants x and y, each of whom prefers the other to his partner in M. Such a pair is said to block M, or to be a blocking pair with respect to M.

Wikipedia discusses the answer to your question. It says the stable case cannot be always found, yet, there exists an efficient algorithm, due Irving (1985), which will find such matching if there's one.

---

Edit:

Several natural relaxations are conceivable to the SRP: Instead of requiring that "there are no two participants x and y, each of whom prefers the other to his partner in M," one can require that:

1. At least some certain fraction of people be satisfied with their roommates. Here, satisfiability can be interpreted differently. For instance:
   • A pair (x,y) is said to be satisfied if y is x's first choice, and vice versa.
   • A pair (x,y) is said to be satisfied if one of x or y is another's first choice.
   • A pair (x,y) is said to be unsatisfied if there exists a pair (z,w) such that x likes z more than y, and z likes x more than w.
   • ...
2. At most some certain fraction of people be unsatisfied with their roommates. (This requirement might be different that the above depending on the interpretation of satisfiability.)

Answer 3

In addition to the well-known Stable Roommates variant of the Stable Marriage Problem, there is the House Allocation Problem. In this version, you have $n$ people and $m$ houses. The people rank the houses according to their preference, but the houses do not express any preferences over the people. This paper by Abraham, et al discusses an algorithm to find a maximum cardinality, Pareto-optimal matching.