  The idea of social advertising (or social promotion) is to select a group of
influential individuals (a.k.a \emph{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.
