Voronoi game on graphs and its complexity

Abstract. The Voronoi game is a two-person game which is a model for a competitive facility location. The game is done on a continuous domain, and only two special cases (1-dimensional case and 1-round case) are well investigated. We introduce the discrete Voronoi game of which the game arena is given as a graph. We first show the best strategy when the game arena is a large complete k-ary tree. Next we show that the discrete Voronoi game is intractable in general. Even in 1-round case, and the place occupied by the first player is fixed, the game is NP-complete in general. We also show that the game is PSPACE-complete in general case. Key words: Voronoi Game, NP-completeness, PSPACE-completeness.