Core Stability in Additively Separable Hedonic Games of Low Treewidth
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909109406662656 |
|---|---|
| author | Hanaka, Tesshu Köhler, Noleen Lampis, Michael |
| author_facet | Hanaka, Tesshu Köhler, Noleen Lampis, Michael |
| contents | 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 ($Σ_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_10815 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Core Stability in Additively Separable Hedonic Games of Low Treewidth Hanaka, Tesshu Köhler, Noleen Lampis, Michael Data Structures and Algorithms Computational Complexity Computer Science and Game Theory 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 ($Σ_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. |
| title | Core Stability in Additively Separable Hedonic Games of Low Treewidth |
| topic | Data Structures and Algorithms Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2402.10815 |