An approximation algorithm and price of anarchy for the binary-preference capacitated selfish replication game

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider in this paper a simple model for human interactions as service providers of different resources over social networks, and study the dynamics of selfish behavior of such social entities using a game-theoretic model known as binary-preference capacitated selfish replication (CSR) game. It is known that such games have an associated ordinal potential function, and hence always admit a pure-strategy Nash equilibrium (NE). We study the price of anarchy of such games, and show that it is bounded above by 3; we further provide some instances for which the price of anarchy is at least 2. We also devise a quasi-polynomial algorithm O(n2+ln D) which can find, in a distributed manner, an allocation profile that is within a constant factor of the optimal allocation, and hence of any pure-strategy Nash equilibrium of the game, where the parameters n, and D denote, respectively, the number of players, and the diameter of the network. We further show that when the underlying network has a tree structure, every globally optimal allocation is a Nash equilibrium, which can be reached in only linear time.

Original languageEnglish (US)
Title of host publication54rd IEEE Conference on Decision and Control,CDC 2015
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3568-3573
Number of pages6
ISBN (Electronic)9781479978861
DOIs
StatePublished - Feb 8 2015
Event54th IEEE Conference on Decision and Control, CDC 2015 - Osaka, Japan
Duration: Dec 15 2015Dec 18 2015

Publication series

NameProceedings of the IEEE Conference on Decision and Control
Volume54rd IEEE Conference on Decision and Control,CDC 2015
ISSN (Print)0743-1546

Other

Other54th IEEE Conference on Decision and Control, CDC 2015
CountryJapan
CityOsaka
Period12/15/1512/18/15

Keywords

  • Capacitated selfish replication game
  • optimal allocation
  • potential function
  • price of anarchy
  • pure Nash equilibrium (NE)
  • quasi-polynomial algorithm

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization

Fingerprint Dive into the research topics of 'An approximation algorithm and price of anarchy for the binary-preference capacitated selfish replication game'. Together they form a unique fingerprint.

Cite this