Introduction
Coalition formation is a fundamental problem in multiagent systems, modeling scenarios from research team assembly to international alliances. Hedonic games provide a formal framework for this, where agents' preferences depend solely on the members of their own coalition. While traditional research has focused on the existence and centralized computation of stable partitions, this paper investigates the decentralized process: can agents reach stability through individual, self-interested moves?
Individual Stability Dynamics
The authors focus on Individual Stability (IS). In IS dynamics, an agent moves to a new coalition only if they prefer the new group and no member of the welcoming coalition is made worse off. This "no-harm" condition distinguishes IS from simpler Nash stability. The study addresses three core questions:
- Convergence: Does every sequence of IS moves eventually terminate in a stable partition?
- Reachability: If a stable partition exists, is there a sequence of moves that leads to it?
- Complexity: How difficult is it to determine if a stable state is reachable?
Analysis Across Game Classes
The paper evaluates four prominent classes of hedonic games: Anonymous (AHGs), Hedonic Diversity (HDGs), Fractional (FHGs), and Dichotomous (DHGs). Each class represents different ways agents value their groups, from simple size preferences to complex average valuations of peers.
Key Findings and Convergence
A major contribution is the identification of conditions that guarantee convergence. For AHGs and HDGs, "naturally single-peaked" preferences—where agents have an ideal group size or ratio and dislike deviations from it—are shown to be strong drivers of stability.
However, stability is not always guaranteed. The authors settle a long-standing open problem by providing a 15-agent counterexample demonstrating that stable partitions may not exist even in symmetric Fractional Hedonic Games. Furthermore, they show that dynamics can cycle, failing to reach a stable state even when one exists. For Anonymous games, the authors identified a 15-agent instance that fails to reach stability, a significant improvement over previous 63-agent examples, suggesting that instability is more common than previously thought.
The Importance of the Initial State
A recurring theme is the "Singleton Advantage." Starting from a partition where every agent is in their own coalition (singletons) often leads to better outcomes. For instance, in simple symmetric FHGs, the authors prove that dynamics starting from singletons will converge in at most $O(n^2)$ steps. In contrast, starting from an arbitrary partition can lead to cycles or NP-hard reachability problems.
Computational Complexity
The paper establishes that finding a path to stability is generally hard. By using complexity reductions from problems like 3-SAT, the authors prove that deciding if a stable partition is reachable (the $\exists$-IS-SEQUENCE problem) is NP-hard across all four game classes. This suggests that while decentralized moves are a natural way for coalitions to form, they do not provide an efficient "algorithm" for finding stable structures in the worst case.
Conclusion
By shifting the focus from static existence to dynamic reachability, this work provides a more realistic view of coalition formation. While the complexity results are pessimistic, the convergence proofs for restricted preferences and the fast guarantees for singleton starts offer practical paths forward for designing stable multiagent systems. Future research may explore specific movement heuristics or coalitional moves to bypass the identified bottlenecks.
Summary updated