Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games
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.
Cite
Text
Bullinger and Gilboa. "Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games." International Joint Conference on Artificial Intelligence, 2025. doi:10.24963/IJCAI.2025/419Markdown
[Bullinger and Gilboa. "Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games." International Joint Conference on Artificial Intelligence, 2025.](https://mlanthology.org/ijcai/2025/bullinger2025ijcai-settling/) doi:10.24963/IJCAI.2025/419BibTeX
@inproceedings{bullinger2025ijcai-settling,
title = {{Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games}},
author = {Bullinger, Martin and Gilboa, Matan},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2025},
pages = {3771-3779},
doi = {10.24963/IJCAI.2025/419},
url = {https://mlanthology.org/ijcai/2025/bullinger2025ijcai-settling/}
}