Source-linked AI summary
Competitive Contagion in Networks
Sanjeev Goyal, Michael Kearns
TL;DR
The paper asks how competing firms should seed products in social networks when stochastic local adoption, network structure, and unequal budgets interact. It develops a game-theoretic diffusion framework with switching and selection dynamics, proving bounded or unbounded Price of Anarchy and Budget Multiplier behavior under sharp conditions.
Problem
The paper studies how competition for product adoption in social networks is shaped by stochastic diffusion, network structure, and firms’ seeding budgets.
Method
The paper models firms’ seeding choices as a network game with broad local dynamics decomposed into switching and selection functions, then analyzes Nash equilibria.
Results
Concave switching with linear selection bounds the Price of Anarchy by 4 and the pure-strategy Budget Multiplier by 2, while violating these properties can make either quantity unbounded.
Takeaways & Limitations
The framework identifies dynamic properties that determine whether networks preserve efficient resource use and initial budget proportions or amplify their distortions.
Takeaways & Limitations
The Budget Multiplier theorem’s general guarantee is stated for equilibria where the larger-budget player uses a pure strategy, with broader mixed-strategy validity only under additional conditions.
Abstract
from arXiv · showhide
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.
1. INTRODUCTION
The paper studies competition between firms seeding products in social networks, focusing on how local dynamics, budgets, and network structure shape equilibrium efficiency and budget amplification.
- Framework: Firms simultaneously seed consumers, whose subsequent stochastic adoptions determine each firm’s eventual payoff.The framework models Red and Blue firms competing over similar products or services in a known social network.
- Framework: The model separates adoption into switching, which depends on total neighboring adoption, and selection, which determines the competitor chosen after switching.The paper allows a broad class of local influence processes through functions f and g.
- Price of Anarchy: The Price of Anarchy is at most 4 when switching is concave and selection is linear, uniformly across all networks.The proof uses coupled stochastic processes to relate unilateral deviations to socially optimal seeding.
- Price of Anarchy: Any r > 1 makes the Price of Anarchy unbounded for f(x) = x^r with linear g, whereas r ≤1 keeps it at most 4.Layered networks repeatedly compose the switching function and amplify convexity.
- Budget Multiplier: The Budget Multiplier measures how much equilibrium final-payoff inequality can exceed the players’ initial budget inequality.It is maximized over Nash equilibria for fixed graphs, dynamics, and budgets.
- Budget Multiplier: The pure-strategy Budget Multiplier is at most 2 under concave switching and linear selection, but slight nonlinearity in selection can make it unbounded.The paper presents this as another sharp threshold phenomenon and identifies the Budget Multiplier as a new contribution.
2. MODEL
The model is a two-player stochastic adoption game on a known graph: firms allocate finite seeding budgets, local updates spread infections, and expected final infections define payoffs.
- Game and strategies: Red and Blue simultaneously choose initial seed allocations over vertices of a known, possibly directed graph.Each player may distribute a positive-integer budget across vertices, with the allocation summing to that player’s budget.
- Contagion process: After seeding, discrete-time stochastic contagion assigns each vertex the state Uninfected, Red, or Blue.The process determines how initial infections generate new adoptions.
- Update schedule: An update schedule determines which vertices are considered, while infected vertices are not candidates for later updates.Schedules may be sequential or parallel and may include immunity or finite termination.
- Local dynamics: The switching-selection model applies f to total infected-neighbor share and g to Red’s share among infected neighbors.Switching determines whether adoption occurs; selection determines which firm wins conditional on adoption.
- Payoffs and efficiency: Each firm’s payoff is the expected number of its eventual infections over strategy and update-process randomization.The Price of Anarchy compares the welfare-maximizing allocation with the lowest-payoff Nash equilibrium.
- Budget Multiplier: The Budget Multiplier is the largest equilibrium ratio of final-payoff inequality to initial-budget inequality.It captures how graph structure and stochastic dynamics amplify resource differences.
3. LOCAL DYNAMICS: MOTIVATION
The paper motivates switching and selection functions as separate dimensions of local adoption, illustrates them parametrically, and notes that some adoption rules lie outside this decomposition.
- Function roles: The switching function models overall contagion, while the selection function models competitor choice based on local market shares.This decomposition represents adoption intensity separately from which firm wins an adoption.
- Switching function: For f(x) = x^r, r = 1 is linear, r < 1 is concave, and r > 1 is convex or threshold-like.Concave switching rises quickly and saturates; convex switching stays low until adoption becomes substantial.
- Selection function: For the Tullock selection function, s = 1 is proportional selection, s < 1 equalizes, and s > 1 polarizes outcomes.As s approaches 0, selection approaches one-half for each competitor; as s approaches infinity, it approaches winner-take-all.
- Figure 1: Figure 1 contrasts concave, linear, and convex switching curves with equalizing, linear, and polarizing selection curves.The left panel varies r in f(x) = x^r; the right varies s in g(y) = y^s/(y^s + (1 −y)^s).
- Applications: The parametric families serve as examples for the paper’s general results and technology-adoption applications.The paper discusses social-network services as plausibly convex-switching and televisions as plausibly concave-switching.
- Scope: The switching-selection decomposition excludes some adoption functions, including rules whose total adoption cannot be expressed as a function of combined exposure.The paper also gives an example violating monotonicity when consumers favor settled majority choices.
4. EQUILIBRIUM EXAMPLES
The examples show that equilibrium outcomes depend jointly on network structure, switching and selection functions, and budget allocation. Small changes in these ingredients can produce large changes in PoA and Budget Multiplier.
- Price of Anarchy: Linear switching and selection can yield a unique equilibrium with PoA 1 when both seeds target the larger component.The equilibrium infects all 100 vertices, which is the maximum possible with two seeds.
- Price of Anarchy: Changing only switching to f(1/2) = ϵ creates an equilibrium in the smaller component with PoA 10 for ϵ < 1/25.Each player receives 5, while deviating to the larger component yields expected payoff ϵ × 100.
- Price of Anarchy: With one 110-vertex component, both switching functions produce PoA 1 because equilibrium seeds infect every vertex.This remains true even when f(1/2) < 1/25.
- Price of Anarchy: Across fixed networks, updating rules, and selection functions, variations in switching functions can substantially change PoA; network changes can also do so.The examples establish that neither dynamics nor topology alone determines efficiency.
- Price of Anarchy: Small violations of the sufficient conditions for bounded PoA can produce arbitrarily high PoA.Theorem 1 gives boundedness conditions, while Theorem 3 establishes the sharp contrasting failure.
- Budget Multiplier: Budget Multiplier varies with switching and selection functions and with network structure, despite fixed budgets and updating rules.Theorems 4–6 give sufficient boundedness conditions, show unboundedness under small violations, and isolate switching-function concavity.
5. RESULTS: PRICE OF ANARCHY
The paper establishes a sharp PoA threshold: concave switching dynamics with linear selection yield a network-independent bound, while convexity or threshold behavior can make PoA arbitrarily large.
- 5.1 PoA: Upper Bound: Concavity of the switching function supports bounded PoA because it supplies the required diminishing-returns condition for the coupling argument.The switching-selection formulation makes total infection probability additive, while competitiveness limits a player’s infection probability in the presence of its rival.
- 5.1 PoA: Upper Bound: Theorem 1 bounds the Price of Anarchy by 4 on every graph when adoption is competitive and total infection probability is additive.The proof uses coupled stochastic processes to relate unilateral departures, individual payoffs, and total joint infections.
- 5.2 PoA: Lower Bound: Threshold switching can produce arbitrarily large PoA: coordinating seeds in one component is a Nash equilibrium, although concentrating them in the other component maximizes joint infections.The equilibrium yields n1 second-layer infections, whereas the socially optimal placement yields n2, so PoA equals n2/n1 and can grow without bound.
- 5.2 PoA: Lower Bound: Even slight convexity causes unbounded PoA: for f(x) = x^r with r > 1 and linear g, a graph family has PoA growing linearly with population size.Layered directed networks repeatedly compose the switching function, amplifying convexity and creating inefficient equilibria.
- 5.2 PoA: Lower Bound: Together, the upper and lower bounds establish a sharp threshold at r = 1 for power switching functions with linear selection.The bounded regime is r ≤1; for every r > 1 and any V, some graph has PoA greater than V.
- 5.1 PoA: Upper Bound: For f(x) = x^r and linear g, PoA is at most 4 for r ≤1, including specified nonlinear selection functions when s ∈[r, 1].The result permits some equalizing nonlinear selection functions alongside sufficiently concave switching functions.
6. RESULTS: BUDGET MULTIPLIER
The paper defines Budget Multiplier as the extent to which equilibrium outcomes amplify initial budget differences, then establishes sharp boundedness thresholds tied to adoption dynamics. Under linear selection and suitable switching, it is bounded by 2; nonlinear or sufficiently convex dynamics can make it unbounded across network families.
- Upper Bound: Theorem 4 bounds the pure-strategy Budget Multiplier by 2 on every graph when the switching function is concave and the selection function is linear.The proof attributes subsequent adoptions to their initial seeds.
- Upper Bound: The upper-bound argument uses attribution simulations to compare solo and competitive diffusion, with equilibrium payoffs constrained by profitable imitation strategies.The attribution process labels infections by the seed responsible for generating them.
- Lower Bound: Small departures from linear selection can produce unbounded Budget Multiplier because layered networks amplify nonlinearity through self-composition and squeeze out the smaller-budget player.The construction yields ratios increasing exponentially in the number of layers for fixed s > 1.
- Lower Bound: For linear switching and Tullock selection g(y) = y^s/(y^s + (1 − y)^s), s = 1 gives Budget Multiplier at most 2, whereas every s > 1 permits values above any V on some graph.Theorem 5 further states that, for s > 1, a graph family has Budget Multiplier growing linearly with population size.
- Lower Bound: If f(1/2) = 0 and f(1) = 1, replicated chain constructions yield arbitrarily large Budget Multiplier, even when the smaller-budget player has many seeds.The replication prevents profitable deviations by making missing input infections halt other chains.
7. CONCLUDING REMARKS
The framework identifies conditions under which equilibrium resource use is efficient or inefficient and budgets are neutralized or amplified. It also highlights open questions about endogenous budgets, equilibrium structure, algorithms, and multi-stage play.
- The framework identifies adoption-dynamics properties under which equilibrium resource use is efficient or unboundedly inefficient.
- Network structure can neutralize or dramatically accentuate ex-ante resource differences between players.
- The relationship between equilibrium structure and network structure remains an open research direction.
- Endogenous budgets could aggravate or mitigate high PoA, while large network advantages may incentivize budget increases and become self-neutralizing.
- Future work includes computing equilibria and best responses and studying multi-stage games with spending tied to the evolving network state.
APPENDIX
The appendix sketches rational microeconomic foundations for the stochastic consumer decisions represented by the switching and selection functions. It gives information-sharing examples while leaving richer joint firm-consumer models for future work.
- The appendix sketches cases where stochastic consumer decisions can be grounded in rational microeconomic models.
- An information-sharing example models consumers learning about search goods through their own search and conversations with friends or neighbors.
- A second example combines information sharing with payoff externalities from adopting the same product as other consumers.
- A fully game-theoretic formulation involving both firms and consumers is left for future work.