Pure Nash Equilibrium in a Capacitated Selfish Resource Allocation Game

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)536-547
Number of pages12
JournalIEEE Transactions on Control of Network Systems
Issue number1
StatePublished - Mar 2018

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Signal Processing
  • Computer Networks and Communications
  • Control and Optimization


Dive into the research topics of 'Pure Nash Equilibrium in a Capacitated Selfish Resource Allocation Game'. Together they form a unique fingerprint.

Cite this