Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games
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≥3 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.
Related
- Stability, discretization, and optimality of continuous-time causal optimal transport
- A Riemannian Extension of a Quadrature Surface Free Boundary Problem: Stability and Optimality
- Policy iteration with discounted cost: near-optimality bounds and stability guarantees ⋆
- Additive mappings of unweighted directed graphs preserving individual values of the cycle length
- Improvement of the dimension bound for unweighted RCD spaces
BibTeX
@misc{gogoi2026social,
title = {{Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games}},
author = {Hritiz Gogoi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04948},
eprint = {2610.04948},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04948},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games
AU - Hritiz Gogoi
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.04948
UR - https://arxiv.org/abs/2610.04948
AB - 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≥3 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.
ER -