2026/07/29 by Matan Gilboa
Computer Science · #cs.GT #cs.CC
A preliminary version of the results in this paper appeared as part of earlier versions of arXiv:2510.19084, when the two works formed a single manuscript
arxiv created 2026/07/29 · arxiv updated 2026/07/31
In a hedonic game, agents need to be partitioned into coalitions, and have a preference order over partitions. A partition is called strongly popular if it beats any other partition in a majority vote among the agents. We focus on the fundamental class of additively separable hedonic games (ASHGs), where agents have additive valuations that induce their preferences. We prove that determining the existence of strongly popular partitions in ASHGs is complete for PCW, a recently introduced complexity class which lies in between PNP and S2P (Gilboa et al., 2025). This settles an open problem by Brandt and Bullinger (2022) and Bullinger and Gilboa (2025).