Computer Science – Computer Science and Game Theory
Scientific paper
2010-07-16
Computer Science
Computer Science and Game Theory
Scientific paper
Motivated by 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 [Chun et al, PODC2004}, 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 networks. 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 framework of natural preference orders, orders that are entirely arbitrary except for two natural constraints - "Nearer is better" and "Independence of irrelevant alternatives". Using our axiomatic framework, we next study CSR games on arbitrary networks and delineate the boundary between intractability and effective computability in terms of the network structure, object preferences, and the total number of objects. We also show the existence of equilibria for general undirected networks when either object preferences are binary or there are two objects. For general CSR games, however, we show that it is NP-hard to determine whether equilibria exist. We also show that the existence of equilibria in strongly connected networks with two objects and binary object preferences can be determined in polynomial time via a reduction to the well-studied even-cycle problem. Finally, we introduce a fractional version of CSR games (F-SCR) with application to content distribution using erasure codes. We show that while every F-CSR game instance possesses an equilibrium, finding an equilibrium in an F-CSR game is PPAD-complete.
Gopalakrishnan Ragavendran
Kanoulas Dimitrios
Karuturi Naga Naresh
Rajaraman Rajmohan
Rangan Pandu C.
No associations
LandOfFree
Capacitated Caching Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Capacitated Caching Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capacitated Caching Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-50536