TY - GEN
T1 - A random tree search algorithm for Nash equilibrium in capacitated selfish replication games
AU - Ahmadyan, Seyed Nematollah
AU - Etesami, Seyed Rasoul
AU - Poor, H. Vincent
N1 - Funding Information:
This research was supported in part by the National Science Foundation under Grants ECCS-1343210 and ECCS-1549881.
PY - 2016/12/27
Y1 - 2016/12/27
N2 - In this paper, we consider a resource allocation game with binary preferences and limited capacities over large scale networks and propose a novel randomized algorithm for searching its pure-strategy Nash equilibrium points. It is known that such games always admit a pure-strategy Nash equilibrium and benefit from having a low price of anarchy. However, the best known theoretical results only provide a quasi-polynomial constant approximation algorithm of the equilibrium points over general networks. Here, we search the state space of the resource allocation game for its equilibrium points. We use a random tree based search method to minimize a proper score function and direct the search toward the pure-strategy Nash equilibrium points of the system. We demonstrate efficiency of our algorithm through some empirical results.
AB - In this paper, we consider a resource allocation game with binary preferences and limited capacities over large scale networks and propose a novel randomized algorithm for searching its pure-strategy Nash equilibrium points. It is known that such games always admit a pure-strategy Nash equilibrium and benefit from having a low price of anarchy. However, the best known theoretical results only provide a quasi-polynomial constant approximation algorithm of the equilibrium points over general networks. Here, we search the state space of the resource allocation game for its equilibrium points. We use a random tree based search method to minimize a proper score function and direct the search toward the pure-strategy Nash equilibrium points of the system. We demonstrate efficiency of our algorithm through some empirical results.
UR - http://www.scopus.com/inward/record.url?scp=85010807471&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85010807471&partnerID=8YFLogxK
U2 - 10.1109/CDC.2016.7798943
DO - 10.1109/CDC.2016.7798943
M3 - Conference contribution
AN - SCOPUS:85010807471
T3 - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
SP - 4439
EP - 4444
BT - 2016 IEEE 55th Conference on Decision and Control, CDC 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 55th IEEE Conference on Decision and Control, CDC 2016
Y2 - 12 December 2016 through 14 December 2016
ER -