Date/Time
Date(s) - 25/01/2022
1:00 pm - 2:00 pm
Abstract: 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 these 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 (but deterministic) algorithm in polynomial time. These results help us explore the boundary between NP-hardness and polynomial-time solvability in problems of coalition formation.
This talk is based on a talk presented at The 14th International Symposium on Algorithmic Game Theory, Aarhus, Denmark (SAGT 2021).
