  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, 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 game-theoretic 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(n^2\log n) steps, where n
denotes the total number of nodes. However, for k>2 this problem becomes
NP-hard with no polynomial time approximation algorithm with a performance
guarantee better than 1+1/102k^2, even under metric access costs. We then
provide a 3-approximation algorithm for the optimal resource allocation which
runs only in linear time O(n). 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. Using this reduction, we show that finding the
lexicographically smallest Nash equilibrium for k> 2 is NP-hard, and provide an
algorithm to find it in O(n^3 2^n) steps. While the reduction to weighted
Max-k-Cut suggests that finding a pure Nash equilibrium using best response
dynamics might be PLS-hard, it allows us to use tools from quadratic
programming to devise more systematic algorithms towards obtaining Nash
equilibrium points.
