The story of the month
Optimal Graph Cuts Can Collapse Under Group Collusion
Imagine players coloring vertices in a network to disagree with neighbors. When edges between differently colored vertices earn rewards, colorings maximizing cut achieve greatest welfare. While some optimal colorings were known unstable, researchers asked whether every network admits an optimal coloring resisting colluding teams.
The answer is no. A 182-vertex network shows an unweighted cut game can fail to admit any optimal strong equilibrium.
In this network, every coloring achieving maximum social welfare allows a coalition to switch colors together, strictly improving each member's payoff.