Towards Structural Tractability in Hedonic Games
Abstract
Hedonic games are a well-studied model of coalition formation, in which selfish agents are partitioned into disjoint sets, and agents care about the make-up of the coalition they end up in. The computational problem of finding a stable outcome tends to be computationally intractable, even after severely restricting the types of preferences that agents are allowed to report. 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.
Cite
Text
Peters. "Towards Structural Tractability in Hedonic Games." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.9935Markdown
[Peters. "Towards Structural Tractability in Hedonic Games." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/peters2016aaai-structural/) doi:10.1609/AAAI.V30I1.9935BibTeX
@inproceedings{peters2016aaai-structural,
title = {{Towards Structural Tractability in Hedonic Games}},
author = {Peters, Dominik},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {4252-4253},
doi = {10.1609/AAAI.V30I1.9935},
url = {https://mlanthology.org/aaai/2016/peters2016aaai-structural/}
}