Complexity of Hedonic Games with Dichotomous Preferences
Authors: Dominik Peters
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we study the computational complexity of questions related to finding optimal and stable partitions in dichotomous hedonic games under various ways of restricting and representing the collection of approved coalitions. Encouragingly, many of these problems turn out to be polynomial-time solvable. In particular, we show that an individually stable outcome always exists and can be found in polynomial time. We also provide efficient algorithms for cases in which agents approve only few coalitions, in which they only approve intervals, and in which they only approve sets of size 2 (the roommates case). These algorithms are complemented by NP-hardness results, especially for representations that are very expressive, such as in the case when agents goals are given by propositional formulas. |
| Researcher Affiliation | Academia | Dominik Peters Department of Computer Science University of Oxford, UK dominik.peters@cs.ox.ac.uk |
| Pseudocode | Yes | Algorithm 1 Find an individually stable partition |
| Open Source Code | No | The paper does not provide any links or explicit statements about releasing source code for its own described methods. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity and algorithms. It does not describe experiments with datasets, thus no training data information is provided. |
| Dataset Splits | No | The paper is theoretical and focuses on computational complexity and algorithms. It does not describe experiments with datasets, thus no validation split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments requiring specific hardware, so no hardware specifications are mentioned. |
| Software Dependencies | No | The paper describes theoretical algorithms and complexity analysis and does not mention specific software dependencies with version numbers for implementation. |
| Experiment Setup | No | The paper describes theoretical algorithms and complexity analysis and does not describe an experimental setup with hyperparameters or training settings. |