Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.04948
curl -X POST /api/v1/records/arxiv/2610.04948/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.04948/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'