The Host’s Dilemma: Ensuring Fair "Bang for the Buck" in Competitive Viral Marketing

Executive Summary

Viral marketing is no longer a solo sport. On platforms like Facebook or Twitter, multiple brands (e.g., Xbox vs. PlayStation) compete for the same pool of users. "The Bang for the Buck" shifts the perspective from the advertiser to the Host—the platform owner. The core challenge? How to allocate influential "seed" users to competing clients so that everyone gets a fair return on their investment. This paper introduces the K-LT model and the Needy Greedy algorithm, ensuring that no advertiser feels cheated by the network’s inherent biases.

Problem & Motivation: Why Fairness Matters

In the real world, brands don't have access to the full social graph due to privacy and proprietary reasons; they buy "Influence as a Service" from the host. If a host allocates high-impact seeds to Nikon but low-impact seeds to Canon despite similar budgets, the "Bang for the Buck" (Amplification Factor) becomes skewed.

Existing models like WPCLT were fundamentally "broken"—adding more seeds could actually decrease a brand's total spread (non-monotone). The authors realized that a robust model must preserve the mathematical elegance of submodularity while handling the cutthroat nature of competition.

Methodology: The K-LT Model & Needy Greedy

The authors propose the K-LT (K-color Linear Threshold) model. It splits adoption into two logical steps:

1. Influence Phase: A node becomes "influenced" when the total weight from active neighbors hits a random threshold (classic LT).
2. Adoption Phase: The node picks a specific brand based on the most recent influence it received.

The Secret Sauce: Adjusted Marginal Gain

To solve the allocation problem, the authors define Adjusted Marginal Gain (${\delta }_u$). This value represents the specific contribution of a seed $u$ to the total network spread, independent of which specific brand it is assigned to.

The Needy Greedy Algorithm

Since Fair Seed Allocation (FSA) is NP-hard (reducible from the 3-PARTITION problem), the authors developed Needy Greedy. It works by:

• Sorting all selected seeds by their Adjusted Marginal Gain.
• Iteratively giving the next best seed to the "neediest" company (the one currently having the lowest amplification factor).

Experiments & Results

The researchers tested their approach on Epinions, Flixster, and NetHEPT. The results were stark:

• Performance: The Needy Greedy algorithm's relative error in fairness was nearly negligible (often <1% in 2-player games).
• Scalability: While Dynamic Programming (DP) offers the theoretical optimum for $K=2$, Needy Greedy is three orders of magnitude faster and works for any number of competitors.

Figure: The Box-and-whisker diagram shows how Needy Greedy tightly clusters amplification factors around the theoretical optimum (green line).

Critical Insight & Future Outlook

This work highlights a critical shift in AI for social networks: moving from Optimization (maximizing spread) to Mechanism Design (maximizing fairness and client satisfaction).

Limitations: The current model assumes all products have equal "virality." In the future, a "Better Product" (higher intrinsic weight) should logically achieve a higher amplification factor. Incorporating varying product quality into the K-LT framework is the next frontier for fair viral marketing.

Takeaway for Architects

If you are building a recommendation or advertising engine for a multi-sided marketplace, you cannot simply optimize for the global maximum. You must account for inter-client fairness, or your most valuable advertisers will eventually churn.