Stable Roommate Problem with Diversity Preferences

1 Introduction

Alice and Bob are planning their wedding. They have agreed on the gift registry and the music to be played, but they still need to decide on the seating plan for the wedding reception. They expect 120 guests, and the reception venue has 20 tables, with each table seating 6 guests. However, this task is far from being easy: e.g., Alice's great-aunt does not get along with Bob's family and prefers not to share the table with any of them; on the contrary, Bob's younger brother is keen to meet Alice's family and would be upset if he were stuck with his relatives. After spending an evening trying to find a seating plan that would keep everyone happy, Alice and Bob are on the brink of canceling the wedding altogether.

Bob's friend Charlie wonders if the hapless couple may benefit from consulting the literature on the stable roommate problem. In this problem, the goal is to find a stable assignment of 2n agents into n rooms of size 2, where every agent has a preference relation over her possible roommates. The most popular notion of stability in this context is core stability: no two agents should strictly prefer each other to their current roommate. Another relevant notion is exchange stability: no two agents should want to swap their places. However, for the stable roommate problem, neither core stable nor exchange stable outcomes are guaranteed to exist. Further, while Irving [1985] proved that it is possible to decide in time linear in the size of the input if an instance of the roommate problem with strict preferences admits a core stable outcome, many other algorithmic problems for core and exchange stability are computationally hard [Cechl´arov´a and Manlove, 2005; Ronn, 1990]. For the s-dimensional stable roommate problem, where each room has size s and agents have preferences over all s - 1-subsets of agents as their potential roommates, even the core non-emptiness problem for strict preferences is NP-complete for s ≥ 3 [Huang, 2007; Ng and Hirschberg, 1991].

∗An extended abstract of this paper appears in the proceedings of AAMAS'20.

†Most of this research was done when the first author was an MSc student at the University of Oxford.

However, Charlie then notes that Alice and Bob's problem has additional structure: the invitees can be classified as bride's family or groom's family, and it appears that all constraints on seating arrangements can be expressed in terms of this classification: each person only has preferences over the ratio of groom's relatives and bride's relatives at her table. Thus, the problem in question is closely related to hedonic diversity games, recently introduced by Bredereck et al. [2019]. These are coalition formation games where agents have diversity preferences, i.e., they are partitioned into two groups (say, red and blue), and every agent is indifferent among coalitions with the same ratio of red and blue agents. However, positive results for hedonic diversity games are not directly applicable to the roommate setting: in hedonic games, agents form groups of varying sizes, while the wedding guests have to be split into groups of six.

In this paper, we investigate the multidimensional stable roommate problem (for arbitrary room size s) with diversity preferences; we refer to the resulting problem as the roommate diversity problem. This model captures important aspects of several real-world group formation scenarios, such as flat-sharing, splitting students into teams for group projects and seating arrangements at important events. We consider common solution concepts from the literature on the stable roommate problem; for each solution concept, we analyze the complexity of checking if a given outcome is a valid solution, whether the set of solutions is guaranteed to be non-empty, and, if not, how hard it is to check if an instance admits a solution as well as to compute a solution if it exists.

1.1 Our Contribution

We show that for room size two, every instance admits an outcome that is core stable, exchange stable and Pareto optimal. For s > 2, we provide counterexamples showing that core stable, exchange stable or envy-free outcomes may fail to exist. We also prove that for core stability, strong exchange stability and envy-freeness the existence questions are computationally hard; for Pareto optimality, we show that it is not only hard to find a Pareto optimal outcome, but also to verify whether a given outcome is Pareto optimal. We provide an overview of our results in Table 1.

On the positive side, we show that all existence questions we consider are in FPT with respect to the room size. To the best of our knowledge, apart from some work on the multidimensional stable roommate problem with cyclic preferences [Hofbauer, 2016], this is one of the first positive results for the multidimensional stable roommate problem. Thus, the roommate diversity problem offers an attractive combination of expressive power and computational tractability.

1.2 RelatedWork

The stable roommate problem was proposed by Gale and Shapley [1962]. While Irving [1985] proved that it is possible to check in time linear in the input whether a roommate problem admits a core stable outcome if the preferences are restricted to be strict, Ronn [1990] showed that this problem becomes NP-complete if ties in the preference relations are allowed. As in practice a group deviation usually requires some regrouping, Alcalde [1994] initiated the study of local stability notions that do not require reallocating nondeviating agents, by introducing the notion of exchange stability. Subsequently, Cechl´arov´a and Manlove [2005] proved that it is NP-complete to decide whether an instance of the stable roommate problem with strict preferences admits an exchange stable outcome. Another concept that is relevant for the roommate problem is Pareto optimality [Abraham et al., 2005; Cseh et al., 2019; Sotomayor, 2011]. Morrill [2010] proved that for room size two it is possible to check if a given outcome is Pareto optimal, and to find a Pareto improvement if it exists, in time quadratic in the number of agents. This implies that a Pareto optimal outcome can be found in polynomial time. Researchers have also considered various notions of fairness in the context of the roommate problem [Abdulkadiro˘glu and S¨onmez, 2003; Aziz and Klaus, 2019]. One such notion is envy-freeness: an outcome is said to be envy-free if no agent wants to take the place of another agent.

While much of the work on the stable roommate problem focuses on the case s = 2, there are a few papers that consider the three-dimensional stable roommate problem [Huang, 2007; Ng and Hirschberg, 1991]. For different possible definitions of the agents' preferences, it is NP-complete to decide whether an instance with strict preferences admits a core stable outcome [Huang, 2007; Iwama et al., 2007; Ng and Hirschberg, 1991]. For this reason, despite its great practical relevance, the multidimensional version of the roommate problem has not attracted much attention yet.

One possibility to circumvent these negative results is to search for reasonable subclasses of the stable roommate problem, i.e., to identify realistic restrictions on the agents' preferences for which the associated computational problems become tractable. This approach has been successful in the study of the two-dimensional stable roommate problem [Abraham et al., 2007; Bartholdi III and Trick, 1986; Bredereck et al., 2017; Chung, 2000; Cseh and Juhos, 2019], as well as in the context of hedonic games [Aziz et al., 2019; Banerjee et al., 2001; Bogomolnaia and Jackson, 2002]. In particular, Bredereck et al. [2019] and Boehmer and Elkind [2020a] analyzed the complexity of finding stable outcomes in hedonic diversity games for several notions of stability, such as Nash stability, individual stability and core stability. However, these results do not directly translate to our model: first, with the exception of core stability, the solution concepts we consider are different from those considered in hedonic diversity games, and second, the hard constraint on the room sizes in the roommate problem changes both the set of feasible allocations and the set of possible deviations.

Finally, we note that Bredereck et al. [2019] and Boehmer and Elkind [2020a] related hedonic games with diversity preferences to anonymous hedonic games [Bogomolnaia and Jackson, 2002], where the agents' preferences over coalitions only depend on coalition sizes. This connection proves useful in our setting as well: e.g., in our hardness reductions we use the fact that it is NP-complete to decide whether an anonymous hedonic game admits a Nash or core stable outcome [Ballester, 2004].

Diversity-related questions have also been studied in the context of stable matching problems [Huang, 2010; Kamada and Kojima, 2015]. However, our approach is fundamentally different: in our model, types are used to define agents' preferences rather than distributional constraints on the outcome.

Full version. The full version of the paper is available on arXiv [Boehmer and Elkind, 2020b]. It contains all missing proofs and some preliminary results on extensions of our model, such as non-uniform room sizes and more than two types of agents.

2 Preliminaries

For every positive integer t, we denote the set {1, . . . , t} by [t], and we write [0, t] to denote {0} ∪ [t].

Definition 1. A roommate diversity problem with room size s is a quadruple G = (R, B, s, (≿i)i∈R∪B) with N = R∪· B and |N| = k · s for some k ∈ N. The preference relation ≿i of each agent i ∈ N is a weak order over the set D = { js : j ∈ [0, s]}.

In the following, we call all agents in R red agents and all agents in B blue agents, and write r = |R|, b = |B| and n = |R ∪· B| . We refer to size-s subsets of N as coalitions or rooms; the quantity k = |N| s is then the number of rooms. For each i ∈ N, let Ni = {S ⊆ N : |S| = s, i ∈ S} denote all size-s subsets of N containing i, i.e., all possible rooms that i can be part of.

An outcome of G is a partition of all agents into k rooms π = {C1, . . . , Ck} such that |Ci| = s for all i ∈ [k]. Let π(i) denote i's coalition in π. Given a coalition C ⊆ N, let θ(C) denote the fraction of red agents in C, i.e., θ(C) = |C∩R| |C| : we say that C is of fraction θ(C). A coalition C ⊆ N is called pure if C ⊆ R or C ⊆ B and mixed otherwise.

For each agent i ∈ N, we interpret her preference relation ≿i over D as her preferences over the fraction of red agents in her coalition; for instance, 2 5 ≿i 35 means that agent i prefers a room where two out of five agents are red to a room where three out of five agents are red. 1 Thereby, ≿i induces agent i's preferences over all possible rooms she can be part of. 2 Given two rooms S, T ∈ Ni, overloading notation, we write S ≻i T and say that i strictly prefers S to T if θ(S) ≿i θ(T) and θ(T) ̸≿i θ(S). Further, we write S ≿i T and say that i weakly prefers S to T if θ(T) = θ(S) or θ(T) ≿i θ(S). If i weakly prefers S to T and T to S, we write S ∼i T and say that i is indifferent between S and T .

The preference relation of agent i is said to be singlepeaked if there exists a peak pi ∈ D such that for all α, β ∈ D such that pi ≤ α < β or β < α ≤ pi it holds that α ≿i β. The preference relation of i is said to be dichotomous if it is possible to partition D into two sets D+ and D- so that for all d ∈ D+, d′ ∈ D- it holds that d ≻i d′ , for all d, d′ ∈ D- it holds that d ∼i d′ and for all d, d′ ∈ D+ it holds that d ∼i d′ . We say that i approves all fractions in D+ and disapproves all fractions in D-.

Generalizing the definition of Gale and Shapley [1962], we say that a coalition S ⊆ N with |S| = s blocks an outcome

1 We could equivalently define the agents' preferences over the number of red agents in each room; we chose the ratio-based definition for consistency with the hedonic diversity games literature and to emphasize the room size.

2 For succinctness and consistency with prior work, we assume that each agent has preferences over the entire set D, including 0 and 1, even though a red agent cannot be part of a room with ratio 0 and a blue agent cannot be part of a room with ratio 1. Allowing agents to have preferences over 'impossible' ratios has no impact on our results: even if, say, a blue agent ranks 1 highly, she cannot deviate to a coalition with this ratio. In all of our examples, the impossible ratios are ranked at the bottom of agent's preferences.

π if for all i ∈ S it holds that θ(S) ≻i θ(π(i)); we say that S weakly blocks an outcome π if for all i ∈ S it holds that θ(S) ≿i θ(π(i)) and there exists an i ∈ S such that θ(S) ≻i θ(π(i)). An outcome π is called (strongly) core stable if no coalition (weakly) blocks it.

In an outcome π, a pair of agents i, j ∈ N with π(i) ̸= π(j) has an exchange deviation if they would like to exchange places, i.e., θ((π(j) \ {j}) ∪ {i}) ≻i θ(π(i)) and θ((π(i) \ {i}) ∪ {j}) ≻j θ(π(j)). Further, a pair of agents i, j ∈ N with π(i) ̸= π(j) has a weak exchange deviation if θ((π(j) \ {j})∪{i}) ≻i θ(π(i)) and θ((π(i)\{i})∪{j}) ≿j θ(π(j)). An outcome is called (strongly) exchange stable if no pair of agents has a (weak) exchange deviation [Alcalde, 1994].

An outcome π is called Pareto optimal if there is no other outcome that makes all agents weakly better off and some agents strictly better off, i.e., there is no outcome π′ such that θ(π′ (i)) ≿i θ(π(i)) for all i ∈ N and θ(π′ (i)) ≻i θ(π(i)) for some i ∈ N.

An outcome π is called envy-free if there does not exist a pair of agents i, j ∈ N with π(i) ̸= π(j) such that i envies j's place, i.e., θ((π(j) \ {j}) ∪ {i}) ≻i θ(π(i)).

Due to space constraints, we defer several proofs to the full version of the paper.

3 Roommate Diversity ProblemWith Room Size Two

For s = 2, the roommate diversity problem becomes a special case of the classical stable roommate problem. Our first observation is that diversity preferences make the classical problem significantly easier: we can efficiently find an outcome that is Pareto optimal, core stable and exchange stable. This result motivates us to focus on the case s > 2 in the remainder of the paper.

Theorem 1. Every instance of the roommate diversity problem with room size two admits an outcome that is Pareto optimal, core stable and exchange stable, even if we allow for indifferences in the preferences.

Proof sketch. We say that a mixed pair is happy if both agents in the pair weakly prefer a mixed pair to a pure pair. The general idea of the algorithm is to first create as many happy mixed pairs as possible. The algorithm then attempts to put the remaining agents in pure pairs. If at this point the number of blue agents is odd, this is not possible. In this case, depending on the preferences of agents in mixed pairs, it either inserts an additional mixed pair or breaks up one of the mixed pairs to create two pure pairs: one red and one blue.

4 (Strong) Core Stability

We have seen that for the roommate diversity problem with s = 2 a core stable outcome is guaranteed to exist. However, for larger values of s this is not the case.

Theorem 2. An instance of the roommate diversity problem may fail to have a core stable outcome, even if no indifferences in the preferences are allowed.

Assume for the sake of contradiction that G has a core stable outcome π. If π consists of two coalitions of fraction 24 , {r4, b1, b2, b3} is blocking. If π consists of one coalition of fraction 3 4 and one coalition of fraction 14 , {r1, r2, r3, r4} is blocking. If π consists of a purely blue and a purely red coalition, {r1, r2, b1, b2} is blocking.

Further, if we assume that the room size is flexible and part of the input, the associated existence question becomes NPcomplete.

Theorem 3. It is NP-complete to decide whether a given instance of the roommate diversity problem admits a core stable outcome. The hardness result holds even if no indifferences in the preferences are allowed.

Proof sketch. To check whether an outcome is core stable, we iterate over all j ∈ [0, s] and check if there are j red agents and s-j blue agents preferring js to the fraction of their current coalition. To prove hardness, we reduce from the problem of deciding whether an anonymous hedonic game admits a core stable outcome [Ballester, 2004]. Given an anonymous hedonic game G′ with n agents, we build an n-dimensional instance G of the roommate diversity problem. To this end, for each agent i in G′ , we introduce a red agent ri whose preference relation is constructed by replacing each size ℓ ∈ [n] in the preferences of i with fraction ℓn . Moreover, for all ℓ ∈ [n], we introduce n2 blue agents preferring ℓn to every other fraction, while they rank all other fractions arbitrarily. To construct an outcome of G from an outcome π′ of G′ , for each coalition S ∈ π′ , we insert a coalition consisting of the corresponding red agents {ri : i ∈ S} and n - |S| blue agents with |S| n as their top fraction. If a coalition T blocks π′ in G′ , the coalition consisting of red agents {ri : i ∈ T} and n-|T| blue agents with |T| n as their top fraction is a blocking coalition for the respective outcome of G. The other direction works analogously.

Using the construction in the proof of Theorem 3, we can map the single-peaked anonymous hedonic game with empty core constructed by Banerjee et al. [2001] to a single-peaked instance of the roommate diversity problem with an empty core. We obtain the following corollary.

Corollary 1. An instance of the roommate diversity problem may fail to have a core stable outcome, even if all agents' preferences are single-peaked.

In contrast, if agents' preferences are dichotomous, the core is non-empty, and an outcome in the core can be computed efficiently: following the approach of Peters [2016], to construct a core stable outcome, we iterate over all fractions ℓs for ℓ ∈ [0, s] and add the maximum possible number of rooms consisting of ℓ red agents and s-ℓ blue agents who all approve ℓs . The rest of the agents are split into the remaining rooms. We obtain the following result.

Theorem 4. Every instance of the roommate diversity problem with dichotomous preferences admits a core stable outcome; moreover, an outcome in the core can be computed in polynomial time.

However, this positive result does not extend to the more demanding notion of strong core stability.

Theorem 5. It is NP-complete to decide whether a given roommate diversity problem admits a strongly core stable outcome, even if the preferences are restricted to be dichotomous and every agent approves at most four fractions.

Proof sketch. Peters [2016] showed that the corresponding problem for anonymous hedonic games is NP-complete. By reducing from this problem, we can establish that our problem is NP-hard as well; the reduction is similar to the one used in the proof of Theorem 3.

5 (Strong) Exchange Stability

As pointed out in the introduction, it is not always plausible to assume that agents are allowed to perform group deviations. Therefore, in this section, we focus on stability concepts that are defined in terms of agent swaps.

5.1 Same-Type Swaps

If the set of possible deviations is limited to agent swaps, it may be the case that only agents of the same type are allowed to swap their places: we call the resulting stability notion same-type-exchange stability. For example, if a professor forms fixed-size teams for a group project, she may want to fix the fraction of graduate students in each group (e.g., to ensure that the experienced students are equally distributed) but still allow for swaps between two undergraduate students or between two graduate students. Under this weaker version of exchange stability, the agents are guaranteed to eventually converge to a stable outcome.

Theorem 6. Every instance of the roommate diversity problem has a (strongly) same-type-exchange stable outcome, and some such outcome can be computed in polynomial time.

Proof. To compute a (strongly) same-type-exchange stable outcome, we start at an arbitrary outcome π and swap pairs who have a (weak) same-type-exchange deviation until this is no longer possible. To see that this procedure always terminates, note that same-type exchange deviations do not change the fraction of red agents in any coalition. Thereby, nothing changes for agents who are not involved in the swap, while both agents involved in the swap weakly improve and at least one of them strictly improves. As every agent's preference relation is defined over s + 1 elements, the total number of swaps is at most ns.

5.2 Unrestricted Swaps

Unfortunately, the existence guarantee for same-type swaps does not extend to unrestricted swaps.

Theorem 7. An instance of the roommate diversity problem may fail to have an exchange stable outcome, even if the preferences are single-peaked and no indifferences in the preferences are allowed.

Proof sketch. The following single-peaked roommate diversity game G = ({r1, r2, r3, r4, r5}, {b1, b2, b3, b4}, 3, (≿i )i∈N ) with:

does not admit an exchange-stable outcome.

Further, the associated existence problem for strong exchange stability is NP-complete.

Theorem 8. It is NP-complete to decide whether a given instance of the roommate diversity problem admits a strongly exchange stable outcome. The hardness result still holds if the preferences are dichotomous and every agent approves at most four fractions.

Proof sketch. To show hardness, we reduce from the problem of deciding whether an anonymous hedonic game admits a Nash stable outcome [Ballester, 2004; Peters, 2016]; recall that an outcome of a hedonic game is said to be Nash stable if no agent wants to move from her current coalition to another existing coalition or to form a singleton coalition. Our reduction is similar to the one in the proof of Theorem 3: we map an anonymous hedonic game G′ with n agents to an ndimensional instance of the roommate diversity problem G so that an agent i in G′ is mapped to a red agent in G whose preference relation is obtained from that of i by replacing ℓ with ℓn for all ℓ ∈ [1, n]; however, here, we introduce n2 -n blue agents who are indifferent among all fractions.

We believe that deciding whether a roommate diversity problem admits an exchange stable outcome is NP-complete as well, but we were unable to extend the proof of Theorem 8 to show this.

6 Pareto Optimality

In the roommate problem, Pareto optimality emerges as a natural notion of stability. Indeed, an outcome is not Pareto optimal if and only if we can rearrange the agents so that all of them are weakly better off and at least some of them are strictly better off, i.e., there is a weakly improving deviation by the grand coalition [Elkind et al., 2016; Morrill, 2010].

While for many other stability concepts we consider stable outcomes are not guaranteed to exist, by the definition of Pareto optimality, every instance of the roommate diversity problem admits a Pareto optimal outcome. Indeed, we can start at an arbitrary outcome and perform a sequence of at most ns Pareto improvements, i.e., rearrangements of the agents that make all agents weakly better off and some agents strictly better off. However, it is still computationally hard to compute a Pareto optimal outcome, as finding a Pareto improvement is difficult.

Theorem 9. For the unrestricted roommate diversity problem, it is coNP-complete to decide whether a given outcome is Pareto optimal; moreover, we cannot compute a Pareto optimal outcome in polynomial time unless P=NP. These results hold even if preferences are dichotomous.

Proof sketch. To show that an outcome is not Pareto optimal, it suffices to guess a Pareto improvement and verify that it indeed makes all agents weakly better off and some agents strictly better off; this establishes that our decision problem is in coNP. To prove hardness for the unrestricted case, we construct reductions from the related problems for anonymous hedonic games, which are NP-hard, as proven by Aziz et al. [2013]. The reductions are similar to the reduction in the proof of Theorem 8.

7 Envy-Freeness

We can think of envy-freeness as a "one-sided" version of exchange stability. Thus, similarly to same-type-exchange stability, we can define same-type-envy-freeness by only considering envy among agents of the same type. Same-typeenvy-freeness is a plausible variant of envy-freeness, as people tend to envy those who are similar to them [Salovey and Rodin, 1984]. Moreover, same-type-envy-freeness is also an appealing notion of fairness: if agent i and agent j are of the same type and i envies j, swapping i and j has no effect on other agents, so the decision which of these agents should get a better set of roommates is essentially arbitrary. Unfortunately, an outcome that is fair in this sense is not guaranteed to exist.

Theorem 10. There exists an instance of the roommate diversity problem with room size two that has no same-typeenvy-free outcome and thereby also no envy-free outcome. Moreover, in this instance the agents' preferences are singlepeaked and dichotomous.

This game is clearly single-peaked and can be transformed into a dichotomous game by putting the two bottom fractions for each agent in the same equivalence class. As every outcome of this game consists of one mixed and one purely blue coalition, the blue agent in the mixed coalition always envies the two blue agents in the pure coalition.

On the positive side, there exist two special cases where the existence of a same-type-envy-free outcome is guaranteed.

Theorem 11. A same-type-envy-free outcome is guaranteed to exist if the number of red agents is divisible by s or by k.

Proof. If s divides r, there exists an outcome consisting of pure coalitions only. If k divides r, there exists an outcome where the fraction of each coalition is rk . In either case, all agents of the same type are in coalitions of the same fraction, so no agent envies another agent of her type.

Nevertheless, it can be proven by a reduction from EXACT COVER BY 3-SETS that the general existence question for envy-freeness is NP-complete.

Theorem12. It is NP-complete to decide whether a given instance of the roommate diversity problem admits an envy-free outcome, even if no indifferences in the preference relations are allowed. This hardness result also holds if the agents' preferences are dichotomous and every agent is allowed to approve at most four fractions.

We were not able to extend Theorem 12 to same-typeenvy-freeness, but conjecture that the hardness result still holds. However, if preferences are strict, there exists a simple algorithm that solves this problem in time linear in n and single-exponential in s, i.e., this problem is in FPT with respect to s.

Theorem 13. Given an instance of the roommate diversity problem with room size s and strict preferences, it is possible to check in time O(ns2s ) whether this instance admits a same-type-envy-free outcome and to find one if it exists.

8 Parameterized Analysis

In Section 3, we saw that fixing the size of the rooms to s = 2 has a significant impact on the complexity of finding stable outcomes. Motivated by this result, as well as by Theorem 13, in this section, we study the parameterized complexity of the roommate diversity problem with respect to parameter s. This is a promising parameter, since in most of our hardness reductions we converted an anonymous hedonic game with n agents into an instance with room size n; it is also appealing because in practice the room size can be much smaller than the number of agents. Indeed, most of the algorithmic problems considered in this work turn out to be in FPT with respect to s. We start by considering (strong) core stability.

Theorem 14. The problem of determining whether an instance of the roommate diversity problem admits a (strongly) core stable outcome is fixed-parameter tractable with respect to the room size.

Proof sketch. As every agent is fully characterized by her preference relation and type, the number of distinct agents can be upper-bounded by 2 ∗ 2(s+1)2 . For each such agent class, we introduce s + 1 variables denoting the number of agents from this class that are put into a room with i ∈ [0, s] red agents. Using these variables, we can check whether they induce a valid outcome and whether this outcome is (strongly) core stable by appropriately selected linear constraints. Thereby, it is possible to formalize this problem as an Integer Linear Program (ILP) and use the algorithm of Lenstra Jr [1983] that solves an ILP with ρ variables and input length L in time O(ρ2.5ρ+o(ρ)L).

This approach, with appropriate modifications, extends to (strong) exchange stability and envy-freeness.

Theorem 15. The problem of determining whether an instance of the roommate diversity problem admits a (strongly) exchange stable outcome is fixed-parameter tractable with respect to the room size.

Theorem 16. The problem of determining whether an instance of the roommate diversity problem admits an envy-free outcome is fixed-parameter tractable with respect to the room size.

Theorems 14-16 highlight a fundamental difference between the classical stable roommate problem and the roommate problem with diversity preferences: for the former all studied existence problems are NP-complete for s = 3 or even for s = 2, while for the latter many of these problems are polynomial-time solvable if the size of the rooms is fixed or bounded. Thus, assuming diversity preferences fundamentally changes the complexity of the roommate problem. We note, however, that we were unable to extend our ILP techniques to questions concerning Pareto optimality; it remains an open problem whether these questions are also in FPT with respect to the room size s.

9 Conclusions And Future Directions

In this paper, we have proposed the roommate diversity problem, which is an interesting special case of the multidimensional stable roommate problem. We have initiated the algorithmic study of this problem by considering various standard solution concepts and analyzing the existence of stable outcomes and the complexity of computing them (see Table 1). While we have answered many questions that arise in this context, the complexity of deciding whether a roommate diversity problem admits an exchange stable outcome remains open. Moreover, it is unclear if every instance with dichotomous preferences admits an exchange stable outcome. By parameterizing our computational problems by the size of the rooms, we showed that diversity preferences are a powerful restriction, as all studied existence problems lie in FPT with respect to this parameter. However, it would be desirable to obtain parameterized algorithms that are combinatorial rather than ILP-based, since ILP-based algorithms tend to be slow in practice.

Acknowledgements

This work was supported by a DFG project "MaMu", NI 369/19 (Boehmer) and by an ERC Starting Grant ACCORD under Grant Agreement 639945 (Elkind).