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.

Madeo, D., Mocenni, C., Palma, G., Rinaldi, S. (2022). A Game Theory Proof of Optimal Colorings Resilience to Strong Deviations. MATHEMATICS, 10(15) [10.3390/math10152781].

A Game Theory Proof of Optimal Colorings Resilience to Strong Deviations

Mocenni, C;Palma, G;Rinaldi, S
2022-01-01

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.
2022
Madeo, D., Mocenni, C., Palma, G., Rinaldi, S. (2022). A Game Theory Proof of Optimal Colorings Resilience to Strong Deviations. MATHEMATICS, 10(15) [10.3390/math10152781].
File in questo prodotto:
File Dimensione Formato  
mathematics-10-02781.pdf

accesso aperto

Tipologia: PDF editoriale
Licenza: Creative commons
Dimensione 918.21 kB
Formato Adobe PDF
918.21 kB 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/1227899