Back to Search
Start Over
Stable Roommate Problem with Diversity Preferences
- Source :
- Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI
- Publication Year :
- 2020
- Publisher :
- arXiv, 2020.
-
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.<br />Comment: accepted to IJCAI'20
- Subjects :
- FOS: Computer and information sciences
Computer science
Stability (learning theory)
Pareto principle
0102 computer and information sciences
02 engineering and technology
Decision problem
01 natural sciences
FOS: Economics and business
Core (game theory)
010201 computation theory & mathematics
Computer Science - Computer Science and Game Theory
0202 electrical engineering, electronic engineering, information engineering
Economics - Theoretical Economics
Theoretical Economics (econ.TH)
020201 artificial intelligence & image processing
Fraction (mathematics)
Mathematical economics
Diversity (business)
Stable roommates problem
Computer Science and Game Theory (cs.GT)
Subjects
Details
- ISBN :
- 978-0-9992411-6-5
- ISBNs :
- 9780999241165
- Database :
- OpenAIRE
- Journal :
- Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI
- Accession number :
- edsair.doi.dedup.....3cc3668bd8a3c191e3eaee4382a34279
- Full Text :
- https://doi.org/10.48550/arxiv.2004.14640