Computing Approximate Pure Nash Equilibria in Digraph k-Coloring Games

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ász 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 , δ v o (G) = Ω(ln ∆o(G)+ln ∆i(G)) where ∆o(G) (resp. ∆i(G)) is the maximum outgoing (resp. maximum ingoing) degree of G, and δ v o (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.