# Submodular Optimization Beyond Nonnegativity: Adaptive Seed Selection in Incentivized Social Advertising

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 49 references that are in the map.
- First posted on arXiv 30 Sep 2021.

## Builds on (most cited first, 9 of 9)

- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Submodular Maximization Beyond Non-negativity: Guarantees, Fast Algorithms, and Applications](https://mlsanity.com/paper/1904.09354/) (2019)
- [Regularized Submodular Maximization at Scale](https://mlsanity.com/paper/2002.03503/) (2020)
- [Guess Free Maximization of Submodular and Linear Sums](https://mlsanity.com/paper/1810.03813/) (2018)
- [Botivist: Calling Volunteers to Action Using Online Bots](https://mlsanity.com/paper/1509.06026/) (2015)
- [Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret](https://mlsanity.com/paper/1412.1462/) (2014)
- [Revenue Maximization in Incentivized Social Advertising](https://mlsanity.com/paper/1612.00531/) (2016)
- [Optimizing Ad Allocation in Social Advertising](https://mlsanity.com/paper/1505.03235/) (2015)
- [Efficient and Effective Algorithms for Revenue Maximization in Social Advertising](https://mlsanity.com/paper/2107.04997/) (2021)

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

- [Procurement Auctions via Approximately Optimal Submodular Optimization](https://mlsanity.com/paper/2411.13513/) (2024)

## Abstract (arXiv)

The idea of social advertising (or social promotion) is to select a group of influential individuals (a.k.a seeds) to help promote some products or ideas through an online social networks. There are two major players in the social advertising ecosystem: advertiser and platform. The platform sells viral engagements such as "like"s to advertisers by inserting their ads into the feed of seeds. These seeds receive monetary incentives from the platform in exchange for their participation in the social advertising campaign. Once an ad is engaged by a follower of some seed, the platform receives a fixed amount of payment, called cost per engagement, from the advertiser. The ad could potentially attract more engagements from followers' followers and trigger a viral contagion. At the beginning of a campaign, the advertiser submits a budget to the platform and this budget can be used for two purposes: recruiting seeds and paying for the viral engagements generated by the seeds. Note that the first part of payment goes to the seeds and the latter one is the actual revenue collected by the platform. In this setting, the problem for the platform is to recruit a group of seeds such that she can collect the largest possible amount of revenue subject to the budget constraint. We formulate this problem as a seed selection problem whose objective function is non-monotone and it might take on negative values, making existing results on submodular optimization and influence maximization not applicable to our setting. We study this problem under both non-adaptive and adaptive settings. Although we focus on social advertising in this paper, our results apply to any optimization problems whose objective function is the expectation of the minimum of a stochastic submodular function and a linear function.