Elsevier

Theoretical Computer Science

Volume 539, 19 June 2014, Pages 68-86
Theoretical Computer Science

On the efficiency of Influence-and-Exploit strategies for revenue maximization under positive externalities

https://doi.org/10.1016/j.tcs.2014.04.026Get rights and content
Under an Elsevier user license
open archive

Abstract

The mitigated effectiveness of traditional forms of advertising along with winner-take-all phenomena caused by globalization and the Internet necessitates a new approach in marketing. Hartline et al. (2008) [16] introduced a marketing model for social networks, where a seller is trying to exploit positive externalities between the buyers and to maximize his revenue by designing an intelligent series of individualized offers. Under this setting, we study the problem of revenue maximization and mostly focus on Influence-and-Exploit (IE) marketing strategies. We show that in undirected social networks, revenue maximization is NP-hard not only when we search for an optimal marketing strategy, but also when we search for the best IE strategy. Rather surprisingly, we observe that allowing IE strategies to offer prices smaller than the myopic price in the exploit step leads to a significant improvement on their performance. Thus, we show that the best IE strategy approximates the maximum revenue within a factor of 0.911 for undirected and of roughly 0.553 for directed social networks. Utilizing a connection between good IE strategies and large cuts in the underlying social network, we obtain polynomial-time algorithms that approximate the revenue of the best IE strategy within a factor of roughly 0.9. Hence, we significantly improve on the best known approximation ratio for revenue maximization to 0.8229 for undirected and to 0.5011 for directed networks (from 2/3 and 1/3, respectively).

Keywords

Pricing
Externalities
Social network monetization
Influence and Exploit strategies

Cited by (0)

This research was supported by the project AlgoNow, co-financed by the European Union (European Social Fund – ESF) and Greek national funds, through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) – Research Funding Program: THALES, investing in knowledge society through the European Social Fund. Part of this work was done while P. Siminelakis was with the School of Electrical and Computer Engineering, National Technical University of Athens, Greece. An extended abstract of this work appeared in the Proceedings of the 8th International Workshop on Internet and Network Economics (WINE 2012), Paul W. Goldberg (Editor), Lecture Notes in Computer Science 7695, pp. 270–283, Springer, 2012.

1

This author is partially supported by a scholarship from the Onassis Foundation.