Network Coloring and Colored Coin Games - Search Theory: A Game Theoretic Perspective - page 56

Chapter 4
Network Coloring and Colored Coin Games

Christos Pelekis and Moritz Schauer

Abstract Kearns et al. introduced the Graph Coloring Problem to model dynamic
conflict resolution in social networks. Players, represented by the nodes of a graph,
consecutively update their color from a fixed set of colors with the prospect of finally
choosing a color that differs from all neighbors choices. The players only react
on local information (the colors of their neighbors) and do not communicate. The
reader might think of radio stations searching for transmission frequencies which
are not subject to interference from other stations. While Kearns et al. (see [ 10 ])
empirically examined how human players deal with such a situation, Chaudury et
al. performed a theoretical study and showed that, under a simple, greedy and selfish

strategy, the players find a proper coloring of the graph within time O log n
δ

with probability ≥ 1 − δ ,where n is the number of nodes in the network and δ is

arbitrarily small. In other words, the graph is properly colored within τ steps and

with high probability for some constant c . Previous estimates on the
constant c are very large. In this chapter we substantially improve the analysis and
upper time bound for the proper coloring, by combining ideas from search games
and probability theory.

c log n
δ

τ <

4.1 Notation and Definitions

=( , )

The network coloring game is a stochastic process evolving on a graph, G V E ,

on n vertices and maximum degree . Each vertex is thought of as a player that has k

available colors. Each player has the same set of colors. As in [ 2 ] we assume that k

Δ

≥

Δ + 2. The game is played in rounds and in each round all players simultaneously

and individually choose a color. They can only observe the colors chosen by their