Distributed game-theoretic vertex coloring

We exploit the game-theoretic ideas presented in [12] to study the vertex coloring problem in a distributed setting. The vertices of the graph are seen as players in a suitably defined strategic game, where each player has to choose some color, and the payoff of a vertex is the total number of players that have chosen the same color as its own. We extend here the results of [12] by showing that, if any subset of non-neighboring vertices perform a selfish step (i.e., change their colors in order to increase their payoffs) in parallel, then a (Nash equilibrium) proper coloring, using a number of colors within several known upper bounds on the chromatic number, can still be reached in polynomial time. We also present an implementation of the distributed algorithm in wireless networks of tiny devices and evaluate the performance in simulated and experimental environments. The performance analysis indicates that it is the first practically implementable distributed algorithm. © 2010 Springer-Verlag.