Nash equilibria in Voronoi games on graphs
ESA'07: Proceedings of the 15th annual European conference on Algorithms(2007)
摘要
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.
更多查看译文
关键词
Nash Equilibrium, Social Cost, Delaunay Triangulation, Voronoi Cell, Pure Nash Equilibrium
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要