Report

Optimal Marketing Strategies over Social Networks Jason Hartline (Northwestern), Vahab Mirrokni (Microsoft Research) Mukund Sundararajan (Stanford) Network Affects Value JOHN JASON $20 zune VAHAB A person’s value for an item depends on others who own the item Network Affects Value JOHN JASON $30 zune VAHAB zune A person’s value for an item depends on others who own the item Examples Early phone system • Value proportional to #subscribers • Monthly fee doubles every year for first four years CompuServe • Initially, small sign up fee Standard Influence Models (See [Kempe+03], its citations) •Probability of adoption depends on who else has item No dependence on price •Maximize adoption: Which k players would you give item away to? Standard Optimal Pricing Set B of buyers No network effect or externalities Value vi drawn from distribution Fi Revenue(p) = p(1 - F(p)) pi* is optimal price, Ri is optimal revenue Contributions Propose model where adoption is based on price and network effects Study Revenue maximization Identify a family of strategies called influence and exploit strategies that are easy to implement and optimize over Problem Definition Given: a monopolist seller and set V of potential buyers digital goods (zero manufacturing cost) value of buyer for good vi = 2V R+ Problem Definition (cont.) Assumptions: buyer’s decision to buy an item depends on other buyers who own the item and the price seller does not know the buyer’s value function but instead has a distributional information about them Value with Network Effects Set B of buyers If set S of buyers has adopted, viS drawn from distribution FiS. Directed Graph Setting wii wji vi(S) = wii + ∑j in S wji Marketing Strategy Seller visits buyers in a sequence and offers each buyer a price Order and price can depend on history of sales Seller earns the price as revenue when buyer accepts Goal: maximize expected revenue Marketing Strategy: sequence of offer to buyers and the prices that we offer Question: algorithmic techniques? Upper Bound on Revenue viS drawn from distribution FiS Player specific revenue function Ri(S) Ri(S) is monotone ∑i Ri(B/i) is an upper bound on revenue Optimal price no longer optimal (myopic optimal price) Optimizing Symmetric Case vi(S) drawn from distr. Fk(k=|S|) Define: p*(#bought, #remain), E*(.,.) E(k, t) = (1 - Fk(p))[p + E*(k+1, t-1)] + Fk(p)[E*(k,t-1)] optimal price is myopic Initial discounts or freebies are reasonable Hardness of General Case? vi(S) = wii + ∑j in S Wji wii Even when weights are known, Maximizing Revenue = Maximizing feedback arc set wij Approximation-ratio of 1/2 Random ordering achieves approx ratio of 1/2 Influence and Exploit(IE) Give buyers in set I item for free. Recall freebies by symmetric strategy Visit remaining buyers in random sequence, offer each(adaptively) myopic optimal price Motivated by max feedback arc set heuristic and optimal pricing Diminishing Returns We assume Ri(S) is submodular Ri(S) - Ri(S/j) >= Ri(T) - Ri(T/j), if S is a subset of T Studies indicate this is reasonable assumption Easy 0.25-Approximation Building I: Pick each buyer with probability ½ Offer remaining myopic optimal price Sub-modularity implies: Pick each element in set S with prob. p, then: E[f(S)] >= p f(S) Monotone Hazard Rate Monotone Hazard Rate: f(t)/(1-F(t)) is increasing in t Buyers accepts offer with non-trivial probability Can be used to improve the bounds to 2/3 Satisfied by exponential, uniform and Gaussian distributions Nice closure properties Optimizing over IE Define Revenue(I) Lemma: If Ri s are submodular, so is revenue as a function of influence set. But, it is not monotone Use Feige, Mirrokni, Vondrak, to get a 0.4 approximation Local Search Add to S/Delete from S, if F(S) improves S = {5} F(S) = 5 Maximizing non-monotone sub-modular functions (Feige et. al., 08) Local Search Add to S/Delete from S, if F(S) improves S = {3,5} F(S) = 10 Maximizing non-monotone sub-modular functions (Feige et. al., 08) Local Search Add to S/Delete from S, if F(S) improves S = {2, 3, 5} F(S) = 11 Maximizing non-monotone sub-modular functions (Feige et. al., 08) Local Search Add to S/Delete from S, if F(S) improves S = {2, 5} F(S) = 12 Maximizing non-monotone sub-modular functions (Feige et. al., 08) Recap We propose model where adoption depends on price, study revenue maximization Identify Influence and Exploit Strategies Show they are reasonable Discuss optimization techniques Further Work Pricing model: set prices once and for all (no traveling salesman) No price discrimination Dynamics ? Thanks