tailieunhanh - Optimal Marketing Strategies over Social Networks

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. | Optimal Marketing Strategies over Social Networks Jason Hartline Electrical Engineering and Computer Science Northwestern University Evanston IL 60208 hartline@eecs. Vahab S. Mirrokni Microsoft Research One Microsoft Way Redmond W 98052 mirrokni@theory. Mukund Sundararajant Stanford University mukunds@ 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. Categories and Subject Descriptors Theory of Computation Analysis of Algorithms and Problem Complexity Computer Applications Social and Behavioral Sciences Economics General Terms Algorithm Theory and Economics. Keywords Pricing Monetizing Social Networks Marketing and Sub-modular Maximization. Work done while author was at Microsoft Research Silicon Valley. Work done while author was an intern at Microsoft Research. Copyright is held by the International World Wide Web Conference