A non-trivial polynomial time algorithm for a 3D Stable Roommates problem
In this talk we consider possible formalisations of the three-dimensional Stable Roommates problem (3D-SR). Players specify preference lists over their peers, and the task is to partition the players into sets of size 3 based on their preferences. A number of hardness results exist under various schemes of preference representation. We consider a formalisation of 3D-SR in which agents’ preferences are additively separable and binary, named 3D-SR-AS-BIN. The decision problem then asks whether we can partition the players into sets of three, such that no three players would prefer to be in a set together than remain in their current triples. We show that 3D-SR-AS-BIN is NP-complete and consider its restriction in which preferences are symmetric, named 3D-SR-SAS-BIN. We show that every instance of 3D-SR-SAS-BIN contains a stable matching that can be found using a non-trivial algorithm in polynomial time. These results help us explore the boundary between NP-hardness and polynomial-time solvability in problems of coalition formation.