Solving Four Open Problems about Core Stability in Altruistic Hedonic Games
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911291635924992 |
|---|---|
| author | Rothe, Jörg Schlotter, Ildikó |
| author_facet | Rothe, Jörg Schlotter, Ildikó |
| contents | Hedonic games -- at the interface of cooperative game theory and computational social choice -- are coalition formation games in which the players have preferences over the coalitions they can join. Kerkmann et al. [13] introduced altruistic hedonic games where the players' utilities depend not only on their own but also on their friends' valuations of coalitions. The complexity of the verification problem for core stability has remained open in four variants of altruistic hedonic games: namely, for the variants with average- and minimum-based "equal-treatment" and "altruistic-treatment" preferences. We solve these four open questions by proving the corresponding problems coNP-complete; our reductions rely on rather intricate gadgets in the related networks of friends. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22370 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Solving Four Open Problems about Core Stability in Altruistic Hedonic Games Rothe, Jörg Schlotter, Ildikó Computer Science and Game Theory Computational Complexity Hedonic games -- at the interface of cooperative game theory and computational social choice -- are coalition formation games in which the players have preferences over the coalitions they can join. Kerkmann et al. [13] introduced altruistic hedonic games where the players' utilities depend not only on their own but also on their friends' valuations of coalitions. The complexity of the verification problem for core stability has remained open in four variants of altruistic hedonic games: namely, for the variants with average- and minimum-based "equal-treatment" and "altruistic-treatment" preferences. We solve these four open questions by proving the corresponding problems coNP-complete; our reductions rely on rather intricate gadgets in the related networks of friends. |
| title | Solving Four Open Problems about Core Stability in Altruistic Hedonic Games |
| topic | Computer Science and Game Theory Computational Complexity |
| url | https://arxiv.org/abs/2511.22370 |