A note on competitive diffusion through social networks

Noga Alon, Michal Feldman, Ariel D. Procaccia, Moshe Tennenholtz

Research output: Contribution to journalArticle

65 Scopus citations

Abstract

We introduce a game-theoretic model of diffusion of technologies, advertisements, or influence through a social network. The novelty in our model is that the players are interested parties outside the network. We study the relation between the diameter of the network and the existence of pure Nash equilibria in the game. In particular, we show that if the diameter is at most two then an equilibrium exists and can be found in polynomial time, whereas if the diameter is greater than two then an equilibrium is not guaranteed to exist.

Original languageEnglish (US)
Pages (from-to)221-225
Number of pages5
JournalInformation Processing Letters
Volume110
Issue number6
DOIs
StatePublished - Feb 15 2010
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Keywords

  • Algorithmic game theory
  • Graph algorithms
  • Social networks

Fingerprint Dive into the research topics of 'A note on competitive diffusion through social networks'. Together they form a unique fingerprint.

  • Cite this