  In this paper we study a game where every player is to choose a vertex
(facility) in a given undirected graph. All vertices (customers) are then
assigned to closest facilities and a player's payoff is the number of customers
assigned to it. We show that deciding the existence of a Nash equilibrium for a
given graph is NP-hard which to our knowledge is the first result of this kind
for a zero-sum game. We also introduce a new measure, the social cost
discrepancy, defined as the ratio of the costs between the worst and the best
Nash equilibria. We show that the social cost discrepancy in our game is
Omega(sqrt(n/k)) and O(sqrt(kn)), where n is the number of vertices and k the
number of players.
