Economics at your fingertips  

Stable Roommate Problem with Diversity Preferences

Niclas Boehmer and Edith Elkind

Papers from

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 et al., 2019]: 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.

Date: 2020-04
New Economics Papers: this item is included in nep-des, nep-gen and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed

Downloads: (external link) Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link:

Access Statistics for this paper

More papers in Papers from
Bibliographic data for series maintained by arXiv administrators ().

Page updated 2022-07-23
Handle: RePEc:arx:papers:2004.14640