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

arXiv: https://arxiv.org/abs/2411.05713 · HTML: https://mlsanity.com/paper/2411.05713/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Nov 2024.

## Built on by (most cited first, 1 of 1)

- [Coalition Formation in LLM Agent Networks: Stability Analysis and Convergence Guarantees](https://mlsanity.com/paper/2604.14386/) (2026)

## Abstract (arXiv)

We study coalition formation in the framework of hedonic games. There, a set of agents needs to be partitioned into disjoint coalitions, where agents have a preference order over coalitions. 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 and prior work suggests significant computational hardness. We confirm this impression by proving that deciding about the existence of popular partitions in additively separable and fractional hedonic games is Sigma2p-complete. This settles the complexity of these problems and is the first work that proves completeness of popularity for the second level of the polynomial hierarchy.