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 gamma-Nash equilibrium (for some gamma >= 1) if no agent can strictly improve her payoff by a multiplicative factor of gamma by changing color. We first propose a deterministic polynomial time algorithm that, for any k >= 3, returns a k-coloring that is a Delta(o) (G)-Nash equilibrium, where Delta(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 Lovasz 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 2 V, delta(v)(0) (G) = Omega(ln Delta(o) (G) ln Delta(i) (G)) where Delta(o) (G) (resp. Delta(i) (G)) is the maximum outgoing (resp. maximum ingoing) degree of G, and delta(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+epsilon)-Nash equilibrium, for any epsilon > 0, by using O(log n/epsilon) colors.