Pricing social visibility service in online social networks
Shiyuan Zheng, Hong Ling Xie, John C. S. Lui · 2021
In online social networks (OSNs), users may want to enhance their social visibility, as it can make their contents, i.e., opinions, videos, pictures, etc., attract attention from more users. 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 contribute to such boosting service. The OSN operator keeps a fraction of the payment from requesters and distributes the remaining part to participating suppliers "fairly" via a scheme based on the Shapley value. The objective of the OSN provider is to select the price and supplier set to maximize the revenue under the budget constraint of requesters. We first show that the revenue maximization problem is not simpler than an NP-hard problem. We then decompose it into two subroutines, prove the hardness of each sub-routine, and eventually design computationally efficient approximation algorithms to solve the revenue maximization problem. We conduct extensive experiments to evaluate our proposed algorithms.