2011/10/09 by Dimitris Fotakis, Fotakis, Dimitris, Paris Siminelakis +1 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Game Theory and Applications #Optimization and Search Problems #Social and Information Networks (cs.SI) #Spam and Phishing Detection
paper · pdf · doi:10.48550/arxiv.1110.1894
openalex publication_date 2011/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of revenue maximization in the marketing model for\nsocial networks introduced by (Hartline, Mirrokni, Sundararajan, WWW '08). We\nrestrict our attention to the Uniform Additive Model and mostly focus on\nInfluence-and-Exploit (IE) marketing strategies. We obtain a comprehensive\ncollection of results on the efficiency and the approximability of IE\nstrategies, which also imply a significant improvement on the best known\napproximation ratios for revenue maximization. Specifically, we show that in\nthe Uniform Additive Model, both computing the optimal marketing strategy and\ncomputing the best IE strategy are NP-hard for undirected social networks.\nWe observe that allowing IE strategies to offer prices smaller than the myopic\nprice in the exploit step leads to a measurable improvement on their\nperformance. Thus, we show that the best IE strategy approximates the maximum\nrevenue within a factor of 0.911 for undirected and of roughly 0.553 for\ndirected networks. Moreover, we present a natural generalization of IE\nstrategies, with more than two pricing classes, and show that they approximate\nthe maximum revenue within a factor of roughly 0.7 for undirected and of\nroughly 0.35 for directed networks. Utilizing a connection between good IE\nstrategies and large cuts in the underlying social network, we obtain\npolynomial-time algorithms that approximate the revenue of the best IE strategy\nwithin a factor of roughly 0.9. Hence, we significantly improve on the best\nknown approximation ratio for revenue maximization to 0.8229 for undirected and\nto 0.5011 for directed networks (from 2/3 and 1/3, respectively, by Hartline et\nal.).\n