Stable Roommate Problem with Diversity Preferences
Authors: Niclas Boehmer, Edith Elkind
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | TU Berlin, Berlin, Germany University of Oxford, Oxford, UK niclas.boehmer@tu-berlin.de, elkind@cs.ox.ac.uk |
| Pseudocode | No | The paper describes algorithms and proof sketches in narrative text, but it does not include formal pseudocode blocks or figures labeled 'Algorithm'. |
| Open Source Code | No | The paper states: 'The full version of the paper is available on arXiv [Boehmer and Elkind, 2020b].' This refers to the full version of the paper document, not source code for the methodology. |
| Open Datasets | No | The paper is theoretical and focuses on complexity proofs and the existence of solutions for mathematical problem instances, not on empirical data training or datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets, therefore no training/validation/test splits are mentioned. |
| Hardware Specification | No | The paper is theoretical and does not describe any computational experiments that would require specific hardware. No hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and analysis, not empirical experiments that would have a setup with hyperparameters or system-level settings. |