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á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.