AARM: Balancing Virality and Truthfulness in Social Advertising

TL;DR

This paper addresses a critical conflict in social advertising: platforms want maximum ad exposure (revenue), but advertisers often "free-ride" by underreporting budgets to get viral reach for free. The authors introduce AARM (Ad Allocation with Regret Minimization), an algorithm that optimizes a specialized utility function to ensure ads stay close to declared budgets while respecting user "attention limits." It provides a 1/4-factor approximation and remains scalable even on networks with millions of nodes.

Background & Motivation: The Free-Rider Problem

In social platforms like Facebook or Twitter, "Promoted Posts" propagate through organic shares. Unlike traditional display ads, the final number of impressions is uncertain. If a post goes viral, the advertiser might receive 10x the engagements they paid for.

From an economic perspective, this creates a truthfulness issue. If an advertiser knows they might get "free" viral reaches, they are incentivized to declare a lower budget. This work treats this overshooting as "regret" for the platform and seeks to minimize it, essentially forcing the system to behave predictably.

Methodology: Shifting the Utility

The core innovation is the definition of a Utility Function $U(\mathcal{S})$. Instead of purely maximizing engagements, the utility is defined as:

• ${\alpha }_i\cdot {\sigma }_i(S_i)$ if the revenue is below the budget $B_i$.
• $2\cdot B_i-{\alpha }_i\cdot {\sigma }_i(S_i)$ if it exceeds the budget.

This "tent-shaped" function penalizes over-delivery. To solve this, the authors tackle two scenarios:

1. Budgeted Social Advertising: Hard limits on how many ads a single user sees (Individual Attention) and total seeds (Global Attention).
2. Unconstrained Social Advertising: Converting hard constraints into a penalty function (regularization).

High-Efficiency Estimation

To make this work on massive graphs, the authors use Reverse-Reachable (RR) set sampling. By utilizing the IMM (Influence Maximization via Martingales) scheme, they can estimate influence spread with high accuracy without the prohibitive cost of traditional Monte Carlo simulations.

The optimization targets both individual attention (user level) and overall platform limits.

Experiments & Performance

The researchers tested AARM on benchmark datasets including Epinions, Pokec, and LiveJournal (4.8M nodes, 69M edges).

1. Quality vs. Baselines

Typical greedy or random baselines often "overshoot" the budget significantly because they don't factor in the viral nature of the network. As shown in the results, AARM maintains high positive utility while baselines like IRIE or Myopic often drop into negative utility territory because they trigger cascades that far exceed the advertiser's willingness to pay.

Figure: AARM vs. Baselines. AARM maintains stable utility as attention budgets per user ($\kappa$) increase.

2. Scalability

On the LiveJournal dataset, AARM scales almost linearly. While previous heuristics like IRIE took over 50 hours for campaigns with 5+ advertisers, AARM completed the task in under an hour.

Figure: AARM consistently outperforms TIRM and IRIE in running time across diverse network sizes.

Critical Insight: The Value of "Regret"

The most striking takeaway is the transition from Influence Maximization (which is "more is better") to Regret Minimization (which is "exactness is better"). In a mature advertising ecosystem, predictability is more valuable than raw reach. By proving that this regret-based problem still possesses submodular properties (under specific transformations), the authors bridge the gap between social network theory and auction mechanism design.

Conclusion & Future Directions

AARM provides a robust framework for social platforms to manage multi-advertiser environments. It respects user experience (via attention budgets) and ensures advertisers can't "game" the system. Future work may look into Linear Threshold (LT) models, where adoption depends on the aggregate influence of multiple neighbors, rather than independent probabilities.