On Dynamics of Basic Network Creation Games with Non-Uniform Communication Interest

We consider network construction process by selfish players. Each player is associated to a vertex of a communication graph and can simultaneously remove one incident edge and add a new incident edge. Each player is interested in a subset of players and the goal of each player is to minimize the average or maximum distance to these players. Starting from a given initial communication graph, a sequence of selfish edge swaps generates an evolution of the communication graph. Due to non-uniform communication interest, this game may converge to a disconnected Nash equilibrium, which attains infinite social cost. In this paper, we focus on the dynamics of this game. We first give theoretical analysis such as the existence of a best response cycle and a sufficient condition on an initial communication graph so that it keeps connectivity in its dynamics. We then present simulation results to show the ratio of disconnected Nash equilibria, the social cost, and convergence time.