5
$\begingroup$

The 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!

$\endgroup$
6
$\begingroup$

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

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

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Dang. This is going to make my lunch plans much more complicated. $\endgroup$ – Tom Anderson Oct 3 '14 at 19:39

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.