Optimal Coloring Strategies for the Max k -Cut Game

Andrea Garuglieri, Dario Madeo, Chiara Mocenni (), Giulia Palma and Simone Rinaldi
Additional contact information
Andrea Garuglieri: Department of Information Engineering and Mathematics, University of Siena, Via Roma 56, 53100 Siena, Italy
Dario Madeo: Department of Information Engineering and Mathematics, University of Siena, Via Roma 56, 53100 Siena, Italy
Chiara Mocenni: Department of Information Engineering and Mathematics, University of Siena, Via Roma 56, 53100 Siena, Italy
Giulia Palma: Department of Information Engineering and Mathematics, University of Siena, Via Roma 56, 53100 Siena, Italy
Simone Rinaldi: Department of Information Engineering and Mathematics, University of Siena, Via Roma 56, 53100 Siena, Italy

Mathematics, 2024, vol. 12, issue 4, 1-15

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.

Keywords: max k -cut problem; game theory; optimal colorings; coalitions; Nash equilibrium (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/4/604/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/4/604/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:4:p:604-:d:1340883

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().