Discrete Applied Mathematics 244 (2018), 1-19.
Pure-strategy Nash equilibria on competitive diffusion games
by Hikoe Enomoto, Masahiro Hachimori, Shun Nakamura, Maiko Shigeno, Yuya Tanaka, Masaaki Tsugami
Abstract
This paper treats two types of competitive facility location games on graphs: information diffusion
games and discrete Voronoi games. Both of these games can be regarded as models of the rumor spreading
processes on the networks, where each player of the game wants to select an influencer who can widely
spread information throughout the network. For each game, given a graph and the number of players,
we are interested in whether there exist pure Nash equilibria or not. In this paper, we discuss the
existence of pure Nash equilibria on graphs with small diameter, path graphs, and cycle graphs.
The results include the behavior of the discrete Voronoi games on graphs with diameter two, and the
complete characterization of the existence of the pure Nash equilibria in the discrete Voronoi games
and information diffusion games on path graphs.