Digraph k-Coloring Games: New Algorithms and Experiments

We study digraph k-coloring games where strategic agents are vertices of a digraph and arcs represent agents’ mutual unidirectional conflicts/idiosyncrasies. Each agent can select, as strategy, one of k different colors, and her payoff in a given state (a k-coloring) is given by the number of outgoing neighbors with a color different from her one. Such games model lots of strategic real-world scenarios and are related to several fundamental classes of anti-coordination games. Unfortunately, the problem of understanding whether an instance of the game admits a pure Nash equilibrium (NE), i.e., a state where no agent can improve her payoff by changing strategy, is NP-complete. Thus, in this paper, we focus on algorithms to compute an approximate NE: informally, a coloring is an approximate γ-NE, for some γ ≥ 1, if no agent can improve her payoff, by changing strategy, by a multiplicative factor of γ. Our contribution is manifold and of both theoretical and experimental nature. First, we characterize the hardness of finding pure and approximate equilibria in both general and special classes of digraphs. Second, we design and analyze three approximation algorithms with different theoretical guarantees on the approximation ratio, under different conditions; (i) algorithm approx-1 which computes, for any k ≥ 3, a ∆o-NE for any n vertex graph having a maximum outdegree of ∆o, in polynomial time; (ii) algorithm lll-spe, a ran- domized algorithm that, for any constant k ≥ 2, determines a γ-NE for some constant γ but only in digraphs whose minimum outdegree is sufficiently large, in polynomial time in expectation; (iii) algorithm approx-3 which, for any ε > 0, computes a (1+ε)-NE by using O( log n ) colors, for any n-vertex digraph. Note that, the latter shows that a (1 + ε)-NE ε exists and can be computed in polynomial time for k = O(log n).