Core Stability in Additively Separable Hedonic Games of Low Treewidth
<|reference_start|>Core Stability in Additively Separable Hedonic Games of Low Treewidth: Additively Separable Hedonic Game (ASHG) are coalition-formation games where we are given a graph whose vertices represent $n$ selfish agents and the weight of each edge $uv$ denotes how much agent $u$ gains (or loses) when she is placed in the same coalition as agent $v$. We revisit the computational complexity of the well-known notion of core stability of ASHGs, where the goal is to construct a partition of the agents into coalitions such that no group of agents would prefer to diverge from the given partition and form a new (blocking) coalition. Since both finding a core stable partition and verifying that a given partition is core stable are intractable problems ($\Sigma_2^p$-complete and coNP-complete respectively) we study their complexity from the point of view of structural parameterized complexity, using standard graph-theoretic parameters, such as treewidth.<|reference_end|>
@article{hanaka2024core,
    title={Core Stability in Additively Separable Hedonic Games of Low Treewidth},
    author={Tesshu Hanaka, Noleen K"ohler and Michael Lampis},
    journal={arXiv preprint arXiv:2402.10815},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10815},
    primaryClass={cs.DS cs.CC cs.GT}
}