The Price of Influence: Solving the Pricing Game in Sponsored Viral Marketing

TL;DR

In the world of sponsored viral marketing, celebrities and "spreaders" aren't just passive nodes; they are rational actors who set their own prices. This paper explores how an advertiser’s selection algorithm (Omniscient, Simple-Greedy, or Double-Greedy) dictates the stability of the market. The big reveal? The popular Simple-Greedy algorithm fails to reach a price equilibrium when more than three influencers are involved, but a Double-Greedy approach guarantees a stable market and predictable profits.

Context: When Everyone is a Seller

Emerging platforms allow anyone to register as a spreader with self-claimed prices. This creates a complex triangular relationship between Sponsors (who pay), Platforms (who select), and Spreaders (who influence). The core tension is a pricing game: a spreader wants to charge a high price to maximize profit but risks being excluded by the advertiser if the price exceeds the marginal value of their influence.

The Core Problem: Instability in Selection

The "Influence Maximization Problem" (IMP) usually assumes a fixed budget or a fixed number of spreaders. In a profit-maximizing scenario, the advertiser wants to maximize: $u_a=\sigma (S)-{\sum }_{i\in S}{p}_i$ where $\sigma (S)$ is the expected activations.

The difficulty is that this utility function is non-monotone. Adding a spreader might increase influence but decrease total profit if their price is too high. Traditional greedy algorithms often struggle with this lack of monotonicity, leading to scenarios where spreaders can "game" the system, preventing the market from reaching a Nash Equilibrium (NE)—a state where no one can improve their profit by changing their price.

Methodology: Testing the Selection Policies

The authors analyze three advertiser behaviors:

1. The Omniscient Advertiser ($X_o$)

This ideal advertiser always finds the mathematically optimal set.

• Result: A unique NE exists where every spreader claims exactly their unique influence ($\sigma (T)-\sigma (T\setminus \{i\})$). Competition is so fierce that spreaders get no "extra" profit.

2. The Simple-Greedy Advertiser ($X_s$)

This advertiser picks the best available spreader one by one until no positive marginal utility remains.

• The Failure: While it works for 2 or 3 spreaders, for 4 or more, the authors prove that an NE might not exist. Influencers can constantly undercut or skip each other, leading to a perpetual cycle of price changes.

Figure 1: The general framework of sponsored viral marketing.

3. The Double-Greedy Advertiser ($X_d$)

Based on the Buchbinder et al. algorithm, this policy processes spreaders in a fixed order and maintains two sets (one starting empty, one starting full) to balance the marginal gains.

• The Breakthrough: This policy guarantees a unique Nash Equilibrium regardless of the number of spreaders.
• Pricing Mechanics: In this equilibrium, the price is set as: ${\varphi }_i=\frac{{\delta }_i+\sigma (t_i|S_{i-1})}{2}$ where ${\delta }_i$ is unique influence and $S_{i-1}$ is the set of previously processed spreaders.

Experimental Insights: Profit Guarantees

The study doesn't just prove existence; it proves value. Under the Double-Greedy equilibrium:

• Social Welfare: The Price of Anarchy is 1, meaning the maximal total influence $\sigma (T)$ is always achieved.
• Advertiser Profit: The advertiser is guaranteed a profit at least 1/2 of the optimal profit ($u_a(S^{\ast })$).

Figure 2: Topologies used to prove the non-existence of NE in Simple-Greedy systems with 4+ spreaders.

Critical Analysis & Conclusion

Takeaway

The research highlights a critical "algorithmic vulnerability" in simple greedy platforms. If a platform like Facebook or a third-party ad agency uses a standard greedy selection, they risk a volatile market where influencers cannot settle on stable prices. Transitioning to a Double-Greedy framework provides the mathematical "anchor" needed for market stability.

Limitations

• Cost Assumption: The paper assumes the private cost of promotion for the spreader is near zero ($c_i\approx 0$). In reality, producing content has significant costs.
• Knowledge Requirements: It assumes spreaders know the advertiser's policy and the influence values of their peers, which is a high bar for information transparency.

Future Work

The next frontier is incorporating stochastic arrivals of spreaders and arbitrary private costs, moving from a static game to a dynamic, real-time marketplace.