Nash equilibria in Voronoi games on graphs

Details Nash equilibria in Voronoi games on graphs Nash equilibria in Voronoi games on graphs

2007-02-09

arxiv.org/abs/cs/0702054v2

Computer Science

Computer Science and Game Theory

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Nash equilibria in Voronoi games on graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nash equilibria in Voronoi games on graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nash equilibria in Voronoi games on graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-8124