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

The model of Network Coloring Game (NCG) first proposed by Kearns et al. is used to simulate conflict resolving dynamics and consensus reaching procedures in social sciences. In NCG, individual's payoff depends on preference mechanism and is zero when a player shares the same color with someone in the neighborhood. The equilibrium is reached when nobody has incentives to continue choosing a different color. Applications of NCG include resource allocation \cite{Bampas:2013}, timetable scheduling \cite{Seo:2016}, etc., thus numerous literature devoted in estimating the convergence situation and optimizing social payoffs. In this work, we adopted some Markov Chain techniques to further research on NCG. Firstly, with no less than $\Delta + 2$ colors provided, we proposed and proved that the converging time is stochastically bounded by $O_p(\log n)$, through introducing an absorbing Markov Chain to approximate upper bounds for its expectation and variance, which is an improvement on Chaudhuri et al.'s result \cite{Chaudhuri:2008}. Here $n$ is the number of vertices and $\Delta$ is the maximum degree of the network. Secondly, as most literature ignores the dynamics after the conflict is solved, we focused on post-conflict adjustments among the players when a Borda preference mechanism is applied. Markov Chain Monte Carlo (MCMC) methods like Metropolis-Hasting Algorithm and Simulated Annealing Heuristic were employed to simulate payoff-optimizing behaviors and estimate both local and global optimal social welfare. Supporting experimental results were given to illustrate the corresponding procedures.