Stable Roommate Problem with Diversity Preferences

Niclas Boehmer, Edith Elkind

Abstract

The Roommate Diversity Problem (RDP) extends the classic stable roommate problem to larger groups where agents' preferences depend on the ratio of types (e.g., Red vs. Blue) within their assigned rooms. This paper investigates the computational complexity of finding stable and fair allocations in this setting. While the problem is generally NP-hard for room sizes greater than two, the authors demonstrate that diversity preferences render the problem Fixed-Parameter Tractable (FPT) with respect to room size. This finding suggests practical feasibility for real-world applications such as project team formation or event seating.

Introduction

The stable roommate problem is a foundational concept in matching theory, typically focused on pairing individuals. However, many practical scenarios require partitioning a population into larger groups, such as dorm rooms of four or project teams of six. In these multidimensional extensions, finding stable outcomes is often computationally intractable or even impossible. This research introduces the Roommate Diversity Problem (RDP), which simplifies agent preferences by categorizing individuals into two distinct types. An agent's utility is determined solely by the fraction of their own type in their assigned room, a constraint termed "diversity preferences."

Methodology

The study employs a theoretical computer science framework to analyze various solution concepts, including Core Stability, Exchange Stability, Pareto Optimality, and Envy-Freeness. The authors utilize complexity analysis to prove NP-completeness through reductions from anonymous hedonic games. Furthermore, they apply parameterized complexity techniques, specifically Integer Linear Programming (ILP) and Lenstra’s algorithm, to evaluate the problem's tractability when the room size ($s$) is small.

Key Results

The research identifies a critical threshold at room size $s=2$. For pairs, stable and Pareto optimal outcomes are guaranteed and easily computable. However, for $s > 2$, existence is no longer guaranteed, and finding solutions becomes NP-hard.

A central contribution of this work is the proof that RDP is Fixed-Parameter Tractable (FPT) with respect to room size. Despite being NP-hard in general, the limited number of "agent types" created by diversity preferences (only $s+1$ possible utility levels) allows for efficient computation when room sizes are fixed.

The complexity landscape is summarized in the following table:

Table 1: Complexity results for existence and verification of stable outcomes under different preference models.

As shown in the table, core stable outcomes are guaranteed and efficiently found under dichotomous preferences. Conversely, verifying Pareto optimality remains coNP-complete in unrestricted settings.

Discussion and Future Work

While the FPT results provide a theoretical foundation for solving RDP, the reliance on ILP solvers may pose practical performance challenges. Future research should focus on developing more efficient combinatorial algorithms. Additionally, extending the model to accommodate more than two agent types or heterogeneous room sizes would better reflect the complexity of real-world social identities. The question of whether finding a Pareto optimal outcome is FPT also remains an open challenge for the field.

Summary updated

Abstract

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.
BibTeX
@inproceedings{boehmer2020stable,
  author = {Niclas Boehmer and Edith Elkind},
  title = {{Stable Roommate Problem with Diversity Preferences}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.24963/ijcai.2020/14},
}
Figure