2007/02/09 by Christoph Dürr, Christoph Durr, Durr, Christoph +3 · 4 citations
Computer Science · Decision Sciences · Economics, Econometrics and Finance · Physics and Astronomy · #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #Opinion Dynamics and Social Influence #cs.DS #cs.GT
paper · pdf · doi:10.48550/arxiv.cs/0702054
openalex publication_date 2007/02/09 · arxiv created 2007/04/13 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.