The pricing game of celebrities in sponsored viral marketing in online social networks

Abstract

After decades of rapid development, online social network (OSN) nowadays is not just a fundamental communication medium, but also an effective platform to conduct advertisement campaign. With detailed demographic information, advertisers are able to deliver their adverts to target users directly. To further exploit the potential of OSN, a new kind of advertisement has emerged, called sponsored viral marketing. It tries to capitalize on the diffusion of information in OSN. Originating from a group of ‘celebrities’, who are selected and sponsored by the advertiser or the OSN platform, adverts are spread out ‘virally’ to enormous number of OSN users. To effectively conduct this advertisement campaign, three aspects need to be studied, namely, the information diffusion model, the celebrity selection process, and the payment for promoting adverts. This thesis is concerned with these three aspects and mainly addresses the last issue.

Firstly, the problem of how information propagates in OSN is studied. Based on the prevalent Independent Cascade model, the Cascade with Varying Activation Probability (CVAP) model is proposed to incorporate the phenomenon that the activation probability (the probability that a user get influenced) varies with the number of previous activations. A real dataset crawled from Renren.com was used to demonstrate the variation and further validate the accuracy of the CVAP model.

The second part investigates how to properly select celebrities to maximize the influence spread. It is also known as the influence maximization problem. Under the CVAP model, submodularity is shown to be preserved. Then based on the submodularity, simple greedy algorithm is proved to achieve an approximation of 1 - 1/e. Various acceleration techniques can be used to make the algorithm more efficient to large scale networks.

Finally, the thesis addresses the pricing problem for celebrities in sponsored viral marketing. The problem is modeled as a pricing game, in which celebrities propose their prices to the platform and got paid accordingly. With a platform adopting a simple greedy algorithm, it is proved that if there are more than three celebrities in the game, pure Nash Equilibrium is not guaranteed to exist, rendering the algorithm ineffective. A sophisticated greedy algorithm, called double greedy algorithm is thus introduced. With a platform adopting the double greedy algorithm, pure Nash Equilibrium exists and is also unique. Moreover, it is proved that the utility of the platform is guaranteed to be 1/2 optimal in the equilibrium state, and its tight upper bound is 1/2 of the maximum influence spread.