Graphical Hedonic Games of Bounded Treewidth
Authors: Dominik Peters
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We introduce the notion of a graphical hedonic game and show that, in contrast, on classes of graphical hedonic games whose underlying graphs are of bounded treewidth and degree, such problems become easy. In particular, problems that can be specified through quantification over agents, coalitions, and (connected) partitions can be decided in linear time. The proof is by reduction to monadic second order logic. We also provide faster algorithms in special cases, and show that the extra condition of the degree bound cannot be dropped. |
| Researcher Affiliation | Academia | Dominik Peters Department of Computer Science University of Oxford, UK dominik.peters@cs.ox.ac.uk |
| Pseudocode | No | The paper discusses algorithmic approaches and time complexities but does not present any structured pseudocode or algorithm blocks labeled as 'Pseudocode' or 'Algorithm'. |
| Open Source Code | No | The paper is theoretical and does not mention releasing any code or provide links to any code repositories related to its methodology. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity and algorithm design; it does not utilize or refer to any datasets, public or otherwise. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments or dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware specifications (e.g., GPU/CPU models) used for running experiments, as no experiments are described. |
| Software Dependencies | No | The paper is theoretical and focuses on mathematical and logical constructs; it does not mention any software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup, nor does it provide details about hyperparameters or system-level training settings, as it does not conduct empirical experiments. |