# Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret

arXiv: https://arxiv.org/abs/1412.1462 · HTML: https://mlsanity.com/paper/1412.1462/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2014.

## Built on by (most cited first, 5 of 5)

- [Learning Ideological Embeddings from Information Cascades](https://mlsanity.com/paper/2109.13589/) (2021)
- [Engagement-Driven Content Generation with Large Language Models](https://mlsanity.com/paper/2411.13187/) (2024)
- [Submodular Optimization Beyond Nonnegativity: Adaptive Seed Selection in Incentivized Social Advertising](https://mlsanity.com/paper/2109.15180/) (2021)
- [Jointly Complementary&Competitive Influence Maximization with Concurrent Ally-Boosting and Rival-Preventing](https://mlsanity.com/paper/2302.09620/) (2023)
- [Towards Regret Free Slot Allocation in Billboard Advertisement](https://mlsanity.com/paper/2401.16464/) (2024)

## Abstract (arXiv)

In this paper, we study the problem of allocating ads to users through the viral-marketing lens. Advertisers approach the host with a budget in return for the marketing campaign service provided by the host. We show that allocation that takes into account the propensity of ads for viral propagation can achieve significantly better performance. However, uncontrolled virality could be undesirable for the host as it creates room for exploitation by the advertisers: hoping to tap uncontrolled virality, an advertiser might declare a lower budget for its marketing campaign, aiming at the same large outcome with a smaller cost. This creates a challenging trade-off: on the one hand, the host aims at leveraging virality and the network effect to improve advertising efficacy, while on the other hand the host wants to avoid giving away free service due to uncontrolled virality. We formalize this as the problem of ad allocation with minimum regret, which we show is NP-hard and inapproximable w.r.t. any factor. However, we devise an algorithm that provides approximation guarantees w.r.t. the total budget of all advertisers. We develop a scalable version of our approximation algorithm, which we extensively test on four real-world data sets, confirming that our algorithm delivers high quality solutions, is scalable, and significantly outperforms several natural baselines.