On the Performance of Mildly Greedy Players in k-Coloring Games

We study the performance of mildly greedy players in k-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than ϵ, for some given ϵ ≥ 0. In presence of mildly greedy players, stability is captured by the concept of (1 +ϵ)-approximate Nash equilibrium. In this paper, we first show that, for any k-coloring game, the (1 + ϵ)-approximate price of anarchy, i.e., the price of anarchy of (1 + ϵ)-approximate pure Nash equilibria, is at least k−1(k−1)ϵ+k, and that this bound is tight for any ϵ ≥ 0. Then, we evaluate the approximation ratio of the solutions achieved after a (1 + ϵ)-approximate one-round walk starting from any initial strategy profile, where a (1 + ϵ)-approximate one-round walk is a sequence of (1 + ϵ)-approximate best-responses, one for each player. We provide a lower bound of minn k−2 k,k−1(k−1)ϵ+ko on this ratio, for any ϵ ≥ 0 and k ≥ 5; for the cases of k = 3 and k = 4, we give finer bounds depending on ϵ. Our work generalizes the results known for cut games, the special case of k-coloring games restricted to k = 2.