TY - GEN

T1 - Competitive contagion in networks

AU - Goyal, Sanjeev

AU - Kearns, Michael

PY - 2012

Y1 - 2012

N2 - We develop a game-theoretic framework for the study of competition between firms who have budgets to "seed" the initial adoption of their products by consumers located in a social network. The payoffs to the firms are the eventual number of adoptions of their product through a competitive stochastic diffusion process in the network. This framework yields a rich class of competitive strategies, which depend in subtle ways on the stochastic dynamics of adoption, the relative budgets of the players, and the underlying structure of the social network. We identify a general property of the adoption dynamics - namely, decreasing returns to local adoption - for which the inefficiency of resource use at equilibrium (the Price of Anarchy) is uniformly bounded above, across all networks. We also show that if this property is violated the Price of Anarchy can be unbounded, thus yielding sharp threshold behavior for a broad class of dynamics. We also introduce a new notion, the Budget Multiplier, that measures the extent that imbalances in player budgets can be amplified at equilibrium. We again identify a general property of the adoption dynamics - namely, proportional local adoption between competitors - for which the (pure strategy) Budget Multiplier is uniformly bounded above, across all networks. We show that a violation of this property can lead to unbounded Budget Multiplier, again yielding sharp threshold behavior for a broad class of dynamics.

AB - We develop a game-theoretic framework for the study of competition between firms who have budgets to "seed" the initial adoption of their products by consumers located in a social network. The payoffs to the firms are the eventual number of adoptions of their product through a competitive stochastic diffusion process in the network. This framework yields a rich class of competitive strategies, which depend in subtle ways on the stochastic dynamics of adoption, the relative budgets of the players, and the underlying structure of the social network. We identify a general property of the adoption dynamics - namely, decreasing returns to local adoption - for which the inefficiency of resource use at equilibrium (the Price of Anarchy) is uniformly bounded above, across all networks. We also show that if this property is violated the Price of Anarchy can be unbounded, thus yielding sharp threshold behavior for a broad class of dynamics. We also introduce a new notion, the Budget Multiplier, that measures the extent that imbalances in player budgets can be amplified at equilibrium. We again identify a general property of the adoption dynamics - namely, proportional local adoption between competitors - for which the (pure strategy) Budget Multiplier is uniformly bounded above, across all networks. We show that a violation of this property can lead to unbounded Budget Multiplier, again yielding sharp threshold behavior for a broad class of dynamics.

KW - algorithmic game theory

KW - social networks

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

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

U2 - 10.1145/2213977.2214046

DO - 10.1145/2213977.2214046

M3 - Conference contribution

AN - SCOPUS:84862632245

SN - 9781450312455

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 759

EP - 774

BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing

T2 - 44th Annual ACM Symposium on Theory of Computing, STOC '12

Y2 - 19 May 2012 through 22 May 2012

ER -