Header menu link for other important links
X
Cache me if you can: Capacitated selfish replication games
Ragavendran Gopalakrishnan, Naga Naresh Karuturi, Chandrasekharan Pandu Rangan
Published in
2012
Volume: 7256 LNCS
   
Pages: 420 - 432
Abstract
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 networks, which have been extensively used to model communication costs of content delivery and P2P systems. The best result from previous work on CSR games for hierarchical networks [19,23] is the existence 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 framework of natural preference orders, orders that are entirely arbitrary except for two 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 completely different functional forms. 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 number of objects. In addition to hierarchical networks, we 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 solved in polynomial time via a reduction to the well-studied evencycle problem. © 2012 Springer-Verlag Berlin Heidelberg.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN03029743
Open AccessYes
Concepts (28)
  •  related image
    ARBITRARY NETWORKS
  •  related image
    AXIOMATIC FRAMEWORK
  •  related image
    Binary objects
  •  related image
    CLASS OF UTILITY FUNCTIONS
  •  related image
    Communication cost
  •  related image
    Content delivery
  •  related image
    Functional forms
  •  related image
    Hierarchical network
  •  related image
    INDEPENDENCE OF IRRELEVANT ALTERNATIVES
  •  related image
    Nash equilibria
  •  related image
    NETWORK STRUCTURES
  •  related image
    Np-hard
  •  related image
    P2P SYSTEM
  •  related image
    PEER TO PEER (P2P) NETWORK
  •  related image
    Polynomial-time
  •  related image
    Polynomial-time algorithms
  •  related image
    Preference order
  •  related image
    PURE NASH EQUILIBRIUM
  •  related image
    REPLICATED OBJECTS
  •  related image
    STRATEGIC CHOICE
  •  related image
    Strongly connected
  •  related image
    UNDIRECTED NETWORK
  •  related image
    Utility functions
  •  related image
    Distributed computer systems
  •  related image
    Game theory
  •  related image
    Information science
  •  related image
    Polynomial approximation
  •  related image
    Peer to peer networks