Competitive Rumor Dynamics: How Social Network Structure Dictates Strategic Equilibrium

TL;DR

When two entities compete to spread information in a social network, their success isn't just about who starts first—it's about the "Cascade Centrality" of their starting points. This paper provides a rigorous mathematical characterization of when competition reaches a stable Nash equilibrium, proves that the competitive outcome is at most 33% less efficient than a social planner’s ideal, and shows that even with equal budgets, one firm can potentially reach twice as many people as the other.

The Problem: Why Equilibrium is Elusive

In the world of social contagion, rumors propagate through individual "thresholds"—I’ll share a rumor only if a certain percentage of my friends do. When two firms compete (e.g., Apple vs. Samsung or two political parties), they seed an initial user.

Existing research struggled to define when this competition stabilizes. In highly symmetric networks with many cycles, firms often end up in a "game of cat and mouse" where no fixed strategy is optimal, leading to a lack of Pure-Strategy Nash Equilibria (PSNE).

Methodology: The Power of Cascade Centrality

The authors introduce Cascade Centrality (${\mathcal{C}}_i$), which calculates the expected influence of a node by summing probabilities across all simple paths emanating from it.

The Core Metric

A node's centrality is defined as: ${\mathcal{C}}_i(G)=1+{\sum }_{j\in V\setminus \{i\}}{\sum }_{P\in {\mathcal{P}}_{ij}}\frac{1}{{\chi }_P}$ where ${\chi }_P$ is the product of node degrees along path $P$.

Intuitive Equilibrium Conditions

The paper identifies two types of stable outcomes:

1. Monopoly Seeding: Both firms seed the same node $i$ if its centrality is so high that even a 50% chance of winning that node's cascade is better than choosing any other node.
2. Strategic Divergence: Firms choose different nodes $i$ and $j$ if they are "far" enough apart to minimize Interference ($ϵ$). Interference occurs when paths from one seed are blocked or redirected by the other.

Figure 1: Visualizing how interference affects the cascade path between nodes.

Experiments & Results: Efficiency and Inequality

The authors tested their model against various graph topologies, including complex cycles and simplified trees.

1. The Price of Anarchy (PoA)

Socially, we might want to maximize the total number of people informed. Competitive firms, however, only care about their own share. The authors proved: $1\le PoA(\Gamma )<1.5$ This means that even in the worst-case scenario, competition only loses about 1/3 of the potential total spread compared to a master coordinator.

2. The Budget Multiplier (Payoff Inequality)

Even if both firms start with exactly one seed, the one in a more "central" position can dominate. The study bounds this inequality: $BM(\Gamma )<2$ One firm can never be more than twice as successful as its competitor if both have unit budgets and are in equilibrium.

Figure 2: A specialized tree structure where standard PSNE fails to be socially efficient.

Deep Insight: Competing on Trees vs. Graphs

The model becomes exceptionally transparent when applied to tree structures. In trees, there are no cycles to complicate the pathing. The authors show that a PSNE always exists in a tree. The strategy is simple: firms will always choose the nodes with the highest and second-highest degrees (number of connections), unless the highest-degree node is so dominant that it exceeds twice the centrality of the next best option.

Critical Analysis & Conclusion

The value of this paper lies in its bridge between Graph Theory and Game Theory. By introducing "Cascade Centrality," it moves beyond simple degree-counting and looks at the global structure of probabilities.

Limitations:

• Unit Budgets: The current findings primarily focus on each firm having only one seed. Real-world marketing campaigns involve hundreds.
• Static Thresholds: The model assumes thresholds are drawn from a uniform distribution $U(0,1)$. In reality, human resistance to rumors is often biased by the content's sentiment.

Takeaway: If you are seeding a rumor in a competitive environment, don't just look for the most connected person; look for the person whose "Cascade Centrality" is at least double that of anyone else to ensure a stable, dominant position.