arXiv:2607.27277 · v2
Complexity of Strong Popularity in Hedonic Games
摘要
In a hedonic game, agents are partitioned into coalitions and have preferences over the coalitions they may join. A partition is called strongly popular if it strictly beats every other partition in a majority vote among the agents. We study the complexity of determining the existence of strongly popular partitions in two fundamental classes of hedonic games: additively separable and fractional hedonic games (ASHGs and FHGs), where agents' utilities are determined, respectively, by the sum and average of their valuations for the members of their coalitions. We prove that this problem is PCW-complete for ASHGs and for FHGs even with non-negative valuations, where PCW is a subclass of associated with unambiguous problems (which have at most one witness), recently introduced by Gilboa et al. (2025). These are the first natural complete problems for PCW, in the sense that their formulations do not involve arbitrary Boolean circuits. Our results resolve open problems posed by Brandt and Bullinger (JAIR 2022) and Bullinger and Gilboa (IJCAI 2025). The two reductions employ substantially different techniques, reflecting both the distinct utility models and the stringent non-negativity constraint in FHGs. Furthermore, in contrast with FHGs, we show that in ASHGs restricting valuations to be non-negative makes the problem polynomial-time solvable.
作者备注：This version includes additional results: Theorems 1.2 and 1.3. A preliminary version of Theorem 1.1 in this paper appeared as part of earlier versions of arXiv:2510.19084, when the two works formed a single manuscript