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: 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. Moreover, for the classic setting with rooms of size two, we present a linear-time algorithm that computes an outcome that is core and exchange stable as well as Pareto optimal. Many of our results for the stable roommate problem extend to the stable marriage problem.
Introduction
The classic Stable Roommate Problem (SRP) involves partitioning a set of agents into pairs such that no two agents prefer each other over their assigned partners. While well-studied for pairs, the problem becomes significantly more complex when generalized to larger group sizes ($s > 2$). In such multidimensional settings, finding stable outcomes is typically NP-hard.
Boehmer and Elkind (2019) introduce a specific variant: the roommate diversity problem. In this model, agents' preferences are not based on the specific identities of their roommates, but rather on the group's composition. For instance, in a population divided into two types (e.g., "Type A" and "Type B"), an agent's utility depends solely on the ratio of their own type within their assigned room. This reflects real-world scenarios like seating arrangements or project team formations where diversity or similarity is a primary concern.
Methodology
The research employs a combination of algorithmic design and complexity analysis to map the landscape of this problem:
- Algorithmic Design for Pairs ($s=2$): The authors develop a constructive, linear-time algorithm for the case where rooms are limited to two people. The algorithm prioritizes "happy mixed pairs" (where both types are satisfied with a 50/50 split) before addressing "pure" pairs.
- Complexity Reductions for Larger Groups ($s > 2$): To establish hardness for $s \ge 3$, the authors reduce known hard problems, such as Exact Cover by 3-Sets and Anonymous Hedonic Games, to the roommate diversity problem.
- Fixed-Parameter Tractability (FPT): By utilizing Integer Linear Programming (ILP) and grouping agents with identical preferences, the authors demonstrate that the problem is FPT with respect to the room size $s$. This means that while the problem is hard in general, it remains computationally manageable for small, fixed room sizes regardless of the total population size.
Key Insights and Results
The study reveals a sharp "phase transition" in complexity. While the $s=2$ case is efficiently solvable even with preference ties—a departure from the general SRP—the problem becomes NP-complete as soon as room sizes reach $s=3$.
The authors provide a comprehensive complexity map for various solution concepts, including core stability, exchange stability, Pareto optimality, and envy-freeness.
Key findings from this analysis include:
- Core and Exchange Stability: Outcomes satisfying these criteria are not guaranteed to exist for $s \ge 3$, and deciding their existence is NP-complete.
- Pareto Optimality: While Pareto-optimal outcomes are guaranteed to exist, verifying whether a given outcome is Pareto optimal is coNP-complete.
- Envy-Freeness: Similar to core stability, envy-free outcomes may not exist, and the existence problem is NP-complete.
- Marriage vs. Roommates: The "Marriage" variant (requiring groups to contain representatives from distinct categories) is found to be even less stable, potentially failing to have a solution even for $s=2$.
Conclusion and Future Work
The research establishes that diversity preferences can simplify the stable roommate problem in specific cases (like $s=2$) and provide a path toward tractability through FPT results for small room sizes. However, the general problem for larger groups remains challenging.
Future research directions include:
- Practical Algorithms: Developing direct combinatorial algorithms for $s > 2$ to replace the current ILP-based FPT proofs, which may be slow in practice.
- Exchange Stability: Resolving the exact complexity of deciding the existence of exchange-stable outcomes, which remains a conjectured NP-complete problem.
- Multi-type Extensions: Extending the model from two types to $k$ types to better reflect more complex real-world diversity requirements.
Summary updated