Complexity of equilibrium in diffusion games on social networks

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

Abstract

We revisit the competitive diffusion game on undirected connected graphs and study the complexity of the existence of pure-strategy Nash equilibrium for such games. We first characterize the utility of each player based on the location of its initial seed placements. Using this characterization, we show that the utility of each player is a sub-modular function of its initial seed set. Following this, a simple greedy algorithm provides an initial seed placement within a constant factor of the optimal solution. We show NP-completeness of the decision on the existence of pure-strategy Nash equilibrium for general networks. Finally we provide some necessary conditions for a given profile to be a Nash equilibrium and obtain a lower bound for the maximum social welfare of the game with two players.

Original languageEnglish (US)
Title of host publication2014 American Control Conference, ACC 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2065-2070
Number of pages6
ISBN (Print)9781479932726
DOIs
StatePublished - Jan 1 2014
Event2014 American Control Conference, ACC 2014 - Portland, OR, United States
Duration: Jun 4 2014Jun 6 2014

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619

Other

Other2014 American Control Conference, ACC 2014
CountryUnited States
CityPortland, OR
Period6/4/146/6/14

Keywords

  • Competitive diffusion game
  • NP-hardness
  • greedy algorithm
  • pure Nash equilibrium
  • social welfare
  • sub-modular function

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Complexity of equilibrium in diffusion games on social networks'. Together they form a unique fingerprint.

Cite this