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.
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