{"id":"arxiv/2610.04948","url":"https://arxiv.org/abs/2610.04948","tags":["math.OC","cs.GT"],"score":0,"title":"Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games","domain":"math.OC","source":"arxiv","authors":["Hritiz Gogoi"],"reviews":0,"subject":"math.OC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-04","reactions":{}}