Best Response Digraphs for Two Location Games on Graphs

We investigate two classes of location games on undirected graphs, where two players simultaneously place one facility each on a vertex. In the first class, called ‘Voronoi games’, the payoff for a player is the number of vertices closer to that player's facility than to the other one, plus half of the number of vertices with equal distance. For the other class, called ‘restaurant location games’, the payoff for a player equals 1 plus $\kappa$ times the number of private neighbors plus $\kappa /2$ times the number of common neighbors, if both locations are different, and 1/2 plus $\kappa /2$ times the number of common neighbors provided both locations are identical, for some constant $\kappa$. For both classes the question of the existence of pure Nash equilibria is investigated. Although Voronoi games, which are obviously constant-sum games, do not need to have pure Nash equilibria, Nash equilibria exist if the play graphs are trees. Restaurant location games have always at least one pure Nash equilibrium. We also try to express these Nash equilibria in graph-theoretical terms, and investigate the structure of so-called best response digraphs for the games in relation to the structure of the underlying play graph.