Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game

Research output: Contribution to journalArticle

Abstract

We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We study the price of anarchy of such games, and show that it is bounded above by 3. We develop a quasi-polynomial algorithm O(n2+lnD), where n is the number of players and D is the diameter of the network, 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 (NE) of the game. Proof of this result uses a novel potential function. We further show that when the underlying network has a tree structure, every globally optimal allocation is an NE, which can be reached in only linear time. We formulate the optimal solutions and NE points of the CSR game using integer linear programs. Finally, we introduce the LCSR game as a localized version of the CSR game, wherein the actions of the players are restricted to only their close neighborhoods.

Original languageEnglish (US)
Pages (from-to)153-163
Number of pages11
JournalAutomatica
Volume76
DOIs
StatePublished - Feb 1 2017

Fingerprint

Approximation algorithms
Polynomials

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
  • Electrical and Electronic Engineering

Cite this

@article{03b76d1beaa64f92b26f191fe2d5f4c5,
title = "Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game",
abstract = "We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We study the price of anarchy of such games, and show that it is bounded above by 3. We develop a quasi-polynomial algorithm O(n2+lnD), where n is the number of players and D is the diameter of the network, 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 (NE) of the game. Proof of this result uses a novel potential function. We further show that when the underlying network has a tree structure, every globally optimal allocation is an NE, which can be reached in only linear time. We formulate the optimal solutions and NE points of the CSR game using integer linear programs. Finally, we introduce the LCSR game as a localized version of the CSR game, wherein the actions of the players are restricted to only their close neighborhoods.",
keywords = "Capacitated selfish replication game, Optimal allocation, Potential function, Price of anarchy, Pure Nash equilibrium (NE), Quasi-polynomial algorithm",
author = "Etesami, {Seyed Rasoul} and Tamer Başar",
year = "2017",
month = "2",
day = "1",
doi = "10.1016/j.automatica.2016.10.002",
language = "English (US)",
volume = "76",
pages = "153--163",
journal = "Automatica",
issn = "0005-1098",
publisher = "Elsevier Limited",

}

TY - JOUR

T1 - Price of anarchy and an approximation algorithm for the binary-preference capacitated selfish replication game

AU - Etesami, Seyed Rasoul

AU - Başar, Tamer

PY - 2017/2/1

Y1 - 2017/2/1

N2 - We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We study the price of anarchy of such games, and show that it is bounded above by 3. We develop a quasi-polynomial algorithm O(n2+lnD), where n is the number of players and D is the diameter of the network, 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 (NE) of the game. Proof of this result uses a novel potential function. We further show that when the underlying network has a tree structure, every globally optimal allocation is an NE, which can be reached in only linear time. We formulate the optimal solutions and NE points of the CSR game using integer linear programs. Finally, we introduce the LCSR game as a localized version of the CSR game, wherein the actions of the players are restricted to only their close neighborhoods.

AB - We consider the capacitated selfish replication (CSR) game with binary preferences, over general undirected networks. We study the price of anarchy of such games, and show that it is bounded above by 3. We develop a quasi-polynomial algorithm O(n2+lnD), where n is the number of players and D is the diameter of the network, 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 (NE) of the game. Proof of this result uses a novel potential function. We further show that when the underlying network has a tree structure, every globally optimal allocation is an NE, which can be reached in only linear time. We formulate the optimal solutions and NE points of the CSR game using integer linear programs. Finally, we introduce the LCSR game as a localized version of the CSR game, wherein the actions of the players are restricted to only their close neighborhoods.

KW - Capacitated selfish replication game

KW - Optimal allocation

KW - Potential function

KW - Price of anarchy

KW - Pure Nash equilibrium (NE)

KW - Quasi-polynomial algorithm

UR - http://www.scopus.com/inward/record.url?scp=85002877417&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85002877417&partnerID=8YFLogxK

U2 - 10.1016/j.automatica.2016.10.002

DO - 10.1016/j.automatica.2016.10.002

M3 - Article

AN - SCOPUS:85002877417

VL - 76

SP - 153

EP - 163

JO - Automatica

JF - Automatica

SN - 0005-1098

ER -