A Game Theoretic Analysis of Selfish Content Replication on Graphs
2011 (English)In: 7th Swedish National Computer Networking Workshop (SNCNW), 2011, 2011Conference paper (Refereed)
Replication games are a model of the problem of content placement in computer and communication systems, when the participating nodes maketheir decisions such as to maximize their individualutilities. In this paper we consider replication gamesplayed over arbitrary social graphs; the social graphmodels limited interaction between the players due to,e.g., the network topology. We show that in replicationgames there is an equilibrium object placement forarbitrary social graphs. Nevertheless, if all nodes followa myopic strategy to update their object placementsthen they might cycle arbitrarily long before reachingan equilibrium if the social graph is non-complete. Wegive suﬃcient conditions under which such cycles do notexist, and propose an eﬃcient distributed algorithm toreach an equilibrium over a non-complete social graph.
Place, publisher, year, edition, pages
Game theory, Selfish Replication
IdentifiersURN: urn:nbn:se:kth:diva-118447OAI: oai:DiVA.org:kth-118447DiVA: diva2:606206
7th Swedish National Computer Networking Workshop (SNCNW), 2011
QC 201302262013-02-262013-02-182013-02-26Bibliographically approved