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.

Coalition resilient outcomes in max k-cut games

Monaco, Gianpiero
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.
9783030108007
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/11697/133474
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 3
social impact