The Max k-Cut Game: On Stable Optimal Colorings

06/09/2020
by   Chiara Mocenni, et al.
0

We study the max k-cut game on an undirected and unweighted graph in order to find out whether an optimal solution is also a strong equilibrium. While we do fail to show that, by proving an alternate formula for computing the cut value difference for a strong deviation, we show that optimal solutions are 7-stable equilibria. Furthermore, we prove some properties of minimal subsets with respect to a strong deviation, showing that each of their nodes will deviate towards the color of one of their neighbors and that those subsets induce connected subgraphs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset