<p>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? </p>

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

<p>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).</p>

<p>Some references: </p>

<ul>
<li>A reference to Scarf's paper: H.E. Scarf, The core of an $N$ person game, Econometrica 35 (1967) 50--69.</li>
<li>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. </li>
<li>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).</li>
</ul>

CC BY-SA 2.5
2010-10-03T05:17:15.103Z
@Prof. Kalai: Would you please point me to a good reference on Scarf's non empty core condition for the case of stable marriage?
Dai Le
CC BY-SA 2.5
2010-10-04T01:23:06.337Z
Try Scarf's original paper that I added to the answer.
Gil Kalai
CC BY-SA 2.5
2010-09-30T13:53:03.553Z
2010-10-04T02:00:22.500Z
2010-10-04T02:00:22.500Z
Gil Kalai
<p>What you are asking is no longer called &quot;Stable Marriage Problem.&quot; In contrast, it's called &quot;Stable Roommates Problem.&quot; According to <a href="http://en.wikipedia.org/wiki/Stable_roommates_problem" rel="noreferrer">Wikipedia</a>:</p>
<blockquote>
<p>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.</p>
<p>It is commonly stated as:</p>
<p>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.</p>
</blockquote>
<p>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.</p>
<hr />
<h3>Edit:</h3>
<p>Several natural relaxations are conceivable to the SRP: Instead of requiring that &quot;there are no two participants x and y, each of whom prefers the other to his partner in M,&quot; one can require that:</p>
<ol>
<li>At least some certain fraction of people be satisfied with their roommates. Here, <b>satisfiability</b> can be interpreted differently. For instance:
<ul>
<li>A pair (x,y) is said to be satisfied if y is x's first choice, and vice versa.
<li>A pair (x,y) is said to be satisfied if one of x or y is another's first choice.
<li>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.
<li> ...
</ul>
<li>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 <b>satisfiability</b>.)
</ol>

CC BY-SA 2.5
2010-09-30T08:44:54.267Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-09-30T08:46:00.447Z
Also, the simplest counterexample involves 4 vertices where the first and second preferences of 3 of them defines a 3-cycle.
Per Vognsen
CC BY-SA 2.5
2010-09-30T08:54:14.930Z
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...
Jukka Suomela
CC BY-SA 2.5
2010-09-30T10:30:35.853Z
I hesitate to upvote this answer because of the first paragraph, which seemingly just offends some people.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-30T10:40:23.647Z
@Tsuyoshi Ito: I didn't mean to offend anyone. On a second thought, I removed the 1st paragraph altogether.
Sadeq Dousti
CC BY-SA 2.5
2010-09-30T08:40:14.527Z
2010-09-30T11:00:04.860Z
2020-06-17T09:38:08.363Z
Sadeq Dousti
<p>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. <a href="http://eprints.gla.ac.uk/1062/1/ISAAC04.pdf">This paper</a> by Abraham, et al discusses an algorithm to find a maximum cardinality, Pareto-optimal matching.</p>

CC BY-SA 2.5
2010-09-30T08:56:20.527Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-09-30T09:00:58.213Z
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".
mhum
CC BY-SA 2.5
2010-09-30T09:11:45.173Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-10-01T11:58:53.930Z
Yes I meant a society in which we have a subset of that population that behaves with a different sets of rules.
IgorCarron
CC BY-SA 2.5
2010-09-30T08:52:16.800Z
2010-09-30T08:52:16.800Z
mhum
<p>This may sound more like a social sciences question more than a TCS one, but it is not. When reading "<a href="http://rads.stackoverflow.com/amzn/click/0521474655">Randomized Algorithms</a>" which describes the Stable Marriage Problem, one can read the following (p54)  </p>

<p>" 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)...."</p>

<p>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 ?</p>

<p>In the affirmative, are there algorithms that perform such a matching ?</p>

CC BY-SA 2.5
2010-09-30T08:10:35.067Z
Sounds like a fun question, especially if you live in Utah!
Dave Clarke
CC BY-SA 2.5
2010-09-30T08:37:26.513Z
The question is a bit open-ended. Naturally you can guarantee that a solution to the [stable roommates problem](http://en.wikipedia.org/wiki/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?
Jukka Suomela
CC BY-SA 2.5
2010-09-30T13:14:39.067Z
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.
Joseph Malkevitch
CC BY-SA 2.5
2010-09-30T15:08:00.003Z
"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: http://www-cs-faculty.stanford.edu/~uno/ms.html
Dai Le
<ds.algorithms><graph-theory><matching>
Extension to the Stable Marriage Problem ?
IgorCarron
# Extension to the Stable Marriage Problem ?

(Asked by: username_0 on 2010-09-30)

This may sound more like a social sciences question more than a TCS one, but it is not. When reading "[Randomized Algorithms](http://rads.stackoverflow.com/amzn/click/0521474655)" 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 ?

**Tags:** ds.algorithms, graph-theory, matching

> **Comments:**
> **username_1**: Sounds like a fun question, especially if you live in Utah!  
> **username_2**: The question is a bit open-ended. Naturally you can guarantee that a solution to the [stable roommates problem](http://en.wikipedia.org/wiki/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?  
> **username_3**: 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.  
> **username_4**: "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: http://www-cs-faculty.stanford.edu/~uno/ms.html  

---

## 3 answers

### Answer by username_5 on 2010-09-30. Score: 11

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).

> **Comments:**
> **username_4**: @Prof. Kalai: Would you please point me to a good reference on Scarf's non empty core condition for the case of stable marriage?  
> **username_5**: Try Scarf's original paper that I added to the answer.  

---

### Answer by username_6 on 2010-09-30. Score: 10

What you are asking is no longer called "Stable Marriage Problem." In contrast, it's called "Stable Roommates Problem." According to [Wikipedia](http://en.wikipedia.org/wiki/Stable_roommates_problem):

> 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.* ...- 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**.)

> **Comments:**
> **username_2**: 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.  
> **username_7**: Also, the simplest counterexample involves 4 vertices where the first and second preferences of 3 of them defines a 3-cycle.  
> **username_2**: 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...  
> **username_8**: I hesitate to upvote this answer because of the first paragraph, which seemingly just offends some people.  
> **username_6**: @username_8: I didn't mean to offend anyone. On a second thought, I removed the 1st paragraph altogether.  

---

### Answer by username_9 on 2010-09-30. Score: 7

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](http://eprints.gla.ac.uk/1062/1/ISAAC04.pdf) by Abraham, et al discusses an algorithm to find a maximum cardinality, Pareto-optimal matching.

> **Comments:**
> **username_2**: 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.  
> **username_9**: 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".  
> **username_2**: 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.  
> **username_0**: Yes I meant a society in which we have a subset of that population that behaves with a different sets of rules.  

---

