Cache me if you can: Capacitated selfish replication in networks

Motivated by peer-to-peer (P2P) networks and content delivery applications, we study Capacitated Selfish Replication (CSR) games, which involve nodes on a network making strategic choices regarding the content to replicate in their caches. Selfish replication games were introduced in [6], who analyzed the uncapacitated case leaving the capacitated version as an open direction. In this work, we study pure Nash equilibria of CSR games with an emphasis on hierarchical net-works, which have been extensively used to model the communication costs of content delivery and P2P systems. The best result from previous work on CSR games for hierarchical networks [21, 27] is the ex-istence of a Nash equilibrium for a (slight generalization of a) 1-level hierarchy when the utility function is based on the sum of the costs of accessing the replicated objects in the network. Our main result is an exact polynomial-time algorithm for finding a Nash Equilibrium in any hierarchical network using a new technique which we term “fictional players”. We show that this technique extends to a general frame-work of natural preference orders, orders that are entirely arbitrary except for two natural constraints-“Nearer is better ” and “Independence of irrelevant alternatives”. This axiomatic treatment captures a vast class of utility functions and even allows for nodes to simultaneously have utility functions of completel