2015/06/12 by S. Rasoul Etesami, Seyed Rasoul Etesami, Tamer Başar +3
Computer Science · Decision Sciences · Mathematics · #Combinatorics (math.CO) #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Multiagent Systems (cs.MA) #Optimization and Control (math.OC) #Peer-to-Peer Network Technologies #cs.DM #cs.GT #cs.MA #math.CO #math.OC
paper · pdf · doi:10.48550/arxiv.1506.04047
openalex publication_date 2015/06/12 · arxiv created 2016/03/11 · arxiv updated 2016/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We first show that such games have an associated ordinary potential function, and hence always admit a pure-strategy Nash equilibrium (NE). Further, when the minimum degree of the network and the number of resources are of the same order, there exists an exact polynomial time algorithm which can find a NE. Following this, we study the price of anarchy of such games, and show that it is bounded above by 3; we further provide some instances for which the price of anarchy is at least 2. We develop a quasi-polynomial algorithm O(n2Dln n), where n is the number of players and D is the diameter of the network, which can find, in a distributed manner, an allocation profile that is within a constant factor of the optimal allocation, and hence of any pure-strategy NE of the game. Proof of this result uses a novel potential function.