A Game Theory Proof of Optimal Colorings Resilience to Strong Deviations

Abstract

This paper provides a formal proof of the conjecture stating that optimal colorings in max k-cut games over unweighted and undirected graphs do not allow the formation of any strongly divergent coalition, i.e., a subset of nodes able to increase their own payoffs simultaneously. The result is obtained by means of a new method grounded on game theory, which consists in splitting the nodes of the graph into three subsets: the coalition itself, the coalition boundary and the nodes without relationship with the coalition. Moreover, we find additional results concerning the properties of optimal colorings.

Keywords

• max <i>k</i>-cut problem
• game theory
• optimal colorings
• coalitions
• Nash equilibrium