Cache me if you can: capacitated selfish replication games in networks

DOI10.1007/S00224-019-09939-7MaRDI QIDQ2300628zbMATH OpenOpenAlexFDO

Authors Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman, Ravi Sundaram

Publication date 27 February 2020

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.2694

zbMATH Keywords

computational complexitygame theorychoice theoryhierarchical networkscachingdistributed networkspreference orders

Mathematics Subject Classification ID

Applications of game theory (91A80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Abstract: In Peer-to-Peer (P2P) network systems, content (object) delivery between nodes is often required. One way to study such a distributed system is by defining games, which involve selfish nodes that make strategic choices on replicating content in their local limited memory (cache) or accessing content from other nodes for a cost. These Selfish Replication games have been introduced in [8] for nodes that do not have any capacity limits, leaving the capacitated problem, i.e. Capacitated Selfish Replication (CSR) games, open. In this work, we first form the model of the CSR games, for which we perform a Nash equilibria analysis. In particular, we focus on hierarchical networks, given their extensive use to model communication costs of content delivery in P2P systems. We present an exact polynomial-time algorithm for any hierarchical network, under two constraints on the utility functions: 1) "Nearer is better", i.e. the closest the content is to the node the less its access cost is, and 2) "Independence of irrelevant alternatives", i.e. aggregation of individual node preferences. This generalization represents a vast class of utilities and more interestingly allows each of the nodes to have simultaneously completely different functional forms of utility functions. In this general framework, we present CSR games results on arbitrary networks and outline the boundary between intractability and effective computability in terms of the network structure, object preferences, and the total number of objects. Moreover, we prove that the problem of equilibria existence becomes NP-hard for general CSR games.

Recommendations

• Cache me if you can: capacitated selfish replication games
• Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game
• Selfish caching in distributed systems, a game-theoretic analysis
• On the topologies formed by selfish peers
• Topological implications of selfish neighbor selection in unstructured peer-to-peer networks

Cites work

• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1233801 (Why is no real title available?)
• scientific article; zbMATH DE number 1947060 (Why is no real title available?)
• scientific article; zbMATH DE number 2080852 (Why is no real title available?)
• scientific article; zbMATH DE number 1559555 (Why is no real title available?)
• scientific article; zbMATH DE number 1559581 (Why is no real title available?)
• scientific article; zbMATH DE number 1928256 (Why is no real title available?)
• A course in game theory.
• Algorithmic Game Theory
• Approximation Algorithms for Data Placement Problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Cache me if you can: capacitated selfish replication games
• Efficient dispersal of information for security, load balancing, and fault tolerance
• How easy is local search?
• Mistreatment-resilient distributed caching
• On a network creation game
• On the complexity of the parity argument and other inefficient proofs of existence
• Optimal data placement on networks with a constant number of clients
• Permanents, Pfaffian orientations, and even directed circuits
• Placement algorithms for hierarchical cooperative caching
• Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game
• Pure Nash Equilibrium in a Capacitated Selfish Resource Allocation Game
• Raptor codes
• Selfish caching in distributed systems, a game-theoretic analysis
• Settling the complexity of computing two-player Nash equilibria
• Social choice and individual values
• The Online Median Problem
• The complexity of computing a Nash equilibrium
• Worst-case equilibria

Cited in

(4)

• Selfish caching in distributed systems, a game-theoretic analysis
• Cache me if you can: capacitated selfish replication games
• Give-and-take based peer-to-peer content distribution networks
• Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game

This page was built for publication: Cache me if you can: capacitated selfish replication games in networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300628)