<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>We investigate strong Nash equilibria in the max <italic>k</italic>-cut game on an undirected and unweighted graph with a set of <italic>k</italic> colors, where vertices represent players and the edges indicate their relations. Each player <italic>v</italic> chooses one of the available colors as its own strategy, and its payoff (or utility) is the number of neighbors of <italic>v</italic> that has chosen a different color. Such games are significant since they model loads of real-worlds scenario with selfish agents and, moreover, they are related to fundamental classes of games. Few results are known concerning the existence of strong equilibria in max <italic>k</italic>-cut games in this direction. In this paper we make some progress in the understanding of the properties of strong equilibria. In particular, our main result is to show that optimal solutions are 7-strong equilibria. This means that in order a coalition of nodes is able to deviate and drive the system towards a different configuration, i.e. a different coloring, a number of nodes of the coalition strictly larger than 7 is necessary. We also conjecture that, in a generic graph with <italic>n</italic> nodes, any optimal coloring is also an <italic>n</italic>-strong equilibrium.</p>
</abstract>

We investigate strong Nash equilibria in the max k-cut game on an undirected and unweighted graph with a set of k colors, where vertices represent players and the edges indicate their relations. Each player v chooses one of the available colors as its own strategy, and its payoff (or utility) is the number of neighbors of v that has chosen a different color. Such games are significant since they model loads of real-worlds scenario with selfish agents and, moreover, they are related to fundamental classes of games. Few results are known concerning the existence of strong equilibria in max k-cut games in this direction. In this paper we make some progress in the understanding of the properties of strong equilibria. In particular, our main result is to show that optimal solutions are 7-strong equilibria. This means that in order a coalition of nodes is able to deviate and drive the system towards a different configuration, i.e. a different coloring, a number of nodes of the coalition strictly larger than 7 is necessary. We also conjecture that, in a generic graph with n nodes, any optimal coloring is also an n-strong equilibrium.

Optimal colorings of Max <italic>k</italic>-Cut game

Department of Information Engineering and Mathematics

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":{"italic":"k","content":["Optimal colorings of Max","-Cut game"]}}

We investigate strong Nash equilibria in the max k-cut game on an undirected and unweighted graph with a set of k colors, where vertices represent players and...

Optimal colorings of Max k-Cut game

Published Online: Jun 18, 2022

Page range: 82 - 89

Received: Mar 31, 2022

Accepted: May 15, 2022

DOI: https://doi.org/10.2478/puma-2022-0013

© 2022 Dario Madeo et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.