Markov Chain Approaches to Payoff Optimization in the Self-Organizing Network Coloring Game

The model of Network Coloring Game (NCG) is used to simulate conflict resolving and consensus reaching procedures in social science. In this work, we adopted some Markov Chain Techniques into the investigation of NCG. Firstly, with no less than $\Delta + 2$ colors provided, we proposed and proved that the conflict resolving time has its expectation to be $O(\log n)$ and the variance $O((\log n)^2)$, thus is $O_p(\log n)$, where $n$ is the number of vertices and $\Delta$ is the maximum degree of the network. This was done by introducing an absorbing Markov Chain into NCG. Secondly, we developed an algorithms to reduce the network in post-conflict-resolution adjustments when a Borda rule is applied among players. Markov Chain Monte Carlo methods were employed to estimate both local and global optimal payoffs. Supporting experimental results were given to illustrate the corresponding procedures.