Coalition formation is a fundamental aspect of cooperative game theory, yet modeling real-world group dynamics often requires more than simple pairwise relationships. This research, presented at AAAI-20, introduces Hypergraph Hedonic Games (HHGs) to capture scenarios where agent utility depends on complex group interactions. The study provides the first comprehensive theoretical analysis of the "Price of Anarchy" (PoA) in these games, establishing tight bounds on social welfare loss and proving that calculating this inefficiency is computationally NP-hard.
Modeling Complex Coalitions
In traditional Hedonic Games, agent preferences are typically modeled using simple graphs where edges represent mutual appreciation between two individuals. However, many scenarios—such as forming R&D teams or political alliances—exhibit "critical mass" effects. For instance, a specific trio of experts might be necessary for a project's success, whereas any two of them alone provide no value.
To address this, the authors utilize hypergraphs, where "hyperedges" can connect any number of agents. This allows for a more nuanced representation of group benefits and interactions.
The central inquiry of this work is the Price of Anarchy (PoA): the ratio between the maximum possible social welfare (the social optimum) and the welfare achieved in the worst-case stable outcome where no agent or group has an incentive to deviate.
Stability and Methodology
The researchers employ a rigorous mathematical framework to bound the inefficiency of stable outcomes, focusing on two primary stability concepts:
- $k$-Nash Stability: No group of up to $k$ agents can improve their individual utilities by moving to existing coalitions or forming a new one.
- $k$-core Stability: No group of up to $k$ agents can all improve their utility by breaking away to form a new coalition together.
A key contribution is the definition of "standard" hypergraph hedonic games. In these games, hyperedge weights satisfy mild assumptions ensuring agents aren't "unhappy on average" within a group. The PoA is then analyzed based on the total number of agents ($n$), the maximum hyperedge size ($r$), and the maximum size of a deviating group ($k$).
Key Theoretical Insights
The study reveals that the inefficiency of the game is heavily influenced by the hypergraph arity ($r$). As the size of required groups increases, the potential gap between the social optimum and stable outcomes grows polynomially.
Crucially, the "standard" weight assumption is vital; without it, the Price of Anarchy can become infinite. This implies that in unrestricted settings, selfish behavior can lead to outcomes with zero social welfare, even when highly beneficial configurations are possible. For the most common scenarios (where $k \ge r$), the PoA scales as $\Theta((n/k)^{r-1})$, providing a clear mathematical rule for how inefficiency scales with population size.
Results and Computational Complexity
The authors established tight upper and lower bounds for the Price of Anarchy. For standard HHGs where $k \ge r$, the $k$-core PoA is at most $\frac{r(n-1)_{r-1}}{(k-1)_{r-1}}$. They provided a construction demonstrating that this bound is asymptotically tight.
Beyond theoretical bounds, the paper proves that determining the exact inefficiency of a game is NP-hard. This suggests that central authorities cannot easily calculate the "cost of selfishness" in complex group dynamics, even with full knowledge of agent preferences.
Future Directions
While the bounds are asymptotically tight, a constant multiplicative gap remains between the lower and upper bounds. A specific open case involves standard HHGs where $k = r - 1$; it remains unknown if a finite bound exists for this boundary condition. Future work may also explore how specific hypergraph topologies, such as sparsity or planarity, might mitigate social welfare loss.
Summary updated