Simple Causes of Complexity in Hedonic Games
Authors: Dominik Peters, Edith Elkind
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we identify simple conditions on expressivity of hedonic games that are sufficient for the problem of checking whether a given game admits a stable outcome to be computationally hard. Somewhat surprisingly, these conditions are very mild and intuitive. Our results apply to a wide range of stability concepts (core stability, individual stability, Nash stability, etc.) and to many known formalisms for hedonic games (additively separable games, games with W-preferences, fractional hedonic games, etc.), and unify and extend known results for these formalisms. They also have broader applicability: for several classes of hedonic games whose computational complexity has not been explored in prior work, we show that our framework immediately implies a number of hardness results for them. |
| Researcher Affiliation | Academia | Dominik Peters and Edith Elkind Department of Computer Science University of Oxford, UK {dominik.peters, edith.elkind}@cs.ox.ac.uk |
| Pseudocode | No | The paper describes algorithms and reductions in prose and mathematical notation but does not include structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement about releasing source code for its methodology or any links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not involve empirical experiments with datasets; no dataset access information for training is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets; no information about validation splits is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments; no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments; no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments; no details on hyperparameters or system-level training settings are provided. |