A note on competitive diffusion through social networks

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

doi:10.1016/j.ipl.2009.12.009

A note on competitive diffusion through social networks

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

Research output: Contribution to journal › Article › peer-review

88 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 language	English (US)
Pages (from-to)	221-225
Number of pages	5
Journal	Information Processing Letters
Volume	110
Issue number	6
DOIs	https://doi.org/10.1016/j.ipl.2009.12.009
State	Published - Feb 15 2010
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Keywords

Algorithmic game theory
Graph algorithms
Social networks

Access to Document

10.1016/j.ipl.2009.12.009

Cite this

@article{4abb2a63728640e6ba874631980de172,

title = "A note on competitive diffusion through social networks",

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.",

keywords = "Algorithmic game theory, Graph algorithms, Social networks",

author = "Noga Alon and Michal Feldman and Procaccia, {Ariel D.} and Moshe Tennenholtz",

note = "Funding Information: 1 Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation, by an ERC advanced grant and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.",

year = "2010",

month = feb,

day = "15",

doi = "10.1016/j.ipl.2009.12.009",

language = "English (US)",

volume = "110",

pages = "221--225",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - A note on competitive diffusion through social networks

AU - Alon, Noga

AU - Feldman, Michal

AU - Procaccia, Ariel D.

AU - Tennenholtz, Moshe

N1 - Funding Information: 1 Research supported in part by a USA Israeli BSF grant, by a grant from the Israel Science Foundation, by an ERC advanced grant and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University.

PY - 2010/2/15

Y1 - 2010/2/15

N2 - 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.

AB - 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.

KW - Algorithmic game theory

KW - Graph algorithms

KW - Social networks

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

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

U2 - 10.1016/j.ipl.2009.12.009

DO - 10.1016/j.ipl.2009.12.009

M3 - Article

AN - SCOPUS:74449083450

SN - 0020-0190

VL - 110

SP - 221

EP - 225

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

A note on competitive diffusion through social networks

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this