Adaptive discount allocation in social networks

It has been reported that 40% of consumers will share an email offer with their friend and 28% of consumers will share deals via social media platforms. This motivates us to study the influence maximization discount allocation problem: given a social network and a limited marketing budget, which set of initial users should be selected to receive the discount, and how much should the discounts be worth? Our goal is to maximize the number of customers who finally adopt the target product. We investigate this problem under both non-adaptive and adaptive settings. In the first setting, we have to commit the set of initial users and corresponding discounts all at once in advance. In the latter case, given that an user has been offered a discount, we are able to know immediately her decision on whether or not to accept that discount, therefore, the decision process is performed in a sequential manner based on the feedback from previously selected users. We propose a simple greedy policy with an approximation ratio of (1-1/e) in non-adaptive setting. For the significantly more complex adaptive setting, we propose a series of adaptive policies with bounded approximation ratio in terms of expected utility.