Research map / Graph learning / Graph algorithms and clustering
Individually Stable Dynamics in Coalition Formation over Graphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies whether individual-stability (IS) deviation dynamics in graph hedonic games converge across preference classes (general, IR, monotone, LAS) and acyclic topologies (paths, stars, trees), giving convergence results and cycling counterexamples.
Problem
Convergence of decentralized individual stability (IS) dynamics in coalition formation games over graphs, where feasible coalitions must be connected subgraphs; the question is which preference classes and graph topologies guarantee that better-response deviations always reach an IS partition.
Approach
Identifies the most general preference classes (monotone, IR, LAS) and acyclic topologies (paths, stars, trees) under which IS dynamics always converge, using potential/monotonicity-style arguments and a labeling scheme for trees, and gives cycling examples otherwise.
Key results
- IS dynamics always converge on paths under monotone preferences (theorem); on paths with IR preferences they converge when starting from at most three coalitions, but may cycle with four coalitions.
- On stars, IR preferences (or IR initial state with general preferences) give convergence in O(n^2) deviations.
- Under LAS preferences on trees, IS dynamics always converge; an exponential number of deviations may be needed in trees, and Omega(n^2) on paths.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use monotone preferences on a path | IS dynamics in graph hedonic games · Paths | convergence | Helped |
| Use individually rational preferences and start with at most three coalitions | IS dynamics in graph hedonic games · Paths | convergence | Helped |
| Start with at most three coalitions rather than an unrestricted initial partition | IS dynamics with individually rational preferences · Paths | convergence | Helped |
| Use individually rational preferences | IS dynamics in graph hedonic games · Stars | convergence: O(n^2) | Helped |
| Start from an individually rational state | IS dynamics with general preferences · Stars | convergence: O(n^2) | Helped |
| Use LAS preferences | IS dynamics in graph hedonic games · Trees | convergence: exponential number of deviations | Helped |
| Use LAS preferences | IS dynamics in graph hedonic games · Paths | convergence time: 2n^2; Ω(n^2) | Mixed |
| Use LAS preferences | IS dynamics in graph hedonic games · Stars | convergence: O(n^2) | Helped |
| Use LAS preferences on a graph containing a cycle | IS dynamics in graph hedonic games · Graphs with cycles | convergence | Hurt |
| Use general preferences | IS dynamics in graph hedonic games · Paths | convergence | Hurt |
| Use general preferences | IS dynamics in graph hedonic games · Stars | convergence | Hurt |
| Use individually rational preferences without restricting the initial partition | IS dynamics in graph hedonic games · Paths | convergence | Hurt |
Surprising findings
- IS dynamics can cycle even with LAS preferences when the graph contains a cycle, including a 3-vertex cycle.
- Under monotone preferences on trees, IS dynamics may cycle, so tree convergence needs the stronger LAS assumption.
Limitations
- Convergence is not guaranteed for general preferences on paths and stars, nor for cycles or for monotone preferences on trees.
- Upper bounds on convergence steps remain open for some monotone path and IR path cases.
- Results are purely theoretical with no computational experiments.
Experimental setup
Builds on: graph hedonic games individual stability additively separable preferences
Closest papers by meaning
- Reaching Individually Stable Coalition Structures in Hedonic Games (AAAI 2021 · similarity 0.90)
- Stability in Online Coalition Formation (AAAI 2024 · similarity 0.89)
- Forming Probably Stable Communities with Limited Interactions (AAAI 2019 · similarity 0.89)
- On Pareto Optimality in Social Distance Games (AAAI 2017 · similarity 0.89)
- Nash Stability in Social Distance Games (AAAI 2017 · similarity 0.88)
- Graphical Hedonic Games of Bounded Treewidth (AAAI 2016 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.