Price of anarchy for graph coloring games with concave payoff

We study the price of anarchy in graph coloring games (a subclass of polymatrix common-payoff games). Players are vertices of an undirected graph, and the strategies for each player are the colors $\left\{ {1, \ldots ,k} \right\}$ . A tight bound of $\frac{k}{k-1}$ is known (Hoefer 2007, Kun et al. 2013), if each player's payoff is the number of neighbors with different color than herself.

In our generalization, payoff is computed by determining the distance of the player's color to the color of each neighbor, applying a concave function $f$ to each distance, and then summing up the resulting values. This is motivated, e. g., by spectrum sharing, and includes the payoff functions suggested by Kun et al. (2013) for future work as special cases.

Denote $f^*$ the maximum value that $f$ attains on $\left\{ {0, \ldots ,k - 1} \right\}$ . We prove an upper bound of $2$ on the price of anarchy if $f$ is non-decreasing or assumes $f^*$ somewhere in $\left\{ {0, \ldots ,{\frac{k}{2}}} \right\}$ . Matching lower bounds are given for the monotone case and if $f^*$ is assumed in $\frac{k}{2}$ for even $k$ . For general concave $f$ , we prove an upper bound of $3$ . We use a new technique that works by an appropriate splitting $\lambda = \lambda_1 + \ldots + \lambda_k$ of the bound $\lambda$ we are proving.