Causes of Stability in Dynamic Coalition Formation

Niclas Boehmer, Martin Bullinger, Anna Maria Kerkmann

Abstract

Traditional models of hedonic games often fail to reach stable coalition structures, leading to infinite "run-and-chase" cycles. This paper proposes a dynamic framework where agent preferences evolve based on the history of the formation process. By introducing models of "resentment"—where agents' utility for others decreases after being abandoned—and "appreciation"—where utility increases upon joining—the authors demonstrate that these behavioral shifts act as stabilizing forces. We provide a comprehensive analysis of convergence across various stability concepts, including Nash and Core stability, for Additively Separable and Modified Fractional Hedonic Games. Our results show that while resentment generally guarantees stability, appreciation is more volatile but can lead to faster convergence in specific settings.

Introduction

In the study of hedonic games, researchers analyze how agents partition themselves into coalitions based on preferences for their teammates. A persistent challenge in static models is the lack of stability, often resulting in "run-and-chase" cycles where agents perpetually switch groups. For instance, if agent A prefers to be alone but agent B prefers to be with A, a static model may never reach an equilibrium.

This research addresses this instability by incorporating history-dependent preferences. In the real world, social dynamics are not static; if an agent is repeatedly abandoned, they may develop resentment, while persistent inclusion may foster appreciation. This paper formalizes these behavioral dynamics to prove they can drive systems toward stable outcomes.

Modeling Dynamic Preferences

The authors extend cardinal hedonic games—specifically Additively Separable Hedonic Games (ASHGs) and Modified Fractional Hedonic Games (MFHGs)—by making utility functions time-dependent. Two primary models are explored:

  1. Resentment Model: When an agent leaves a coalition, the members they abandoned decrease their utility for that agent by a fixed amount.
  2. Appreciation Model: When an agent joins a coalition, the existing members increase their utility for that agent.

To generalize these findings, the authors propose an axiomatic framework including principles like Aversion to Enemies (utility improves when an "enemy" leaves) and Enemy Monotonicity.

Stability Concepts

The study evaluates convergence across five major stability notions: Nash Stability (NS), Individual Stability (IS), Contractual Nash Stability (CNS), Core Stability (CS), and Strict Core Stability (SCS). These concepts form a hierarchy of requirements for agent satisfaction and coalition robustness.

Hierarchy of the five stability concepts analyzed in the paper.

Key Results and Convergence Analysis

The core contribution of the paper is a "convergence map" detailing which behavioral models guarantee stability across different game types and stability concepts.

Summary of convergence results for ASHGs and MFHGs under resentment and appreciation models.

Key findings include:

  • Resentment as a Stabilizer: Resentment is a powerful force for stability. By lowering utilities for "leavers," it prunes the set of attractive coalitions, eventually forcing the system into a stable state. In MFHGs, this guarantee often requires "Individual Rationality" (IR), ensuring agents only join groups that improve their utility relative to being alone.
  • The Volatility of Appreciation: While appreciation can lead to faster convergence in simulations (averaging ~4,300 steps vs. ~60,000 for resentment), it is less reliable. It can fuel cycles in Core Stability scenarios by making new coalitions perpetually more attractive.
  • Computational Complexity: Even when stability is guaranteed, the authors prove that finding the shortest sequence of moves to reach an equilibrium is NP-hard.
  • Outcome Structure: Resentment tends to produce "degenerate" outcomes (many small or singleton coalitions), while appreciation leads to "hub" structures with one very large coalition.

Conclusion

By introducing simple, human-like behavioral shifts into coalition formation models, this paper provides a robust solution to the classic problem of instability in hedonic games. While resentment tends to produce smaller, fragmented coalitions and appreciation leads to large "hub" structures, both mechanisms offer pathways to equilibrium that static models lack. Future work may explore more complex psychological nuances, such as forgiveness or non-linear utility changes.

Summary updated

BibTeX
@inproceedings{boehmer2023causes,
  author = {Niclas Boehmer and Martin Bullinger and Anna Maria Kerkmann},
  title = {{Causes of Stability in Dynamic Coalition Formation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.1609/aaai.v37i5.25683},
}
Figure