Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games

Bullinger, Martin; Gilboa, Matan

doi:10.24963/ijcai.2025/419

Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 3771-3779.

https://doi.org/10.24963/ijcai.2025/419

Keywords

Game Theory and Economic Paradigms: GTEP: Cooperative games
Game Theory and Economic Paradigms: GTEP: Computational social choice

Abstract

We study coalition formation in the framework of hedonic games. These games model the problem of partitioning a set of agents having a preference order over the coalitions they can be part of. A partition is called popular if it does not lose a majority vote among the agents against any other partition. Unfortunately, hedonic games need not admit popular partitions. We go further and settle the complexity of the existence problem concerning popularity in additively separable and fractional hedonic games by showing that it is Sigma_2^p-complete in both cases. We are thus the first work that proves a completeness result of popularity for the second level of the polynomial hierarchy.

Martin Bullinger, and Matan Gilboa. 2025. Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 3771–3779. https://doi.org/10.24963/ijcai.2025/419

@inproceedings{ijcai2025p419,
  title     = {Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games},
  author    = {Bullinger, Martin and Gilboa, Matan},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {3771--3779},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/419},
  url       = {https://doi.org/10.24963/ijcai.2025/419},
}

TY  - CPAPER
TI  - Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games
AU  - Bullinger, Martin
AU  - Gilboa, Matan
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 3771
EP  - 3779
DO  - 10.24963/ijcai.2025/419
UR  - https://doi.org/10.24963/ijcai.2025/419
ER  -