Voronoi games on cycle graphs
Ημερομηνία
2008ISSN
0302-9743Source
33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008Volume
5162 LNCSPages
503-514Google Scholar check
Keyword(s):
Metadata
Εμφάνιση πλήρους εγγραφήςΕπιτομή
In a Voronoi game, each of a finite number of players chooses a point in some metric space. The utility of a player is the total measure of all points that are closer to him than to any other player, where points equidistant to several players are split up evenly among the closest players. In a recent paper, Dürr and Thang (2007) considered discrete Voronoi games on graphs, with a particular focus on pure Nash equilibria. They also looked at Voronoi games on cycle graphs with n nodes and k players. In this paper, we prove a new characterization of all Nash equilibria for these games. We then use this result to establish that Nash equilibria exist if and only if or k ≤ 2n/3 or k ≥ n. Finally, we give exact bounds of 9/4and 1 for the prices of anarchy and stability, respectively. © 2008 Springer-Verlag Berlin Heidelberg.