11
$\begingroup$

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 ?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Sounds like a fun question, especially if you live in Utah! $\endgroup$ – Dave Clarke Sep 30 '10 at 8:10
  • 1
    $\begingroup$ The question is a bit open-ended. Naturally you can guarantee that a solution to the stable roommates problem exists if you change the definition of a blocking pair and/or restrict the structure of matching preferences. As a trivial example, you can come up with a problem formulation in which any maximal matching is "stable", and then there is a simple greedy algorithm for finding such a matching. But I don't think this is what you'd like to hear; could you elaborate a bit more? $\endgroup$ – Jukka Suomela Sep 30 '10 at 8:37
  • 1
    $\begingroup$ Two excellent books on the Stable Marriage Problem and its relatives are: Two Sided Matching by Alvin Roth and Marilda Sotomayor and The Stable Marriage Problem by Dan Gusfield and Robert W. Irving. $\endgroup$ – Joseph Malkevitch Sep 30 '10 at 13:14
  • 1
    $\begingroup$ "Stable marriage and its relation to other combinatorial problems" by Knuth is also recommended. You can find the scanned version of the French edition on the website: www-cs-faculty.stanford.edu/~uno/ms.html $\endgroup$ – Dai Le Sep 30 '10 at 15:08
11
$\begingroup$

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).
|cite|improve this answer
$\endgroup$
  • $\begingroup$ @Prof. Kalai: Would you please point me to a good reference on Scarf's non empty core condition for the case of stable marriage? $\endgroup$ – Dai Le Oct 3 '10 at 5:17
  • $\begingroup$ Try Scarf's original paper that I added to the answer. $\endgroup$ – Gil Kalai Oct 4 '10 at 1:23
10
$\begingroup$

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.)
|cite|improve this answer
$\endgroup$
  • $\begingroup$ I guess OP already knows all this, and the question was how to change the rules of the game so that a stable matching is guaranteed to exist. $\endgroup$ – Jukka Suomela Sep 30 '10 at 8:44
  • $\begingroup$ Also, the simplest counterexample involves 4 vertices where the first and second preferences of 3 of them defines a 3-cycle. $\endgroup$ – Per Vognsen Sep 30 '10 at 8:46
  • 2
    $\begingroup$ I guess people usually use the term "stable matching" to refer to any variant of the problem, and "stable marriage" vs. "stable roommates" if they want to emphasise that they study the bipartite vs. non-bipartite version of the problem. But as usual, it's best to define your terms and not assume that these are standardised... $\endgroup$ – Jukka Suomela Sep 30 '10 at 8:54
  • $\begingroup$ I hesitate to upvote this answer because of the first paragraph, which seemingly just offends some people. $\endgroup$ – Tsuyoshi Ito Sep 30 '10 at 10:30
  • $\begingroup$ @Tsuyoshi Ito: I didn't mean to offend anyone. On a second thought, I removed the 1st paragraph altogether. $\endgroup$ – M.S. Dousti Sep 30 '10 at 10:40
7
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ But this is again bipartite matching: you have two different types of entities, "people" vs. "houses" (just like you have "men" vs. "women" in the traditional stable marriage problem). The question seemed to be specifically about non-bipartite matching. $\endgroup$ – Jukka Suomela Sep 30 '10 at 8:56
  • $\begingroup$ You may have a point. I was thinking this problem could address "a society in which a certain subset of the population follow a different set of rules than the larger set". $\endgroup$ – mhum Sep 30 '10 at 9:00
  • $\begingroup$ I see, I thought it referred to a society in which we have a homosexual sub-population. Let's see if we get clarifications to the question. $\endgroup$ – Jukka Suomela Sep 30 '10 at 9:11
  • $\begingroup$ Yes I meant a society in which we have a subset of that population that behaves with a different sets of rules. $\endgroup$ – IgorCarron Oct 1 '10 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.