We explore strong Nash equilibria in the max k-cut game on an undirected and unweighted graph with a set of k colors. Here, the vertices represent players, and the edges denote their relationships. Each player, v, selects a color as its strategy, and its payoff (or utility) is determined by the number of neighbors of v who have chosen a different color. Limited findings exist on the existence of strong equilibria in max k-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.

Garuglieri, A., Madeo, D., Mocenni, C., Palma, G., Rinaldi, S. (2024). Optimal Coloring Strategies for the Max k-Cut Game. MATHEMATICS, 12(4) [10.3390/math12040604].

Optimal Coloring Strategies for the Max k-Cut Game

Madeo D.;Mocenni C.
;
Palma G.;Rinaldi S.
2024-01-01

Abstract

We explore strong Nash equilibria in the max k-cut game on an undirected and unweighted graph with a set of k colors. Here, the vertices represent players, and the edges denote their relationships. Each player, v, selects a color as its strategy, and its payoff (or utility) is determined by the number of neighbors of v who have chosen a different color. Limited findings exist on the existence of strong equilibria in max k-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.
2024
Garuglieri, A., Madeo, D., Mocenni, C., Palma, G., Rinaldi, S. (2024). Optimal Coloring Strategies for the Max k-Cut Game. MATHEMATICS, 12(4) [10.3390/math12040604].
File in questo prodotto:
File Dimensione Formato  
mathematics-12-00604.pdf

accesso aperto

Tipologia: PDF editoriale
Licenza: Creative commons
Dimensione 1.67 MB
Formato Adobe PDF
1.67 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1280255