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