<p>Switching from 2 to 3 "beds" makes the problem NP-complete :-)</p>

<p>See K. Iwama, S. Miyazaki, and K. Okamoto, "Stable roommates problem with triple rooms." Proc. 10th KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2007), pp. 105–112, 2007</p>

<p>(an electronic edition can be <a href="https://www.researchgate.net/publication/228816339_Stable_roommates_problem_with_triple_rooms">downloaded from ResearchGate</a>).</p>

<p><strong>Abstract:</strong> In the stable roommates problem, we are given 2N men and each person's preference list. We are asked to find a stable matching, namely, a set of N pairs satisfying the stability condition. This problem is known to be solved in polynomial time; more precisely, there is a polynomial-time algorithm to find a stable matching for a given instance, or to report that a given instance has no stable matching. In this paper, we extend this problem into three-dimension, i.e., a matching is defined to be a set of triples, and show that this problem is NP-complete. ...</p>

<p>See also this survey: Kazuo Iwama and Shuichi Miyazaki. 2008. <a href="http://dl.acm.org/citation.cfm?id=1345763">A Survey of the Stable Marriage Problem and Its Variants</a>. In Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008) (ICKS '08). IEEE Computer Society, Washington, DC, USA, 131-136.</p>

CC BY-SA 3.0
2014-10-03T19:39:14.853Z
Dang. This is going to make my lunch plans much more complicated.
Tom Anderson
CC BY-SA 3.0
2014-10-02T21:23:15.290Z
2014-10-02T21:29:25.320Z
2014-10-02T21:29:25.320Z
Marzio De Biasi
<p>The <a href="http://en.wikipedia.org/wiki/Stable_roommates_problem">stable roommates problem</a> presents a set of N two-person rooms and 2N would-be roommates with preferences over each other, and asks for a stable allocation of roommates to rooms (and, really, to each other). There is an efficient algorithm which finds a solution, if there is one.</p>

<p>Is there an extension of this problem to rooms which can take more than two people?</p>

<p>Such an extension does seem challenging, because so much of the definition of the problem rests on the fact that roommates are in pairs, which means that each roommate only shares with a single other. This makes comparisons between potential pairings trivial - does the roommate prefer this partner or that one? Asking whether a roommate prefers one <em>set</em> of partners or another is much harder. Still, i'm interested in any approaches which have been taken!</p>

<ds.algorithms><graph-theory><matching>
Is there an extension to the stable roommates problem with multiple roommates per room?
Tom Anderson
# Is there an extension to the stable roommates problem with multiple roommates per room?

(Asked by: username_0 on 2014-10-02)

The [stable roommates problem](http://en.wikipedia.org/wiki/Stable_roommates_problem) presents a set of N two-person rooms and 2N would-be roommates with preferences over each other, and asks for a stable allocation of roommates to rooms (and, really, to each other). There is an efficient algorithm which finds a solution, if there is one.

Is there an extension of this problem to rooms which can take more than two people?

Such an extension does seem challenging, because so much of the definition of the problem rests on the fact that roommates are in pairs, which means that each roommate only shares with a single other. This makes comparisons between potential pairings trivial - does the roommate prefer this partner or that one? Asking whether a roommate prefers one *set* of partners or another is much harder. Still, i'm interested in any approaches which have been taken!

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


---

## 1 answers

### Answer by username_1 on 2014-10-02. Score: 7 | Accepted answer

Switching from 2 to 3 "beds" makes the problem NP-complete :-)

See K. Iwama, S. Miyazaki, and K. Okamoto, "Stable roommates problem with triple rooms." Proc. 10th KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2007), pp. 105–112, 2007

(an electronic edition can be [downloaded from ResearchGate](https://www.researchgate.net/publication/228816339_Stable_roommates_problem_with_triple_rooms)).

**Abstract:** In the stable roommates problem, we are given 2N men and each person's preference list. We are asked to find a stable matching, namely, a set of N pairs satisfying the stability condition. This problem is known to be solved in polynomial time; more precisely, there is a polynomial-time algorithm to find a stable matching for a given instance, or to report that a given instance has no stable matching. In this paper, we extend this problem into three-dimension, i.e., a matching is defined to be a set of triples, and show that this problem is NP-complete. ...

See also this survey: Kazuo Iwama and Shuichi Miyazaki. 2008. [A Survey of the Stable Marriage Problem and Its Variants](http://dl.acm.org/citation.cfm?id=1345763). In Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008) (ICKS '08). IEEE Computer Society, Washington, DC, USA, 131-136.

> **Comments:**
> **username_0**: Dang. This is going to make my lunch plans much more complicated.  

---

