TY - GEN

T1 - An approximation algorithm and price of anarchy for the binary-preference capacitated selfish replication game

AU - Etesami, Seyed Rasoul

AU - Basar, Tamer

N1 - Publisher Copyright:
© 2015 IEEE.

PY - 2015/2/8

Y1 - 2015/2/8

N2 - 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(n2+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.

AB - 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(n2+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.

KW - Capacitated selfish replication game

KW - optimal allocation

KW - potential function

KW - price of anarchy

KW - pure Nash equilibrium (NE)

KW - quasi-polynomial algorithm

UR - http://www.scopus.com/inward/record.url?scp=84961994324&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961994324&partnerID=8YFLogxK

U2 - 10.1109/CDC.2015.7402771

DO - 10.1109/CDC.2015.7402771

M3 - Conference contribution

AN - SCOPUS:84961994324

T3 - Proceedings of the IEEE Conference on Decision and Control

SP - 3568

EP - 3573

BT - 54rd IEEE Conference on Decision and Control,CDC 2015

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 54th IEEE Conference on Decision and Control, CDC 2015

Y2 - 15 December 2015 through 18 December 2015

ER -