Report

Sponsored Search Cory Pender Sherwin Doroudi Optimal Delivery of Sponsored Search Advertisements Subject to Budget Constraints Zoe Abrams Ofer Mendelevitch John A. Tomlin Introduction Search engines (Google, Yahoo!, MSN) auction off advertisement slots on search page related to user’s keywords Pay per click Earn millions a day through these auctions – Auction type is important Sponsored search parameters Bids Query frequencies QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. – Not controlled by advertisers or search engine – Few queries w/ large volume, many with low volume Advertiser budgets Pricing and ranking algorithm Solution Focus on small subset of queries – Predictable volumes in near future – Constitute large amount of total volume Sponsored search parameters Bids Query frequencies Advertiser budgets – Controlled by advertisers Pricing and ranking algorithm – Generalized second price (GSP) auction – Rankings according to (bid) x (quality score) – Charged minimum price needed to maintain rank Goal: take these parameters into account, maximize revenue Motivating example Reserve price is Bidder Bid for q1 Bid for q2 Budget b1 C1 + C1 C1 b2 C1 0 C1 b3 C1 - C1 - 2 C1 Allocation Shown for q1 Greedy b1 Shown for q2 b3 Total Revenue C1 + Optimal b1 2C1 - b2 Problem Definition Queries Q = {q1, q2, q3, ..., qN} Bidders B = {b1, b2, b3, ..., bM} Bidding state A(t); Aij(t) is j’s bid for i-th query dj is j’s daily budget vi is estimate of query frequency Li = {jp : jp B, p = 1, ..., Pi} Lik = {jik : jik Li, l ≤ Lik ≤ P} Ranking and revenue QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. and a QuickTime™ Bid-ranking TIFF (LZW) decompressor Revenue-ranking areQuickTi neededme™ to see andthis a picture. TIFF (LZW) decompressor So, for slate k, are needed to see this pi cture. QuickTime™ and a TIFF (LZW) decompressor Price per click: are needed to see this picture. Independent click through rates Qu ickTime ™ a nd a TIFF (L ZW) dec omp ress or are nee ded to s ee th is p ictur e. Revenue-per-search: Total revenue: Qui ckTime™ and a TIFF ( LZW) decompressor are needed to see this pi cture. QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. Bidder’s cost Total spend for j: Quic kT ime™ and a T IFF (LZW) dec ompres sor are needed to s ee this pi cture. QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. Linear program Queries i = 1, ..., N Bidders j = 1, ..., M Slates k = 1, ..., Ki Data: dj, vi, cijk, rik Variables: xik Constraints: – Budget: – Inventory: QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. QuickTi me™ and a T IFF (LZW) decompressor are needed to see thi s pi cture. Objective function Maximize revenue: Value objective: Clicks objective: Quic kT ime™ and a T IFF (LZW) dec ompres sor are needed to s ee this pi cture. QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. Column Generation Each column represents a slate Could make all possible columns – But for each query, exponential in number of bidders Start with some initial set of columns j: Marginal value for j’s budget i: Marginal value for ith keyword QuickTime™ and a (LZW) decompressor Profit if areTIFF needed to see this picture. Maximize QuickTi me™ and a TIFF (LZW) decom pressor are needed to see this pi cture. How to maximize? If small number of bidders for a query, enumerate all legal subsets Lik, find maxima, see if adding increases profit Otherwise, use algorithm described in another paper ebay.com tigerdirect.com QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. ? nextag.com priceline.com Summary (so far) Various bidders vying for spots on the slate for each query Constrained by budget, query frequencies, ranking method Solve LP for some initial set of slates Check if profit can be made by adding new slates Re-solve LP, if necessary Can be applied to maximize revenue or efficiency Simulation Methodology Compare this method to greedy algorithm – For greedy, assign what gets most revenue at the time; when bidder’s budget is reached, take them out of the pool Used 5000 queries For 11 days, retrieved hourly data on bidders, bids, budgets To determine which ads appear, assign based on frequencies fik = xik/vi After each hour, see if anyone has exceeded budget Simulation Results Current method better than greedy method, when optimizing over revenue or efficiency Larger gain for revenue when revenue optimized Revenue and efficiency are closely tied Gains when efficiency is maximized QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. Gains when revenue is maximized QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. Impact on bidders QuickTime™ and a TIFF (LZW) decompressor are needed to see this picture. Limitations Illegitimate price hikes for other bidders if one person exceeds budget in middle of hour Assumption that expected number of clicks are correct For the purposes of the simulation, expect these to affect greedy and LP optimization similarly Future work Focus on less frequent queries – Frequencies harder to predict – Some work has been done (doesn’t incorporate pricing and ranking) Keywords with completely unknown frequencies Parallel processing for submarkets Investigate how advertisers might respond to this method – Potential changes in reported bids/budgets