Competitive Diffusion: Why Social Network Diameter Dictates Stability

TL;DR

When competing for influence on a social network, do firms ever reach a professional "truce" where no one wants to change their strategy? This paper proves that the answer depends almost entirely on the diameter of the network. If everyone is just two hops away (Diameter ≤ 2), an equilibrium is guaranteed. If the network is more stretched (Diameter ≥ 3), strategic chaos can ensue.

Background: Viral Marketing as a Zero-Sum Game

Traditional models of "viral marketing" often treat the problem as an optimization task: how do I pick the best 10 people to start a trend? However, in the real world, you aren't alone. When Samsung and Apple both target the same influencers, they don't just add up; they often cancel each other out.

This paper shifts the perspective from the users inside the network to the external players (agents) competing for real estate. It introduces a "competitive diffusion" model where:

• Each agent picks one start node.
• Influence spreads step-by-step.
• If two competing influences hit a node at the same time, the node becomes Gray (neutralized) and stops spreading any color.

The "Small World" Guarantee: Diameter ≤ 2

The most striking find is that for graphs where the maximum distance between any two nodes is 2, a Pure Nash Equilibrium (PNE) always exists. To prove this, the authors utilize a "Potential Function."

The Logic of the Potential Function

A potential function $\Phi (\mathbf{x})$ is a global "score" of the game's state. If a player changes their strategy and improves their own utility, the global score must also increase. Because the score cannot increase forever (the graph is finite), the game must eventually hit a peak—an Equilibrium.

The authors defined the potential as: $\Phi (\mathbf{x})=|N(\mathbf{x})|\cdot n+P(\mathbf{x})$ Where:

• $|N(\mathbf{x})|$ is the total number of unique neighbors reached.
• $P(\mathbf{x})$ is the number of pairs of agents who are adjacent.

In a diameter-2 graph, the "collision" of influences happens almost immediately. This limited horizon makes the game strategically "stable." Since many social networks exhibit "small-world" properties (low diameter), this suggests that many real-world competitive scenarios are naturally stable.

Fig 1: Illustration of the diffusion process. When two colors reach a white node simultaneously, it turns gray.

The Breaking Point: Diameter ≥ 3

Once the diameter hits 3, the guarantee vanishes. The authors prove this by "adversarial construction"—designing a complex graph (156 nodes) with "hubs" and "cliques" where two players will infinitely chase each other's tail, constantly deviating to better positions but never finding a stable state.

Fig 2: The complex construction used to prove that Diameter 3 allows for non-equilibrium states.

Why does it break?

In a larger network, players can "hide" or "ambush" each other in different branches of the graph. The immediate feedback loop present in Diameter-2 graphs is lost, allowing for cyclic preferences (A beats B, B beats C, C beats A).

Critical Insight & Takeaways

1. Inductive Bias of Networks: Almost all random graphs ($G_{n,p}$) have a diameter of 2 under standard conditions. This implies that in random or highly connected systems, competitive influence is mathematically predictable.
2. Strategic Complexity: The lack of equilibrium in $D=3$ graphs warns us that in structured, hierarchical, or sparse networks (like some corporate or biological networks), "Optimal Viral Marketing" might be a moving target that never settles.
3. Limitations: The model assumes players pick only one starting node and the spread is deterministic. In reality, firms pick many seeds, and spread is probabilistic. Extending this potential function to "Multi-node Strategies" is the next logical frontier for this research.

Conclusion: This paper provides a crucial theoretical boundary for Algorithmic Game Theory. It tells us that the "topology" of our social connections isn't just about how fast information spreads—it's about whether competition can ever reach a point of stability.