We investigate approximate pure Nash equilibria in digraph k-coloring games, where we are given an unweighted directed graph together with a set of k colors. Vertices represent agents and arcs capture their mutual unidirectional interests. The strategy set of each agent v consists of the k colors and the payoff of v in a given state or coloring is given by the number of outgoing neighbors with a color different from the one of 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 class of games. It is known that the problem of understanding whether the game admits a pure Nash equilibrium is NP-complete. Therefore we focus on designing polynomial time algorithms that return approximate Nash equilibria. Informally, we say that a coloring is a λ-Nash equilibrium (for some λ ≥ 1) if no agent can strictly improve her payoff by a multiplicative factor of λ by changing color. We first propose a deterministic polynomial time algorithm that, for any k ≥ 3, returns a k-coloring that is a Δo(G)-Nash equilibrium, where Δo(G) is the maximum outdegree of the digraph. We then provide our two main results: i) By exploiting the constructive version of the well known Lováasz Local Lemma, we show a randomized algorithm with polynomial expected running time that, given any constant k ≥ 2, computes a constant-Nash equilibrium for a broad class of digraphs, i.e., for digraphs where, for any v ∈ V, δo/v(G) = Ω(ln Δo(G) + ln Δi(G)) where Δo(G) (resp. Δi(G)) is the maximum outgoing (resp. maximum ingoing) degree of G, and δo/v(G) is the outgoing degree of agent v. ii) For generic digraphs, we show a deterministic polynomial time algorithm that computes a (1+ε)-Nash equilibrium, for any ε > 0, by using O(log n/ε) colors.

Computing Approximate Pure Nash Equilibria in Digraph k-Coloring Games

FLAMMINI, MICHELE
;
MONACO, Gianpiero
2017

Abstract

We investigate approximate pure Nash equilibria in digraph k-coloring games, where we are given an unweighted directed graph together with a set of k colors. Vertices represent agents and arcs capture their mutual unidirectional interests. The strategy set of each agent v consists of the k colors and the payoff of v in a given state or coloring is given by the number of outgoing neighbors with a color different from the one of 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 class of games. It is known that the problem of understanding whether the game admits a pure Nash equilibrium is NP-complete. Therefore we focus on designing polynomial time algorithms that return approximate Nash equilibria. Informally, we say that a coloring is a λ-Nash equilibrium (for some λ ≥ 1) if no agent can strictly improve her payoff by a multiplicative factor of λ by changing color. We first propose a deterministic polynomial time algorithm that, for any k ≥ 3, returns a k-coloring that is a Δo(G)-Nash equilibrium, where Δo(G) is the maximum outdegree of the digraph. We then provide our two main results: i) By exploiting the constructive version of the well known Lováasz Local Lemma, we show a randomized algorithm with polynomial expected running time that, given any constant k ≥ 2, computes a constant-Nash equilibrium for a broad class of digraphs, i.e., for digraphs where, for any v ∈ V, δo/v(G) = Ω(ln Δo(G) + ln Δi(G)) where Δo(G) (resp. Δi(G)) is the maximum outgoing (resp. maximum ingoing) degree of G, and δo/v(G) is the outgoing degree of agent v. ii) For generic digraphs, we show a deterministic polynomial time algorithm that computes a (1+ε)-Nash equilibrium, for any ε > 0, by using O(log n/ε) colors.
978-151085507-6
File in questo prodotto:
File Dimensione Formato  
aamas 2017.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 349.15 kB
Formato Adobe PDF
349.15 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: http://hdl.handle.net/11697/111231
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 6
social impact