Complexity and approximability of optimal resource allocation and nash equilibrium over networks

Research output: Contribution to journalArticlepeer-review


Motivated by emerging resource allocation and data placement problems such as web caches and peer-to-peer systems, we consider and study a class of resource allocation problems over a network of agents (nodes). In this model, which can be viewed as a homogeneous data placement problem, nodes can store only a limited number of resources while accessing the remaining ones through their closest neighbors. We consider this problem under both optimization and gametheoretic frameworks. In the case of optimal resource allocation, we will first show that when there are only k = 2 resources, the optimal allocation can be found efficiently in O(n2 log n) steps, where n denotes the total number of nodes. However, for k ≥ 3 this problem becomes NP-hard with no polynomial-time approximation algorithm with a performance guarantee better than 1+ 1/ 102k2, even under metric access costs. We then provide a 3-approximation algorithm for the optimal resource allocation which runs only in O(kn2). Subsequently, we look at this problem under a selfish setting formulated as a noncooperative game and provide a 3-approximation algorithm for obtaining its pure Nash equilibria under metric access costs. We then establish an equivalence between the set of pure Nash equilibria and flip-optimal solutions of the Max-k-Cut problem over a specific weighted complete graph. While this reduction suggests that finding a pure Nash equilibrium using best response dynamics might be PLS-hard, it allows us to use tools from complementary slackness and quadratic programming to devise systematic and more efficient algorithms towards obtaining Nash equilibrium points.

Original languageEnglish (US)
Pages (from-to)885-914
Number of pages30
JournalSIAM Journal on Optimization
Issue number1
StatePublished - 2020


  • Approximation algorithm
  • Computational complexity
  • Data placement problem
  • Facility location
  • Network games
  • Potential games
  • Quadratic programming
  • Resource allocation

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Applied Mathematics


Dive into the research topics of 'Complexity and approximability of optimal resource allocation and nash equilibrium over networks'. Together they form a unique fingerprint.

Cite this