Towards Structural Tractability in Hedonic Games
Authors: Dominik Peters
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate a structural way of achieving tractability, by requiring that agents preferences interact in a well-behaved manner. Precisely, we show that stable outcomes can be found in linear time for hedonic games that satisfy a notion of bounded treewidth and bounded degree. Theorem 2 (Peters 2016b). For any logical sentence φ of HG-logic that may quantify over (connected) partitions, coalitions, and agents, the problem of deciding whether a hedonic game given by an HC-net satisfies φ is fixed-parameter tractable with parameters the treewidth and degree of the dependency graph of the game. Proof idea. Encode HG-logic into monadic second-order logic, and use Courcelle s theorem. |
| Researcher Affiliation | Academia | Dominik Peters Department of Computer Science University of Oxford, UK dominik.peters@cs.ox.ac.uk |
| Pseudocode | No | No pseudocode or algorithm blocks were found in the paper. |
| Open Source Code | No | The paper does not provide any specific links or statements about the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not describe the use of specific datasets with public access information. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental validation with dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or hardware used. |
| Software Dependencies | No | The paper is theoretical and does not list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe a concrete experimental setup with hyperparameters or training configurations. |