Find in Library

We explore strong Nash equilibria in the max <i>k</i>-cut game on an undirected and unweighted graph with a set of <i>k</i> colors. Here, the vertices represent players, and the edges denote their relationships. Each player, <i>v</i>, selects a color as its strategy, and its payoff (or utility) is determined by the number of neighbors of <i>v</i> who have chosen a different color. Limited findings exist on the existence of strong equilibria in max <i>k</i>-cut games. In this paper, we make advancements in understanding the characteristics of strong equilibria. Specifically, our primary result demonstrates that optimal solutions are seven-robust equilibria. This implies that for a coalition of vertices to deviate and shift the system to a different configuration, i.e., a different coloring, a number of coalition vertices greater than seven is necessary. Then, we establish some properties of the minimal subsets concerning a robust deviation, revealing that each vertex within these subsets will deviate toward the color of one of its neighbors.