Pricing Social Visibility Service in Online Social Networks: Modeling and Algorithms

Online social networks (OSNs) such as YouTube, Instagram, Twitter, Facebook, etc., serve as important platforms for users to share their information or content to friends or followers. Oftentimes, users want to enhance their social visibility, as it can make their contents, i.e., opinions, videos, pictures, etc., attract attention from more users, which in turn may bring higher commercial benefits to them. Motivated by this, we propose a mechanism, where the OSN operator provides a
“social visibility boosting service”
to incentivize “transactions” between requesters (users who seek to enhance their social visibility via adding new “neighbors”) and suppliers (users who are willing to be added as a new “neighbor” of any requester when certain “rewards” is provided). We design a posted pricing scheme for the OSN provider to charge the requesters who use such boosting service and reward the suppliers who make contributions. The OSN operator keeps a fraction of the payment from requesters and distributes the remaining part to participating suppliers
“fairly”
via a rewarding rule based on Shapley value. We consider two different objectives/problems of the OSN provider, i.e., to select the optimal prices and supplier set to maximize (1) the revenue or (2) the welfare increase, under the requesters' budget constraint on suppliers. We first show that the problems are not simpler than NP-hard. We then decomposed each problem into two sub-routines, where one focuses on selecting the optimal set of suppliers, and the other one focuses on selecting the optimal prices. We prove the hardness of each sub-routine, and eventually design a computationally efficient approximation algorithm to solve the problems with provable theoretical guarantee on the revenue/welfare increase gap. We conduct extensive experiments on four public datasets to validate the performance of our proposed algorithms.