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, on the other hand, the platform wants to reduce free-riding to ensure the truthfulness of the advertiser. To this end, we introduce a utility function that can access the above tradeoff. Based on this utility function, we define and study two social advertising problems: budgeted social advertising problem and unconstrained social advertising problem. In the first problem, we aim at selecting a set of seeds for each advertiser that maximizes the utility while setting budget constraints on the attention cost; in the second problem, we propose to optimize a linear combination of the utility and attention costs. We prove that both problems are NP-hard, and then develop constant factor approximation algorithms for both problems.