The Celebrity Pricing Game: When Greedy Platforms Meet Strategic Influencers

TL;DR

In the world of sponsored viral marketing, how much should a social media star charge for a "promoted tweet"? This paper moves beyond traditional Influence Maximization (IM) by treating seed nodes as rational players in a Pricing Game. The core finding reveals a paradox: while simple markets with 2-3 influencers reach a stable price, larger markets involving 4 or more influencers may never reach a technical "equilibrium" because the platform's greedy selection habits are easily exploited.

Context: Beyond Influence Maximization

Traditionally, researchers treated influencers as "nodes" to be activated. But in the real economy, influencers like those on Instagram or WeChat are agents who set prices. Previous work assumed platforms were "omniscient"—optimal at choosing the best set of stars. This paper brings the theory down to earth by assuming the platform is greedy, iteratively picking whoever provides the best immediate ROI.

The Problem: The Heuristic Loophole

In IM, the platform's utility is submodular (diminishing returns). Adding a second celebrity often provides less "new" reach than the first.

• The Problem: Because the selection problem is NP-hard, platforms use a greedy shortcut.
• The Intuition: The authors show that this greedy behavior creates a "myopia" that influencers can exploit. If an influencer knows exactly how the greedy algorithm thinks, they can raise their price just enough to still be "the best immediate pick" even if they aren't part of the globally optimal set.

Methodology: Analyzing the Equilibrium

The authors define the marginal unique influence ($\delta$) as the bottom-line value of a celebrity.

The 3-Player Dynamics

With three players, the authors prove that a "Stability" exists. Interestingly, the celebrity who is the "most non-substitutable" (having the least overlap with others) can extract a price higher than their unique marginal influence.

In Figure 2, the overlapping circles represent shared influence. The paper calculates $\alpha$ values to determine who holds the most bargaining power.

The Breakdown at Scale (4+ Players)

Using a real-world Twitter subgraph (81,306 nodes), the authors tested whether prices ever settle down when 4 celebrities compete. They found that in many cases, they don't. As one celebrity raises their price, the greedy platform switches its selection order, causing another celebrity to lose out, who then changes their price, leading to an endless cycle of instability.

Experiments and Chaos

The researchers used one-hop node coverage as a proxy for influence. Their analysis of the Twitter dataset showed that out of 24 possible selection sequences for a 4-player set, none of the candidate price vectors satisfied the conditions for a Pure Nash Equilibrium.

Fig 1: A rare case where PNE actually exists due to a highly structured network of ordinary users (Nodes o5-o7).

Critical Insight: The Cost of Simplicity

Why does this matter? Most advertising platforms (like Google GSP or Facebook’s ad auctions) prefer simplicity over perfect mathematical optimality. This paper proves a hidden cost to that simplicity: Market Volatility.

Takeaways:

1. Platform Myopia: Greedy algorithms are easier to implement but allow influencers to monetize "extra" power through strategic pricing.
2. Market Limits: Pure stability in influencer pricing is mathematically fragile. As the pool of available celebrities grows, the likelihood of finding a stable price point vanishes.
3. Future Direction: To fix this, platforms might need more sophisticated selection strategies like "Double Greedy" or "Local Search" to prevent strategic manipulation by savvy influencers.

Conclusion

This work bridges the gap between social network theory and algorithmic game theory. It suggests that the "word-of-mouth" economy isn't just about who follows whom, but about the high-stakes game of how influencers price their reach in the eyes of a myopic middleman.