Beyond Monopoly: Understanding the Dynamics of Competitive Social Influence

TL;DR

When companies compete for viral dominance on social media, the math changes. This paper explores what happens when we combine classic models like the Voter Model and Logit Dynamics into a two-phase framework (Deciding to buy vs. Deciding which brand). The verdict? Most common "greedy" strategies fail when people have hard thresholds for adoption, but stochastic models remain surprisingly efficient.

Background: The Shift to Multi-Agent Competition

For over a decade, Influence Maximization (IM) research has focused on the "monopolist" view: how one brand reaches the most people. But in reality, brands like Coke and Pepsi, or iOS and Android, fight for the same finite pool of users. This paper moves the needle by analyzing Competitive Contagion, specifically building on the Goyal-Kearns framework to see if standard AI optimization tools still work when the "enemy" is also seeding the network.

The Problem: The Complexity of Choice

Most prior work assumes a simple spread mechanism. The authors identify a gap: real behavior is a two-step process.

1. Activation (AR): Does the user care enough about the product category to join in? (e.g., "Do I need a smartphone?")
2. Selection (SR): If active, which brand do they pick? (e.g., "iPhone or Galaxy?")

The difficulty lies in whether combining these two steps preserves the "nice" mathematical properties—like submodularity—that allow us to use simple algorithms to find the best influencers.

Methodology: Composing Dynamics

The researchers tested combinations of three heavyweight models:

• General Threshold (GT): You only act if a certain percentage of friends do.
• Voter Model (VOT): You pick a random friend and copy them.
• Logit Model (LOG): A probabilistic choice based on "utility" or pressure.

The Two-Phase Framework

The researchers analyzed how these dynamics converge over time. They specifically looked for the Stationary Distribution—the long-term "steady state" of who owns which part of the market.

Figure 1: Summary of convergence and decomposition for various AR/SR combinations.

Key Insights: Why Your Greedy Strategy Might Fail

One of the paper's most significant contributions is testing Submodularity (the law of diminishing returns). In a single-player world, adding one more influencer always helps, but each additional one helps slightly less than the previous one. This property allows the Greedy Algorithm to be highly effective.

However, the authors found that for General Threshold (GT) activation:

• Submodularity is lost (Table 1b).
• This means the standard practice of "just picking the next best node" can be wildly suboptimal in a competitive market.

Figure 2: Results on Submodularity (left) and Efficiency/Price of Anarchy (right).

Experimental Findings & Efficiency

Does competition ruin everything? The Price of Anarchy (PoA) measures how much "total adoption" is lost because firms compete instead of cooperating.

• For Logit-based models, the PoA is constant (Yes in Table 1c). Competition doesn't hurt the total market size much.
• For Threshold-based models, the outcome is "No"—competition can lead to significantly fewer people adopting any product at all compared to a monopoly.

Critical Analysis & Future Outlook

This work serves as a warning to practitioners: Context matters. If you are modeling a product with a hard social threshold (like a peer-pressure-based app), you cannot rely on simple greedy heuristics for viral marketing if a competitor is present.

Limitations: The model assumes static networks and specific "stationary" states. Real social media is much more fluid and transient. Future Work: The "Open" result in Table 1b (Logit AR + Voter SR) remains a theoretical mystery—a perfect opportunity for new researchers to bridge the gap between stochastic choice and linear influence models.

Summary Takeaway

If your market follows "Threshold" logic, competition makes optimization unpredictable. If it follows "Logit" (probabilistic) logic, the market is resilient, and greedy strategies still mostly work.