The One-Round Multi-player Discrete Voronoi Game on Grids and Trees

摘要

Basing on the two-player Voronoi game introduced by Ahn et al. [1] and the multi-player diffusion game introduced by Alon et al. [2] on grids, we investigate the following one-round multi-player discrete Voronoi game on grids and trees. There are n players playing this game on a graph G = (V,E). Each player chooses an initial vertex from the vertex set of the graph and tries to maximize the size of the nearest vertex set. As the main result, we give sufficient conditions for the existenceon-existence of pure Nash equilibrium in 4-player Voronoi game on grids and only a constant gap leaves unknown. We further consider this game with more than 4 players and construct a family of strategy profiles, which are pure Nash equilibrium on sufficiently narrow graphs. Besides, we investigate the game with 3 players on trees and design a linear time/space algorithm to decide the existence of a pure Nash equilibrium.