We investigate strong Nash equilibria in the max k-cut game, where we are given an undirected edge-weighted graph together with a set {1,…,k} of k colors. Nodes represent players and edges capture their mutual interests. The strategy set of each player v consists of the k colors. When players select a color they induce a k-coloring or simply a coloring. Given a coloring, the utility (or payoff) of a player u is the sum of the weights of the edges {u,v} incident to u, such that the color chosen by u is different from the one chosen by v. Such games form some of the basic payoff structures in game theory, model lots of real-world scenarios with selfish agents and extend or are related to several fundamental classes of games. Very little is known about the existence of strong equilibria in max k-cut games. In this paper we make some steps forward in the comprehension of it. We first show that improving deviations performed by minimal coalitions can cycle, and thus answering negatively the open problem proposed in [13]. Next, we turn our attention to unweighted graphs. We first show that any optimal coloring is a 5-SE in this case. Then, we introduce x-local strong equilibria, namely colorings that are resilient to deviations by coalitions such that the maximum distance between every pair of nodes in the coalition is at most x. We prove that 1-local strong equilibria always exist. Finally, we show the existence of strong Nash equilibria in several interesting specific scenarios.

Carosi, R., Fioravanti, S., Gualà, L., Monaco, G. (2019). Coalition Resilient Outcomes in Max k-Cut Games. In SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science 11376 (pp.94-107). Springer [10.1007/978-3-030-10801-4_9].

Coalition Resilient Outcomes in Max k-Cut Games

Gualà, Luciano;
2019-01-01

Abstract

We investigate strong Nash equilibria in the max k-cut game, where we are given an undirected edge-weighted graph together with a set {1,…,k} of k colors. Nodes represent players and edges capture their mutual interests. The strategy set of each player v consists of the k colors. When players select a color they induce a k-coloring or simply a coloring. Given a coloring, the utility (or payoff) of a player u is the sum of the weights of the edges {u,v} incident to u, such that the color chosen by u is different from the one chosen by v. Such games form some of the basic payoff structures in game theory, model lots of real-world scenarios with selfish agents and extend or are related to several fundamental classes of games. Very little is known about the existence of strong equilibria in max k-cut games. In this paper we make some steps forward in the comprehension of it. We first show that improving deviations performed by minimal coalitions can cycle, and thus answering negatively the open problem proposed in [13]. Next, we turn our attention to unweighted graphs. We first show that any optimal coloring is a 5-SE in this case. Then, we introduce x-local strong equilibria, namely colorings that are resilient to deviations by coalitions such that the maximum distance between every pair of nodes in the coalition is at most x. We prove that 1-local strong equilibria always exist. Finally, we show the existence of strong Nash equilibria in several interesting specific scenarios.
SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science
Rilevanza internazionale
contributo
2019
Settore INF/01 - INFORMATICA
English
Intervento a convegno
Carosi, R., Fioravanti, S., Gualà, L., Monaco, G. (2019). Coalition Resilient Outcomes in Max k-Cut Games. In SOFSEM 2019: Theory and Practice of Computer Science - 45th International Conference on Current Trends in Theory and Practice of Computer Science, Proceedings. Lecture Notes in Computer Science 11376 (pp.94-107). Springer [10.1007/978-3-030-10801-4_9].
Carosi, R; Fioravanti, S; Gualà, L; Monaco, G
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/2108/213239
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? ND
social impact