Online Welfare Maximization of Sponsored Viral Marketing with Stochastically Arriving Spreaders

摘要

Selecting k seed users in online social networks (OSNs) as spreaders to publish advertisements so that the final information spread is maximized, is the well-studied influence maximization problem. Studies have been focusing on a static pool of potential spreaders and ignoring their autonomy. In fact, as influential users in OSN, spreaders may act at their own discretion. Their availabilities are affected by both their logging in time and their willingness to participate in a marketing campaign. From the perspective of the advertiser, spreaders arrive stochastically. Instead of selecting spreaders on their own, advertisers usually delegate the task to a professional advertising platform and simply buy impressions. Comparing to the short time that spreaders spend on publishing advertisements, multiple advertisers exist simultaneously and are relatively static with much longer durations. Therefore, it is the platform's responsibility to properly distribute advertisements to stochastically arriving spreaders, or equivalently, allocate spreaders to sponsors. The goal is to maximize the sum utilities of all parties, i.e. the social welfare. In this paper, we propose the online simple-greedy algorithm for such allocation problem. We prove the algorithm is guaranteed to achieve an expected welfare of at least 1-1/e to the expected offline optimum, and further show it is the best that a polynomial-time algorithm can achieve. Moreover, we discussed extensions with different diffusion models and also conduct experiments on real datasets to show the performance of the greedy algorithm.