RMA: Breaking the Efficiency Bottleneck in Multi-Advertiser Social Advertising

TL;DR

The Revenue Maximization (RM) problem in social advertising involves selecting optimal "seed users" for multiple advertisers to maximize total platform revenue under strict budget and social constraints. This paper introduces RMA, an algorithm that replaces instance-dependent (often poor) guarantees with near-constant approximation ratios. By combining a smart ThresholdGreedy approach with a Progressive Sampling mechanism, RMA delivers higher revenue and faster execution than previous state-of-the-art methods.

The Motivation: Why Current "Greedy" Isn't Enough

Social platforms like Facebook or Instagram use Cost-Per-Engagement (CPE) models. Advertisers pay not just for the initial "seed" user they incentivize, but for every "Like" or "Share" that happens as the ad spreads virally.

The technical challenge is a "Submodular Maximization" problem under complex constraints. Previous solutions (like TI-CSRM) had a major flaw: their mathematical guarantees depended on the specific network structure. In the worst-case scenario (e.g., specific "star" or "string" topologies), their performance could drop to near zero. Moreover, they were "budget-shy"—they often stopped selecting seeds too early because they couldn't accurately estimate the remaining budget in real-time.

The Core Methodology: Thresholds & Better Sampling

1. ThresholdGreedy & Binary Search

Instead of a simple greedy pick, the authors propose a ThresholdGreedy algorithm. It only selects a node if its "Marginal Rate" (Revenue Gain / Total Cost) exceeds a specific threshold $\gamma$. To find the perfect $\gamma$, the authors use a Binary Search process. This ensures that the platform doesn't deplete its budget too quickly on high-cost nodes that offer low viral potential, leading to a performance ratio ($\lambda$) that is essentially a constant for a given number of advertisers.

2. Unified RR-Set Generation

Estimating influence spread is #P-hard. Most modern algorithms use Reverse-Reachable (RR) Sets. However, with multiple advertisers, traditional sampling is chaotic. RMA introduces a Uniform Sampling method:

1. Pick an advertiser $i$ proportional to their CPE.
2. Generate an RR-set specifically for that advertiser's topic interest. This mathematical "trick" allows for much tighter concentration bounds, meaning the algorithm needs fewer samples to reach a high-confidence decision.

Figure 1: The social advertising ecosystem involving a host (platform owner) and multiple budget-constrained advertisers.

Experimental Performance: Faster and More Profitable

The authors tested RMA against the current SOTA on four major datasets: LastFM, Flixster, DBLP, and LiveJournal.

• Revenue Boost: In the SuperLinear cost model (where popular influencers are disproportionately expensive), RMA significantly outperformed TI-CARM, which crashed in revenue because it ignored node costs.
• Computational Scalability: On the massive LiveJournal graph (69M edges), RMA finished execution significantly faster while maintaining a higher "Rate of Return"—meaning every dollar spent on seeding generated more engagement revenue compared to baselines.

Figure 2: RMA (red line) consistently achieves the highest revenue across different cost sensitivities ($\alpha$) compared to TI-CSRM and TI-CARM.

Critical Analysis & Takeaways

The beauty of RMA lies in its Bicriteria Approximation. It acknowledges that in reality, overshooting a budget slightly (by a factor of $1+\rho$) is often preferable to under-utilizing it significantly.

Limitations:

• Conflict of Interest: The model assumes a seed user can only endorse one ad. In reality, influencers often cross-promote multiple brands.
• Static Costs: The pricing of nodes is assumed to be fixed/known, whereas real-world influencer pricing is often dynamic and auction-based.

Future Outlook: The next frontier for this research is "Complementarity"—how the platform should allocate seeds when one advertiser's product (e.g., iPhone) might actually help another advertiser's product (e.g., Apple Watch) spread through the same network.

Summary

RMA is a significant step forward for computational advertising. It transforms a theoretical "hard" problem into a practical, scalable solution that ensures social media platforms can maximize their "Viral Revenue" without breaking the bank or the server.