TY - JOUR
T1 - Pure Nash Equilibrium in a Capacitated Selfish Resource Allocation Game
AU - Etesami, Seyed Rasoul
AU - Basar, Tamer
N1 - Funding Information:
Manuscript received September 3, 2016; accepted November 16, 2016. Date of publication November 22, 2016; date of current version March 16, 2018. This work was supported in part by the “Cognitive & Algorithmic Decision Making”, in part by a project grant from the College of Engineering of the University of Illinois, and in part by AFOSR MURI Grant FA 9550-10-1-0573 and NSF grant CCF 11-11342. Recommended by Associate Editor Prof. Fabio Fagnani.
Publisher Copyright:
© 2014 IEEE.
PY - 2018/3
Y1 - 2018/3
N2 - A resource allocation game with identical preferences is considered where each player, as a node of an undirected unweighted network, tries to minimize his or her cost by caching an appropriate resource. Using a generalized ordinal potential function, a polynomial time algorithm is devised in order to obtain a pure-strategy Nash equilibrium (NE) when the number of resources is limited or the network has a high edge density with respect to the number of resources. Moreover, an algorithm to approximate any NE of the game over general networks is provided, and the results are extended to games with arbitrary cache sizes. Finally, a connection between graph coloring and the NE points has been established.
AB - A resource allocation game with identical preferences is considered where each player, as a node of an undirected unweighted network, tries to minimize his or her cost by caching an appropriate resource. Using a generalized ordinal potential function, a polynomial time algorithm is devised in order to obtain a pure-strategy Nash equilibrium (NE) when the number of resources is limited or the network has a high edge density with respect to the number of resources. Moreover, an algorithm to approximate any NE of the game over general networks is provided, and the results are extended to games with arbitrary cache sizes. Finally, a connection between graph coloring and the NE points has been established.
UR - http://www.scopus.com/inward/record.url?scp=85044514428&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85044514428&partnerID=8YFLogxK
U2 - 10.1109/TCNS.2016.2631440
DO - 10.1109/TCNS.2016.2631440
M3 - Article
AN - SCOPUS:85044514428
SN - 2325-5870
VL - 5
SP - 536
EP - 547
JO - IEEE Transactions on Control of Network Systems
JF - IEEE Transactions on Control of Network Systems
IS - 1
ER -