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

Martin Bullinger, Matan GilboaIJCAI 2025 · DOI

TL;DR

This paper settles the computational complexity of finding "popular" outcomes in coalition formation games, specifically for additively separable and fractional hedonic games. The authors prove that determining the existence of such outcomes is $\Sigma_2$-complete, a significant jump in complexity from previous NP-hardness results, highlighting the inherent difficulty of achieving consensus in these scenarios.

What Problem Does This Paper Address?

Imagine a group of agents (people, companies, or even software agents) who need to form coalitions or teams. Each agent has preferences about which coalition they'd rather be in. A "popular" coalition structure is one that no other possible structure can "beat" in a majority vote among the agents. This concept is appealing because it captures a sense of stability and widespread agreement.

However, the problem is that in many realistic coalition formation scenarios, popular outcomes might not even exist. This paper focuses on two specific types of games:

  • Additively Separable Hedonic Games (ASHGs): An agent's utility for a coalition is the sum of values they assign to other members of that coalition.
  • Fractional Hedonic Games (FHGs): Similar to ASHGs, but the utility is the average value assigned to other members, divided by the coalition size.

The core problem addressed is: Given an ASHG or FHG, does there exist at least one popular partition (coalition structure)? While previous work established that finding popular outcomes is hard (NP-hard), the exact complexity remained elusive. This paper aims to precisely pinpoint this complexity.

Methods

The paper tackles the complexity question by employing $\Sigma_2$-completeness proofs. This involves two main steps:

  1. Showing Membership in $\Sigma_2$: The authors demonstrate that the problem of deciding whether a popular partition exists can be verified in polynomial time by a machine that has access to an existential quantifier followed by a universal quantifier. This is achieved by leveraging the definition of popularity, which involves checking if any other partition can defeat the proposed one.
  2. Showing $\Sigma_2$-hardness: This is the more involved part. The authors construct reductions from a known $\Sigma_2$-complete problem, 2-QUANTIFIED 3-DNF-SAT, to the existence problems for ASHGs and FHGs.
  3. For ASHGs: They design a complex hedonic game with many agents representing variables, their negations, clauses, and structural elements. The construction is carefully crafted such that a popular partition in the hedonic game corresponds directly to a satisfying assignment for the 2-QUANTIFIED 3-DNF-SAT instance. The proof involves showing that if a satisfying assignment exists, a specific partition is popular, and conversely, if a popular partition exists, it can be used to extract a satisfying assignment.
  4. For FHGs: A similar reduction strategy is used, but it's adapted for the fractional nature of utilities. This involves using "gadgets" (smaller FHGs known not to admit popular partitions) to encode parts of the SAT instance. The construction ensures that popularity in the overall FHG hinges on the satisfiability of the original logical formula.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity proofs and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • The jump to $\Sigma_2$ is significant: While NP-hardness is challenging, $\Sigma_2$-completeness indicates a substantially higher level of computational difficulty. This means that even with sophisticated solvers, finding popular outcomes in these games could be prohibitively difficult for large instances.
  • Popularity is a strong notion: The paper reinforces that popularity, while intuitive, is a demanding criterion. The complexity arises from the need to check against all possible alternative partitions, and the interaction between agents' preferences can create intricate dependencies.
  • Construction of complex hedonic games: The core technical contribution lies in the ingenious construction of specific hedonic games that precisely mirror the structure of the 2-QUANTIFIED 3-DNF-SAT problem. This demonstrates a powerful technique for proving hardness results in this domain.
  • Fractional vs. Additive utilities matter: The paper shows that even with the restriction of non-negative valuations, FHGs remain $\Sigma_2$-complete, highlighting that the division by coalition size introduces complexity that isn't present in simple additive utilities.

Key Results

  • ASHG-EXISTS-POPULAR is $\Sigma_2$-complete: The problem of determining if an additively separable hedonic game admits a popular partition is $\Sigma_2$-complete.
  • FHG-EXISTS-POPULAR is $\Sigma_2$-complete: The problem of determining if a fractional hedonic game admits a popular partition is $\Sigma_2$-complete, even when agent valuations are restricted to be non-negative.

These results settle the precise complexity of popularity for these two prominent classes of hedonic games, placing them at the second level of the polynomial hierarchy.

Limitations and Future Work

  • Generalization to other hedonic games: The authors suggest that their methods might be applicable to resolving the complexity of popularity in other coalition formation games where popularity has been studied but not fully characterized.
  • Strong and Mixed Popularity: The paper notes that related concepts like "strong popularity" (where a partition must strictly win against all others) and "mixed popularity" (considering probabilistic outcomes) have different complexity profiles and remain open research questions. Resolving their complexity could lead to a richer understanding of consensus mechanisms.
  • Practical implications: While the theoretical results highlight extreme difficulty, future work could explore approximation algorithms or heuristics for finding "near-popular" outcomes in practice, especially for large-scale applications.

Summary updated

BibTeX
@inproceedings{bullinger2025settling,
  author = {Martin Bullinger and Matan Gilboa},
  title = {{Settling the Complexity of Popularity in Additively Separable and Fractional Hedonic Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/419},
}
Figure