Nash Equilibria in Reverse Temporal Voronoi Games

Abstract

We study Voronoi games on temporal graphs as introduced by Boehmer et al. (IJCAI '21) where two players each select a vertex in a temporal graph with the goal of reaching the other vertices earlier than the other player. In this work, we consider the reverse temporal Voronoi game, that is, a player wants to maximize the number of vertices reaching her earlier than the other player.

Since temporal distances in temporal graphs are not symmetric in general, this yields a different game.

We investigate the difference between the two games with respect to the existence of Nash equilibria in various temporal graph classes including temporal trees, cycles, grids, cliques and split graphs. Our extensive results show that the two games indeed behave quite differently depending on the considered temporal graph class.