Stable Roommate Problem with Diversity Preferences

Stable Roommate Problem with Diversity Preferences

Niclas Boehmer, Edith Elkind

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 96-102. https://doi.org/10.24963/ijcai.2020/14

In the multidimensional stable roommate problem, agents have to be allocated to rooms and have preferences over sets of potential roommates. We study the complexity of finding good allocations of agents to rooms under the assumption that agents have diversity preferences (Bredereck, Elkind, Igarashi, AAMAS'19): each agent belongs to one of the two types (e.g., juniors and seniors, artists and engineers), and agents’ preferences over rooms depend solely on the fraction of agents of their own type among their potential roommates. We consider various solution concepts for this setting, such as core and exchange stability, Pareto optimality and envy-freeness. On the negative side, we prove that envy-free, core stable or (strongly) exchange stable outcomes may fail to exist and that the associated decision problems are NP-complete. On the positive side, we show that these problems are in FPT with respect to the room size, which is not the case for the general stable roommate problem.
Keywords:
Agent-based and Multi-agent Systems: Computational Social Choice
Agent-based and Multi-agent Systems: Cooperative Games