Utilitarian Welfare Optimization in the Generalized Vertex Coloring Games: An Implication to Venue Selection in Events Planning

arXiv2206.09153MaRDI QIDQ6402452FDOQ6402452

Authors: Zeyi Chen 

Publication date: 18 June 2022

Abstract: 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(logn)$, 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.

This page was built for publication: Utilitarian Welfare Optimization in the Generalized Vertex Coloring Games: An Implication to Venue Selection in Events Planning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6402452)