Complexity of Probabilistic Inference in Random Dichotomous Hedonic Games

Saar Cohen, Noa AgmonAAAI 2023 · DOI

Introduction

In cooperative game theory, hedonic games model the formation of coalitions where agents' preferences depend solely on the members of their own group. Traditional models assume deterministic participation and certain preferences. However, real-world scenarios—ranging from political voting blocs to sports teams—are often plagued by uncertainty. A player might be sidelined by injury, or a voter might be delayed by traffic.

This paper introduces Random Dichotomous Hedonic Games (RDHGs), a framework where each agent $i$ has an independent probability $p_i$ of participating. The research focuses on the probabilistic inference problem: calculating the likelihood that a resulting coalition partition will satisfy specific criteria, such as being "optimal" (maximizing social welfare) or "stable" (where no agent has an incentive to deviate).

Preference Representations and Methodology

The authors analyze Dichotomous Hedonic Games (DHGs), where agents have binary preferences (approval or disapproval) for coalitions. They explore several ways agents express these preferences:

  • 1-Lists and k-Lists: Agents approve a small, fixed number of specific coalitions.
  • Anonymous Hedonic Games (AHGs): Preferences depend only on the size of the coalition.
  • Candidate Intervals (CIs): Agents approve coalitions that form a continuous interval on a predefined line.
  • Majority Games: Agents approve a group if they are "friends" with the majority of its members.

The study employs combinatorial reductions—notably linking these games to election control problems—and dynamic programming to map the computational boundaries of these problems. As a theoretical work, it focuses on mathematical proofs rather than empirical datasets.

Key Insights

The Election Connection

A significant theoretical contribution is the reduction showing that calculating probabilities in RDHGs is mathematically equivalent to "constructive control by adding players" in voting theory. Ensuring a stable coalition in an RDHG is analogous to strategically adding voters to ensure a specific candidate's victory.

Complexity "Flip"

While standard DHGs are often solvable in polynomial time, the introduction of probabilistic participation often elevates the complexity to #P-hardness. This shift indicates that while finding a single stable outcome might be easy, counting the participation scenarios that lead to such an outcome is computationally intractable.

Poisson Convergence and Welfare Gaps

In majority games, the authors prove that the number of small stable coalitions (specifically size 3) follows a Poisson distribution as the player count grows. Additionally, they introduce the Price of Perfection (PP) and Expected Price of Perfection (EPP) to quantify the social welfare gap between the best possible outcome and a "perfect" partition where every agent is satisfied.

Key Results

The research culminates in a comprehensive "complexity map" detailing the difficulty of inference across different game classes and stability concepts.

Table 1: Complexity of probabilistic inference for various classes of dichotomous hedonic games.

Key findings include:

  • Polynomial Time: Computing the probability of welfare-optimal ($WO$) coalitions is feasible for 1-Lists and Candidate Intervals.
  • #P-Hardness: Computing probabilities for k-Lists ($k \ge 2$) and Anonymous Hedonic Games is generally #P-hard.
  • NP-Completeness: Determining if the probability of a Strict-Core-Stable (SCS) partition is greater than zero is NP-complete, even for simple 1-List games.
  • Approximation: For intractable cases, the authors provide a Fully Polynomial-time Randomized Approximation Scheme (FPRAS) to estimate the probability of non-optimality.

Limitations and Future Directions

The current model assumes that agent participation is independent. In practice, participation is often correlated (e.g., a group of friends traveling together). Furthermore, the study is restricted to dichotomous preferences, whereas real-world utilities are often multi-valued.

Future research aims to investigate the robustness of coalitions—determining the maximum number of withdrawals a stable outcome can withstand—and extending these probabilistic tools to non-dichotomous hedonic games.

Summary updated

BibTeX
@inproceedings{cohen2023complexity,
  author = {Saar Cohen and Noa Agmon},
  title = {{Complexity of Probabilistic Inference in Random Dichotomous Hedonic Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25692},
}
Figure