Optimizing Ad Allocation in Social Advertising

Social advertising (or social promotion) is an effective approach that produces a significant cascade of adoption through influence in the online social networks. The goal of this work is to optimize the ad allocation from the platform's perspective. On the one hand, the platform would like to maximize revenue earned from each advertiser by exposing their ads to as many people as possible, one the other hand, the platform wants to reduce free-riding to ensure the truthfulness of the advertiser. To access this tradeoff, we adopt the concept of \emph{regret} \citep{viral2015social} to measure the performance of an ad allocation scheme. In particular, we study two social advertising problems: \emph{budgeted social advertising problem} and \emph{unconstrained social advertising problem}. In the first problem, we aim at selecting a set of seeds for each advertiser that minimizes the regret while setting budget constraints on the attention cost; in the second problem, we propose to optimize a linear combination of the regret and attention costs. We prove that both problems are NP-hard, and then develop a constant factor approximation algorithm for each problem.