Matan Gilboa settles open problem: strong popularity is PCW-complete
Proving existence of strongly popular partitions in ASHGs is computationally hard, ending a 2022 open question.
Matan Gilboa's new paper, posted on arXiv (2607.27277), tackles a fundamental question in cooperative game theory: when can a set of agents be partitioned into coalitions such that no alternative partition wins a majority vote by the agents themselves? This concept, known as a 'strongly popular' partition, is the gold standard for stability in hedonic games. Gilboa focuses on the widely studied class of additively separable hedonic games (ASHGs), where each agent assigns additive numerical values to other agents, and preferences over coalitions are derived from these sum values.
Gilboa's main result is that the problem of determining whether such a partition exists is complete for PCW, a recently introduced complexity class sitting between P^NP and S_2^P. This completes a line of research that Brandt and Bullinger (2022) and later Bullinger and Gilboa (2025) had left open. The proof is significant because it precisely classifies the algorithmic hardness: the problem is strictly harder than NP-complete problems in terms of oracle access, yet still within the polynomial hierarchy. For AI and multi-agent systems, this means that any general algorithm for coalition formation under additive preferences must either sacrifice optimality or rely on heuristics, as an exact solution is provably intractable in the worst case.
- Proves that checking existence of strongly popular partitions in ASHGs is PCW-complete, settling an open problem by Brandt and Bullinger (2022).
- PCW is a complexity class between P^NP and S_2^P, introduced by Gilboa et al. in 2025.
- The result means coalition formation in additive preference games is computationally intractable in general, guiding practical AI approaches toward approximation or heuristics.
Why It Matters
For AI agents negotiating coalitions, this result proves exact fairness is computationally out of reach, pushing research toward scalable heuristics and approximation.