On the Efficiency of Influence-and-Exploit Strategies for Revenue Maximization under Positive Externalities

Details On the Efficiency of Influence-and-Exploit Strategies for Revenue Maximization under Positive Externalities On the Efficiency of Influence-and-Exploit Strategies for Revenue Maximization under Positive Externalities

2011-10-10

arxiv.org/abs/1110.1894v1

Computer Science

Data Structures and Algorithms

21 pages, 5 figures

Scientific paper

We study the problem of revenue maximization in the marketing model for social networks introduced by (Hartline, Mirrokni, Sundararajan, WWW '08). We restrict our attention to the Uniform Additive Model and mostly focus on Influence-and-Exploit (IE) marketing strategies. We obtain a comprehensive collection of results on the efficiency and the approximability of IE strategies, which also imply a significant improvement on the best known approximation ratios for revenue maximization. Specifically, we show that in the Uniform Additive Model, both computing the optimal marketing strategy and computing the best IE strategy are $\NP$-hard for undirected social networks. We observe that allowing IE strategies to offer prices smaller than the myopic price in the exploit step leads to a measurable 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 networks. Moreover, we present a natural generalization of IE strategies, with more than two pricing classes, and show that they approximate the maximum revenue within a factor of roughly 0.7 for undirected and of roughly 0.35 for directed 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, by Hartline et al.).

Affiliated with

Also associated with

No associations

Rating

On the Efficiency of Influence-and-Exploit Strategies for Revenue Maximization under Positive Externalities does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Efficiency of Influence-and-Exploit Strategies for Revenue Maximization under Positive Externalities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Efficiency of Influence-and-Exploit Strategies for Revenue Maximization under Positive Externalities will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-146251