An Approximation Algorithm and Price of Anarchy for the Binary-Preference Capacitated Selfish Replication Game

We consider in this paper a simple model for human interactions as service providers of different resources over social networks, and study the dynamics of selfish behavior of such social entities using a game-theoretic model known as binary-preference capacitated selfish replication (CSR) game. It is known that such games have an associated ordinal potential function, and hence always admit a pure-strategy Nash equilibrium (NE). 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 also devise a quasi-polynomial algorithm O(n(2+ln D)) 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 Nash equilibrium of the game, where the parameters n, and D denote, respectively, the number of players, and the diameter of the network. We further show that when the underlying network has a tree structure, every globally optimal allocation is a Nash equilibrium, which can be reached in only linear time.