Abstract

In this paper, we consider the competitive diffusion game, and study the existence of its pure-strategy Nash equilibrium when defined over general undirected networks. We first determine the set of pure-strategy Nash equilibria for two special but well-known classes of networks, namely the lattice and the hypercube. Characterizing the utility of the players in terms of graphical distances of their initial seed placements to other nodes in the network, we show that in general networks the decision process on the existence of pure-strategy Nash equilibrium is an NP-hard problem. Following this, we provide some necessary conditions for a given profile to be a Nash equilibrium. Furthermore, we study players' utilities in the competitive diffusion game over Erdos-Renyi random graphs and show that as the size of the network grows, the utilities of the players are highly concentrated around their expectation, and are bounded below by some threshold based on the parameters of the network. Finally, we obtain a lower bound for the maximum social welfare of the game with two players, and study sub-modularity of the players' utilities.

Original languageEnglish (US)
Pages (from-to)100-110
Number of pages11
JournalAutomatica
Volume68
DOIs
StatePublished - Jan 1 2016

Fingerprint

Computational complexity

Keywords

  • Competitive diffusion game
  • Erdos-Renyi graphs
  • NP-hardness
  • Pure-strategy Nash equilibrium
  • Social welfare
  • Sub-modular function

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Electrical and Electronic Engineering

Cite this

Complexity of equilibrium in competitive diffusion games on social networks. / Etesami, Seyed Rasoul; Başar, Tamer.

In: Automatica, Vol. 68, 01.01.2016, p. 100-110.

Research output: Contribution to journalArticle

@article{4a9cb3fe1bec4700a56f7284c7c5fa63,
title = "Complexity of equilibrium in competitive diffusion games on social networks",
abstract = "In this paper, we consider the competitive diffusion game, and study the existence of its pure-strategy Nash equilibrium when defined over general undirected networks. We first determine the set of pure-strategy Nash equilibria for two special but well-known classes of networks, namely the lattice and the hypercube. Characterizing the utility of the players in terms of graphical distances of their initial seed placements to other nodes in the network, we show that in general networks the decision process on the existence of pure-strategy Nash equilibrium is an NP-hard problem. Following this, we provide some necessary conditions for a given profile to be a Nash equilibrium. Furthermore, we study players' utilities in the competitive diffusion game over Erdos-Renyi random graphs and show that as the size of the network grows, the utilities of the players are highly concentrated around their expectation, and are bounded below by some threshold based on the parameters of the network. Finally, we obtain a lower bound for the maximum social welfare of the game with two players, and study sub-modularity of the players' utilities.",
keywords = "Competitive diffusion game, Erdos-Renyi graphs, NP-hardness, Pure-strategy Nash equilibrium, Social welfare, Sub-modular function",
author = "Etesami, {Seyed Rasoul} and Tamer Başar",
year = "2016",
month = "1",
day = "1",
doi = "10.1016/j.automatica.2016.01.063",
language = "English (US)",
volume = "68",
pages = "100--110",
journal = "Automatica",
issn = "0005-1098",
publisher = "Elsevier Limited",

}

TY - JOUR

T1 - Complexity of equilibrium in competitive diffusion games on social networks

AU - Etesami, Seyed Rasoul

AU - Başar, Tamer

PY - 2016/1/1

Y1 - 2016/1/1

N2 - In this paper, we consider the competitive diffusion game, and study the existence of its pure-strategy Nash equilibrium when defined over general undirected networks. We first determine the set of pure-strategy Nash equilibria for two special but well-known classes of networks, namely the lattice and the hypercube. Characterizing the utility of the players in terms of graphical distances of their initial seed placements to other nodes in the network, we show that in general networks the decision process on the existence of pure-strategy Nash equilibrium is an NP-hard problem. Following this, we provide some necessary conditions for a given profile to be a Nash equilibrium. Furthermore, we study players' utilities in the competitive diffusion game over Erdos-Renyi random graphs and show that as the size of the network grows, the utilities of the players are highly concentrated around their expectation, and are bounded below by some threshold based on the parameters of the network. Finally, we obtain a lower bound for the maximum social welfare of the game with two players, and study sub-modularity of the players' utilities.

AB - In this paper, we consider the competitive diffusion game, and study the existence of its pure-strategy Nash equilibrium when defined over general undirected networks. We first determine the set of pure-strategy Nash equilibria for two special but well-known classes of networks, namely the lattice and the hypercube. Characterizing the utility of the players in terms of graphical distances of their initial seed placements to other nodes in the network, we show that in general networks the decision process on the existence of pure-strategy Nash equilibrium is an NP-hard problem. Following this, we provide some necessary conditions for a given profile to be a Nash equilibrium. Furthermore, we study players' utilities in the competitive diffusion game over Erdos-Renyi random graphs and show that as the size of the network grows, the utilities of the players are highly concentrated around their expectation, and are bounded below by some threshold based on the parameters of the network. Finally, we obtain a lower bound for the maximum social welfare of the game with two players, and study sub-modularity of the players' utilities.

KW - Competitive diffusion game

KW - Erdos-Renyi graphs

KW - NP-hardness

KW - Pure-strategy Nash equilibrium

KW - Social welfare

KW - Sub-modular function

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

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

U2 - 10.1016/j.automatica.2016.01.063

DO - 10.1016/j.automatica.2016.01.063

M3 - Article

AN - SCOPUS:84958824487

VL - 68

SP - 100

EP - 110

JO - Automatica

JF - Automatica

SN - 0005-1098

ER -