Information, Bidding and Competition in Sponsored Search Jon Feldman S. Muthukrishnan Sponsored search from the advertiser perspective вЂў What is a search ad campaign? вЂў What are the goals of a search ad campaign? вЂў What information do we have to analyze and manage a campaign? вЂў Given this information, how do we manage a campaign? вЂў How does competition affect a search ad campaign? вЂў Note: the word вЂњauctionвЂќ does not appear above... Goals of this tutorial вЂў Detail the real experience of setting up and managing a search ad campaign. вЂў Formulate general research questions inspired by these details. вЂў Highlight examples of existing research. вЂў non-goal: complete survey of the Sponsored Search literature Users, advertisers, and the search engine вЂў Search engine determines which ads get shown, page layout (and, of course, the search results). вЂў Search engine user determines which (if any) ad is clicked, and whether to buy something. ...thus, even from the advertiser perspective, need to reason about behavior of user and search engine. Multiple perspectives Algorithms optimize stuff and prove bounds What can you prove about that heuristic? Great proof... but is this useful on real data? Learning/IR/Stats learn stuff from data and test it Your mechanism is biasing my data...! IsnвЂ™t the Bayesean assumption unsatisfying? We can predict behavior without always needing to bound stuff. Economics model stuff to learn about the world Your model ignores the nature of the agents...! Outline First half (Jon): вЂў Parameters of a search campaign: п‚§ Keywords, creatives, adgroups, match types, negative keywords, geo, language, demographic, ad networks, delivery method, scheduling, rotation, frequency capping, landing pages, conversion tracking. вЂў Goals of a search campaign: п‚§ Direct vs. branding п‚§ Reaching the user п‚§ Conversion attribution вЂў Information: п‚§ Performance statistics, traffic estimation Outline Second half (Muthu): вЂў Bidding, campaign management п‚§ Bidding strategy, optimization п‚§ Keyword selection, bidding languages вЂў Competition п‚§ Dynamics, vindictive strategies Parameters of a search campaign Ad Networks вЂў What is a good economic model for вЂњoutsourcing ads?вЂќ вЂњCompeting Ad Auctions,вЂќ Ashlagi, Monderer, Tennenholtz, AAW 08 вЂњCompeting Keyword Auctions,вЂќ Liu, Chen, Whinston, AAW 08 Automatic bidding вЂў Much more on bidding types, strategy and algorithms later.... (Muthu) вЂў How can an auctioneer successfully mix bidding types? вЂњGeneral Auction Mechanism for Search Advertising,вЂќ Aggarwal, M., Pal, Pal, WWW вЂ�09 Budget allocation вЂў How should a search engine allocate budget efficiently? Pure online algorithms question: ``Adwords and Generalized Online Matching'', Mehta, Saberi, Vazirani, Vazirani, JACM, 2007. вЂў What incentives do the resulting mechanism create? вЂњMulti-unit Auctions with budget limits,вЂќ Dobzinski, Lavi, Nisan. FOCS 08. Ad rotation вЂў Clear application of explore/exploit model. вЂў What are the implications of having the search engine automate the learning, rather than the advertiser? Frequency capping (not on search ads) вЂў Marketing rule of thumb: People should see your ad between 3 and 7 times. вЂў Is this still true for online ads? For what formats is this a useful rule? вЂў We are now armed with massive data; was this even true to begin with? Keywords, queries and broad match вЂњkeywordвЂќ = the criteria entered by an advertiser вЂњqueryвЂќ = the data entered by the user вЂњbroad matchвЂќ = search engine determines if (and to what degree) a keyword matches a query вЂў When does a keyword match a query? вЂў Are keywords the right language for advertisers to express their preference for queries? п‚§ Other alternatives? Learning / NLP questions вЂў Can user intention be gleaned from queries? вЂў Can advertiser intention be gleaned from sets of keywords, ad creatives, landing pages? "Logistic Regression and Collaborative Filtering for Sponsored Search Term Recommendation", Bartz, Murthi, Sebastian, AAW 06 вЂњKeyword generation for search engine advertising using semantic similarity between terms,вЂќ Abhishek, EC 07 Economic questions вЂў Is it a good idea to opt into broad match? вЂњBid Optimization for Broad Match Ad Auctions,вЂќ Even-Dar, Mirrokni, Mansour, M., Nadav. вЂњTo Broad-Match or Not to Broad Match: An AuctioneerвЂ™s Dilemma?,вЂќ Singh, Roychowdhury, AAW 08 вЂў How do targeting restrictions affect efficiency of ad placements? вЂњThe Cost of Inexpressiveness in Advertisement Auctions,вЂќ Benisch, Sadeh, Sandholm, AAW 08. вЂњThe Cost of Conciseness in Sponsored Search Auctions,вЂќ Abrams, Ghosh, Vee, WINE 07. вЂў How does competition express itself across the keyword/query network? Algorithmic questions вЂў How do match ads to queries (online) to maximize efficiency? вЂњAn Optimal Online Bipartite Matching Algorithm,вЂќ Karp, Vazirani, Vazirani, STOC вЂ™90. вЂњOptimize-and-Dispatch Architecture for Expressive Ad Auctions,вЂќ Parkes and Sandholm, AAW 05. вЂњOffline Optimization for Online Ad Allocation,вЂќ F., Mehta, Mirrokni, M., AAW 09 Goals of a search campaign Goals of advertising вЂў Direct vs. branding вЂњDirectвЂќ advertiser: selling something now e.g.: online electronics retailer вЂњBrandingвЂќ advertiser: building brand awareness e.g.: national restaurant chain Direct advertisers: easier to quantify goals вЂў Direct advertisers want sales вЂњconversionвЂќ = ad interaction that results in a sale v = value(conversion) в‰€ profit from sale Goal: maximize v вЂў #conversions - cost $120.00 $100.00 ....find point where dCost / dConversions = v cost $80.00 $60.00 $40.00 $20.00 $0 5 10 15 conversions 20 25 Conversions via impressions v = value(conversion) в‰€ profit from sale Risk-neutral model: value(click) = v вЂў Pr[conversion | click] value(impression) = value(click) вЂў Pr[click | impression] Therefore: value(impr.) = v вЂў Pr[conversion | click] вЂў Pr[click | impr.] Direct advertisers val(impr.) = v вЂў Pr[conv. | click] вЂў Pr[click | impr.] So generating value is (in principle) simple: For each search query: - bidders declare value(impression) - SE runs an efficient, truthful auction. ...but: ...how do we learn those probabilities? ...who is in the best position to learn them? ...how do we elicit values on a per-query basis? Bid for clicks, rank by impression value вЂў Current SE common practice: - Bidders declare val(click) (= v вЂў Pr[conv | click]) ....bid declared on keyword level. - SE estimates Pr[click | impr.], ranks by val(impr.) = val(click) вЂў Pr[click | impr.] ....ranking at query time. price: min bid required to achieve rank pay only on a click вЂў Implicit assumption: v, Pr[conversion | click] both independent of query. Learning click probabilities: user click models ...but ...how do users interact with ads? вЂњSeparableвЂќ model: - User looks at ad in position j with prob. p(j). p(1) > p(2) > ... > p(k) - If user looks at ad, user clicks on ad with prob. q(i). вЂў Ranking by b(i) q(i) maximizes efficiency вЂў Basis of most mech. design work in sponsored search Learning click probabilities: user click models ...but ...how do users really interact with ads? CS: вЂњSponsored Search Auctions with Markovian Users,вЂќ Aggarwal, F., M., Pal, WINE 08. вЂњA Cascade Model for Externalities in Sponsored Search,вЂќ Kempe, Mahdian, WINE 08. Learning / IR: вЂњAn Experimental Comparison of Click Position-Bias Models,вЂќ Craswell, Zoeter, Taylor, Ramsey, WSDM 2008 вЂњA User Browsing Model... ,вЂќ Dupret, Piwowarsky, SIGIR 08 вЂњClick Chain Model in Web Search,вЂќ Guo, Liu, Kannan, Minka, Taylor, Wang, Faloutsos, WWW 09 Econ: вЂњPosition Auctions with Consumer Search,вЂќ Athey, Ellison, working paper, 2007. Learning click probabilities: user click models вЂњPosition Auctions with Consumer Search,вЂќ Athey, Ellison, working paper, 2007. вЂў User looking for something вЂў Will search down the sponsored links until cognitive cost of looking > expected value from looking SE: arrange ads to minimize user cost, maximize ad value Advertiser: proper targeting, build user trust. Learning and Incentives вЂњDynamic Cost-Per-Action Mechanisms and Applications to Online Advertising,вЂќ Nazerzadeh, Saberi, Vohra, WWWвЂ™08 вЂў Repeated sales of clicks c1, c2, c3, ..., cn. вЂў Mechanism decides to give click i to advertiser j based on history. вЂў Advertiser j then learns how valuable the click was, reports v(i, j). вЂњCharacterizing Truthful Multi-Armed Bandit mechanisms,вЂќ Babaioff, Sharma, Slivkins, EC 09. The Price of Truthfulness for Pay-Per-Click Auctions,вЂќ Devanur, Kakade, EC 09 вЂў If mechanism truthful, each sale must explore or exploit, not both. Conversion Attribution value(click) = v вЂў Pr[conversion | click] What role does the search ad click play in вЂњgeneratingвЂќ the conversion? вЂњIntegrated Multichannel Communication Strategies: Evaluating the Return on Marketing objectives...,вЂќ Briggs, Krishnan, Borin, Journal of Interactive Marketing, 2005. Brand and Search In what phases of this process is (sponsored) search useful? Model still relevant? вЂњInternet Shopping Shoots Holes in the Purchase FunnelвЂќ J. Henry, bnet.com, Sept. 2008. Information Always an aggregated view вЂў Each auction a small part of overall campaign performance. вЂў Huge diversity of queries, competition, targeting features. вЂў Noise in every prediction пѓћ The dynamics of GSP are a second-order concern. Impressions, Clicks, Cost and Position вЂў Always see aggregated view over diverse set of queries п‚§ How should an advertiser react to information? $1.20 $1.00 cost $0.80 ? $0.60 $0.40 ? $0.20 $5 10 15 20 25 conversions $120.00 $100.00 $80.00 cost have: 0 $60.00 $40.00 $20.00 $- need: 0 5 10 15 conversions 20 25 Traffic Projections Keyword-based estimates вЂў How can the SE predict the effect of a bid change? вЂў Bid affects query mix, and therefore conversion probability and value. Simulation-based estimates Traffic predictions from click simulation вЂў If an advertiser had placed differently, what would have happened? click Ad A Ad C click? Ad B Ad A click? Ad C Ad B Ad D Ad D Acting on traffic predictions вЂў How volatile is click traffic? Does volatility come from... п‚§ competition? п‚§ query (inventory) variance? п‚§ changes to SE algorithms? вЂў Can traffic be separated effectively across keywords? п‚§ keywords are related to each other вЂў Need simple, robust bidding strategies (stay tuned). Web Analytics Portfolio of auctions Advertisers face a complex, noisy, dynamic environment. - Important to target effectively, monitor performance. - find signals in massive data sets - Need fast, scalable, simple optimization strategies. ...go have some coffee.