Capacitated Caching Games
Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, Chandrasekharan Pandu Rangan, Rajmohan Rajaraman, Ravi Sundaram · 2010
Capacitated Caching (CC) Games are motivated by P2P and web caching applications, and involve nodes on a network making strategic choices regarding the content to replicate in their caches. Caching games were introduced by Chun et al [6], who analyzed the uncapacitated case leaving the capacitated version as an open direction. In this work, we study pure Nash equilibria of both fractional (FCC) and integral (ICC) versions of CC games. Using erasure codes we present a compelling realization of FCC games in content distribution. We show that every FCC game instance possesses an equilibrium. We also show, however, that finding an equilibrium in an FCC game is PPAD-complete. For ICC games we delineate the boundary between intractability and effective computability in terms of the network structure, object preferences, and the total number of objects. A central result of this paper is the existence (and poly-time computability) of equilibria for hierarchical networks. Using a potential function argument, we also show the existence of equilibria for general symmetric networks when object preferences are binary. For general ICC games, however, equilibria may not exist. In fact, we show that it is NP-hard to determine whether equilibria exist, even when either the network is symmetric and there are