Individually Stable Dynamics in Coalition Formation over Graphs

Angelo Fanelli, Laurent Gourvès, Ayumi Igarashi, Luca MoscardelliAAAI 2025 · DOI

TL;DR

This paper investigates the convergence of decentralized coalition formation processes in graph-based games. It explores how different player preferences and network structures (graphs) influence whether these dynamics will eventually settle into a stable state, providing a comprehensive analysis of convergence guarantees.

What Problem Does This Paper Address?

Coalition formation, where individuals group together to achieve common goals, is a fundamental concept in economics and AI. In many real-world scenarios, these groups are constrained by network structures – people can only easily collaborate with those they are connected to. This paper focuses on "graph hedonic games," where players are nodes in a graph, and feasible coalitions must be connected subgraphs.

A key aspect of these games is "individual stability" (IS), a notion of equilibrium where no single player can unilaterally improve their situation by switching to a new coalition, provided the other members of that coalition agree. While the existence of such stable states is often guaranteed, the process by which players reach them is less understood. This paper tackles the question: if players iteratively make individually stable moves, will they always reach a stable outcome, or could they get stuck in endless cycles? They explore this by examining how different types of player preferences (from general to more restricted ones like "individually rational" and "monotone") and different graph structures (paths, stars, trees) affect convergence.

Methods

The core of the paper is an analysis of "IS dynamics," a sequential process where players make "individually stable deviations." An IS deviation involves a player moving to a new coalition if they prefer it and if all members of the target coalition accept them. The paper defines this process formally and then systematically analyzes its convergence properties under various conditions.

Key methodological contributions include:

  • Hierarchical Preference Analysis: The authors categorize player preferences into a hierarchy: General, Individually Rational (IR), Monotone, and Local Additively Separable (LAS). This allows them to pinpoint which preference types are necessary for convergence on different graph structures.
  • Graph Topology Analysis: They focus on specific graph structures: paths, stars, and trees, which are common in network settings.
  • Proof Techniques: For proving convergence, they often employ proof by contradiction, assuming a cycle exists and deriving a contradiction based on the properties of the dynamics, preferences, and graph structure. For example, in proving convergence on paths with monotone preferences, they use an inductive argument on the structure of potential cycles.
  • Counterexamples: To demonstrate when convergence is not guaranteed, they construct specific examples of graph hedonic games with particular preference profiles and initial states that lead to cyclic dynamics.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses constructed examples rather than real-world datasets.

Key Insights and Ideas

  • Topology Matters Greatly: Convergence is highly dependent on the graph structure. Simple structures like stars and paths offer more guarantees than general graphs with cycles.
  • Preferences are Crucial: Even on simple graphs, convergence can fail if preferences are too general. More restrictive preferences (like monotone or LAS) are often needed to ensure stability.
  • Cycles are the Enemy of Convergence: The primary obstacle to convergence is the possibility of players entering into endless loops of deviations. The paper identifies specific conditions (e.g., cycles in the graph with LAS preferences) that can lead to these loops.
  • Individual Rationality is a Strong Guarantee: For certain graph structures (like stars), even general preferences can lead to convergence if the initial state is "individually rational" (meaning players are not worse off in any coalition than being alone).
  • Monotone Preferences are Powerful on Paths: The paper shows that for path graphs, monotone preferences are sufficient to guarantee convergence of IS dynamics.
  • LAS Preferences are Necessary for Trees: For the more complex structure of trees, Local Additively Separable (LAS) preferences are required to guarantee convergence.

Key Results

The paper presents a detailed overview of convergence results in Table 1, summarizing findings across different preference types and graph topologies:

  • General Preferences: Convergence is not guaranteed even on basic structures like paths and stars.
  • Individually Rational (IR) Preferences: Convergence is guaranteed on stars and paths (with a caveat for paths: it's guaranteed if the initial partition has at most 3 coalitions).
  • Monotone Preferences: Convergence is guaranteed on paths.
  • Local Additively Separable (LAS) Preferences: Convergence is guaranteed on trees. However, even LAS preferences do not guarantee convergence on graphs with cycles.

The paper also provides bounds on the number of steps for convergence in some cases, often showing it to be polynomial (e.g., O(n²) for stars with IR preferences), but also highlights that exponential steps might be needed in some tree scenarios.

Limitations and Future Work

  • Open Questions on Bounds: For some cases where convergence is guaranteed (e.g., monotone preferences on paths, IR preferences on paths with ≤3 coalitions), the paper proves convergence but leaves the exact worst-case bounds on the number of steps open.
  • Best Responses vs. Better Responses: The current analysis focuses on "better responses" (players making any individually stable move). The authors conjecture that using "best responses" (players always choosing their most preferred stable move) might lead to significantly faster convergence.
  • Reconfiguration Schemes: The paper assumes a specific way for remaining coalition members to reconfigure after a player leaves. Exploring alternative reconfiguration schemes could be an interesting avenue.
  • Complexity of Deciding Convergence: For instances where convergence is not always guaranteed, determining whether a specific instance and initial state will converge is a challenging computational problem that remains open.
  • Other Deviation Notions: The study is limited to IS deviations. Investigating convergence for other types of deviations (e.g., Nash deviations, or variations of IS) is a natural extension.

Summary updated

BibTeX
@inproceedings{fanelli2025individually,
  author = {Angelo Fanelli and Laurent Gourvès and Ayumi Igarashi and Luca Moscardelli},
  title = {{Individually Stable Dynamics in Coalition Formation over Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i13.33512},
}
Figure