Digraph k-Coloring Games: New Algorithms and Experiments

Abstract

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 randomized 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 ε, 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)).

Finally, to assess how proposed algorithms behave in the typical case, we complete our study with an extensive experimental evaluation showing that, while newly introduced algorithms achieve bounded worst case behavior, they generally perform poorly in practice. Motivated by such unsatisfactory performance, we shift our attention to the best-response paradigm, successfully applied to other classes of games, and design and experimentally evaluate it a heuristic based on such paradigm. Our experiments provide strong evidences of such approach outperforming, in terms of approximation and computational time, all other methods and hence identify it as the most suited candidate for practical usage. More remarkably, it is also able to compute exact, pure NE in the great majority of cases. This suggests that, while these games are known to not always possess a pure NE, such an equilibrium often exists and can be efficiently computed, even by a distributed uncoordinated interaction of the agents.