Optimal marketing strategies over social networks

ABSTRACT

We discuss the use of social networks in implementing viral marketing strategies. While influence maximization has been studied in this context (see Chapter 24 of [10]), we study revenue maximization, arguably, a more natural objective. In our model, a buyer's decision to buy an item is influenced by the set of other buyers that own the item and the price at which the item is offered.

We focus on algorithmic question of finding revenue maximizing marketing strategies. When the buyers are completely symmetric, we can find the optimal marketing strategy in polynomial time. In the general case, motivated by hardness results, we investigate approximation algorithms for this problem. We identify a family of strategies called influence-and-exploit strategies that are based on the following idea: Initially influence the population by giving the item for free to carefully a chosen set of buyers. Then extract revenue from the remaining buyers using a 'greedy' pricing strategy. We first argue why such strategies are reasonable and then show how to use recently developed set-function maximization techniques to find the right set of buyers to influence.

REFERENCES

• 1: Lars Backstrom , Dan Huttenlocher , Jon Kleinberg , Xiangyang Lan, Group formation in large social networks: membership, growth, and evolution, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150412]
• 2: Barlow, Richard E. and Marshall, Albert W. Bounds for distributions with monotone hazard rate, i. The Annals of Mathematical Statistics, 35(3):1234--1257, sep 1964.
• 3: Barlow, Richard E. and Marshall, Albert W. Bounds for distributions with monotone hazard rate, ii. The Annals of Mathematical Statistics, 35(3):1258--1274, sep 1964.
• 4: Bonnie Berger , Peter W. Shor, Approximation alogorithms for the maximum acyclic subgraph problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.236-243, January 22-24, 1990, San Francisco, California, United States
• 5: Luis Cabral, David Salant, and Glenn Woroch. Monopoly pricing with network externalities. Industrial Organization 9411003, EconWPA, November 1994.
• 6: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 7: Uriel Feige , Vahab S. Mirrokni , Jan Vondrak, Maximizing Non-Monotone Submodular Functions, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.461-471, October 21-23, 2007 [doi>10.1109/FOCS.2007.40]
• 8: Refael Hassin , Shlomi Rubinstein, Approximations for the maximum acyclic subgraph problem, Information Processing Letters, v.51 n.3, p.133-140, Aug. 10, 1994 [doi>10.1016/0020-0190(94)00086-7]
• 9: David Kempe , Jon Kleinberg , Éva Tardos, Maximizing the spread of influence through a social network, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956769]
• 10: J. Kleinberg. Cascading behavior in networks: algorithmic and economic issues. Cambridge University Press, 2007.
• 11: Jay Meattle. http://blog.compete.com/2007/01/25/top-20-websites-ranked-by-time-spent/.
• 12: R. Myerson. Optimal auction design. Mathematics of Operations Research, 6(1):58--73, 1981.
• 13: G. Nemhauser, L. Wolsey, and M. Fisher. An analysis of the approximations for maximizing submodular set functions. Mathematical Programming, 14:265--294, 1978.
• 14: Alantha Newman, The Maximum Acyclic Subgraph Problem and Degree-3 Graphs, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.147-158, August 18-20, 2001
• 15: Ed Oswald. http://www.betanews.com/article/Google_Buy_MySpace_Ads_for_900m/1155050350.
• 16: Everett Rogers. Diffusion of Innovations, 5th Edition. Free Press, August 2003.
• 17: Pekka Sääskilahti. Monopoly pricing of social goods. MPRA Paper 3526, University Library of Munich, Germany, 2007.
• 18: Katharine Q. Seeyle.
• 19: Rob Walker. http://www.slate.com/id/1006264/.
• 20: Tim Weber. http://news.bbc.co.uk/1/hi/business/6305957.stm?lsf.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Algorithms, Economics, Theory

Keywords:
marketing, monetizing social networks, pricing, submodular maximization