Introduction
In multi-agent systems, coalition formation is the process of grouping agents into teams or societies. A prominent framework for studying this is Hedonic Games, where an agent's utility depends exclusively on the members of their own coalition. This paper investigates the dynamics of decentralized coalition formation, specifically focusing on whether individual, self-interested moves by agents lead to a stable partition—a state where no agent has an incentive to change groups.
The research addresses two primary gaps in the literature: the convergence of single-agent dynamics (avoiding infinite cycles) and the impact of various consent rules, moving beyond simple unilateral moves to more realistic majority-based decision-making.
Stability Notions and Taxonomy
The authors analyze a wide spectrum of stability concepts within Additively Separable Hedonic Games (ASHGs). In ASHGs, an agent's total utility is the sum of their individual preferences for every other member in their coalition. The stability notions range from Nash Stability (NS), where agents move freely, to Individual Stability (IS), which requires unanimous consent from the receiving group.
The paper introduces new majority-based notions, such as Joint-Majority Stability (JMS), where a move is permitted if it benefits the moving agent and is supported by a majority of the target coalition. This taxonomy provides a structured way to understand the trade-offs between agent autonomy and group consensus.
The Deviation Lemma and Game Classes
A core contribution of this work is the Deviation Lemma, a novel combinatorial tool that tracks changes in coalition sizes during a sequence of moves. This lemma allows for the construction of potential functions that guarantee convergence to a stable state in polynomial time for specific classes of games, even when local moves might temporarily decrease social welfare.
The analysis focuses on three restricted utility classes:
- Friends-and-Enemies Games (FEG): Utilities are binary (+1 or -1).
- Appreciation of Friends Games (AFG): Agents prioritize the presence of friends over the absence of enemies.
- Aversion to Enemies Games (AEG): Agents prioritize avoiding enemies over gaining friends.
Computational Complexity and Convergence
The paper establishes a clear boundary between computationally tractable and intractable stability problems. While finding a Nash stable partition is generally NP-complete, many stability notions involving consent (like IS or JMS) are solvable in polynomial time (FP) for the restricted game classes mentioned above.
Key results include proofs that single-agent dynamics for JMS and SMS (Simple-Majority Stability) always converge efficiently in FEGs, AFGs, and AEGs. Conversely, the authors use mathematical reductions to prove the hardness of finding Nash stable partitions even under severe utility restrictions.
Conclusion
This research provides a comprehensive map of the landscape of single-agent dynamics in hedonic games. By introducing the Deviation Lemma and exploring majority-based consent, the authors bridge the gap between decentralized agent behavior and global stability. Future work remains to address the complexity of certain notions in unrestricted utility settings and to explore the existence of stable partitions for specific majority-based rules.
Summary updated