Socially best groupings can be unstable to coalitions in graph games
Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games
Computer Science and Game Theory
Summary
Max-k-Cut games involve coloring nodes in a network to maximize connections between different colors, which is good for everyone overall. It was believed that these best possible colorings are stable, meaning no group of players can switch colors together to all benefit at once. The paper shows that this is not always true for unweighted graphs when there are three or more colors. They provide examples where groups can jointly change colors to improve their own outcomes without improving the overall benefit, revealing a surprising weakness in group stability.
What this means in practice
- •For network designers: Design network segmentations knowing optimal partitions may be unstable to coordinated user changes.
- •For game theory programmers: Improve simulations of multi-agent systems by accounting for potential profitable group deviations in strategy assignments.
A theory result. No direct application yet.
Authors
Hritiz Gogoi
Abstract
In Max-$k$-Cut games, optimal colorings maximize social welfare, but are they stable against coordinated deviations that strictly benefit every participating player? A recurring conjecture in the literature asserts that, for unweighted graphs, every optimal coloring has this stability property, known as strong equilibrium. We disprove the conjecture for every $k\ge3$ by exhibiting a finite, simple, connected, unweighted graph with an optimal coloring that is not a strong equilibrium. The profitable coalitional deviation leads to another optimal coloring: every coalition member gains, while players outside the coalition bear the corresponding losses and social welfare remains unchanged. We also give an exact identity relating coalitional gains, changes in cut value, and internal conflicts, recovering the known stability guarantee for optimal colorings when the maximum degree is at most $2k-1$. For strong deviations from general Nash equilibria, we establish a sharp upper bound on the number of monochromatic edges remaining within the coalition and show that this number can exceed the coalition size.