A Game Theory Proof of Optimal Colorings Resilience to Strong Deviations

Dario Madeo, Chiara Mocenni (), Giulia Palma and Simone Rinaldi
Additional contact information
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, 2022, vol. 10, issue 15, 1-14

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 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: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/15/2781/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/15/2781/ (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:10:y:2022:i:15:p:2781-:d:881365

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 ().