WWW 2008 / Poster Paper April 21-25, 2008 · Beijing, China Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems Yunhong Zhou HP Labs 1501 Page Mill Rd Palo Alto CA 95304 Deeparnab Chakrabar ty College of Computing Georgia Tech Atlanta, GA 30332 Rajan Lukose HP Labs 1501 Page Mill Rd Palo Alto CA 95304 yunhong.zhou@hp.com deepc@cc.gatech.edu rajan.lukose@hp.com ABSTRACT We consider the budget-constrained bidding optimization problem for sp onsored search auctions, and model it as an online (multiple-choice) knapsack problem. We design b oth deterministic and randomized algorithms for the online (multiplechoice) knapsack problems achieving a provably optimal comp etitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget-constrained advertiser. Our bidding strategy for revenue maximization is oblivious (i.e., without knowledge) of other bidders' prices and/or click-through-rates for those p ositions. We evaluate our bidding algorithms using b oth synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding p erformance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a p erformance ratio ab ove 90% against the optimum by the omniscient bidder. Categories and Sub ject Descriptors: G.1.6 [Mathematics of Computing]: Mathematical Software - Algorithm Design and Analysis General Terms: Algorithms, Theory, Economics Keywords: Sp onsored search auction, keyword bidding, online knapsack problem, multiple-choice knapsack problem (CTR), denoted (s), which is defined as the total numb er of clicks on an ad divided by the total numb er of impressions (displays). Therefore the default advertiser can obtain slot s by bidding slightly over bs (t); for each user click, he incurs a cost of bs (t), obtains an exp ected revenue V and profit V - bs (t ). Online Knapsack Problems. Let us start with the relatively simple single-slot case. At time t, b(t) is the maximum bid among bidders 1 to N , and X (t) is the numb er of clicks at p eriod t. Winning at time t costs the advertiser w(t) and earns him a profit of v (t) where w(t) b(t)X (t), v (t) (V - b(t))X (t). (1) For revenue maximization, v (t) = V X (t). Since the default bidder has to decide either overbidding b(t) or not at time t, thus keyword bidding corresp onds to the online knapsack problem (Online-KP). The case of multiple slots is captured by the online version of the multiple-choice knapsack problem (Online-MCKP), where each time the advertiser can win at most one ad slot. Our Assumptions. In general, no online algorithm can achieve any non-trivial competitive ratio (the ratio b etween the output of the given algorithm and the offline optimum) for Online-KP [4]. Fortunately, in our setting, we make two reasonable assumptions on the knapsack items, which allow us to develop interesting online algorithms. These two assumptions are: (i)w(t) B; (ii)L v (t ) U, w (t ) t. (2) 1. INTRODUCTION Sp onsored search auction is an effective way of monetizing search query activites for the search engine provider, while shifting the burden to the advertiser to figure out how to automate and optimize the keyword bidding process. In this work we focus on the bid optimization question under the budget constraint. Keyword Bidding Models. For simplicity, assume that the default advertiser has a budget B over a fixed time horizon, discretized into time p eriods 1, . . . , T . He is interested in a single keyword with exp ected value-p er-click V . There are bidders {1, · · · , N } at time t for this keyword and their bids are sorted in decreasing order b1 (t) > . . . > bN (t). There are S ad slots, and are assigned to the top-S bids as follows: bidder s gets slot s; for each user click on his ad, bidder s is charged a price bs+1 , if s < S or a minimum fee bmin (usually 10 ). Each slot s has a click-through-rate Work was done while the author was an intern at HP Labs. Copyright is held by the author/owner(s). WWW 2008, April 21­25, 2008, Beijing, China. ACM 978-1-60558-085-2/08/04. 2. RELATED WORK Keyword Bidding. Sp onsored search auctions have attracted a lot of attention, for b oth auctioneer revenue maximization and advertiser bidding optimization. Among all these work, Mehta etc al. [5] studied the auctioneer revenue maximization with budget-constrained bidders, using a trade-off function (compare it to our threshold function) to grant queries to bidders, and the technique they use is probably most similar to the threshold function we use. Online Algorithms. Awerbuch et al. [2] studied the online call routing which generalizes the online classical knapsack problem. More recently, Buchbinder et al. [3] designed online algorithms for fractional versions of general packing problems which imply an O(ln(U /L))-comp etitive algorithm for the online knapsack problem. 1243 WWW 2008 / Poster Paper April 21-25, 2008 · Beijing, China 3. THE ONLINE KNAPSACK PROBLEM 5. EXPERIMENTAL EXPLORATION In this section, we evaluate our bidding algorithms using b oth synthetic and real-world data, and discuss two useful heuristics: sniping and parameter tuning. The Sniping Heuristic. Simulation of the bidding algorithm describ ed ab ove with synthetic dataset shows that the bidding algorithm is too conservative, and leaves a significant fraction of budget unsp ent. Thus a p otential p erformance improvement is sniping towards the end of the auction. If the bidder has knowledge (reliable estimates) ab out the click traffic (X (t)) and the click-through rates, then the bidding strategies can b e modified to increase its bid appropriately. Theoretically, we can prove that sniping strictly improve the p erformance of the algorithm. For details, see the technical rep ort [6]. Algorithm Online-KP-Threshold Parameter Tunning. If the lower b ound L in the online z Let (z ) (U e/L) (L/e). knapsack problem is too small, we can replace it with a At time t, let z (t) b e the fraction of capacity filled, pick larger value L > L for the threshold function . This v element t iff w(t) (z (t)). essentially discards items with very low efficiency, and the (t ) loss is minimal if the optimal solution consists of items with Theorem 3.1. Both Online-KP-Randomized and Online- relatively high efficiency . It turns out tuning the parameter KP-Threshold have a competitive ratio of ln(U /L) + 1. L makes a significant p erformance improvement. A matching lower b ound: Evaluation using Real Bidding Data. Next we reTheorem 3.2. The competitive ratio of any (possibly ranp ort some exp erimental results on evaluating bidding aldomized) online algorithm for the online knapsack problem gorithms for multiple-slot auctions using real bidding data. is at least ln(U /L) + 1. We scrap ed bidding data from the now defunct Overture webpage [1] with continous crawling for ab out two weeks, 3.1 Single-Slot Auctions for one of the most dynamic and exp ensive keyword "auto insurance." There are totally T = 1842 distinct time p eriwe can translate the algorithms Online-KP-Threshold ods in our collected data, and most top-5 bids are larger to bidding strategies for single-slot keyword auctions for than $10. For the exp eriments, we use B = 1000, and b oth profit and revenue maximization, based on Eq. (1). three different values V = 8, 10, 12. We evaluated b oth the Details are omitted due to space constraints. profit-maximizing and revenue-maximizing strategies with 4. ONLINE-MCKP & MULTIPLE SLOTS and without sniping. For all these exp eriments, we use U = V /bmin - 1 for profit maximization and U = V /bmin The Online-MCKP. The Online-MCKP is a generalizafor revenue maximization, and bmin = 0.9. tion of the Online-KP. At each time p eriod, at most one item Since results are very similar for different parameter valcan b e selected from the item-set Nt = {(vs (t), ws (t))}. The ues, we summarize them in Table 5. For all the examples goal again is to maximize the total value of items selected. we run, sniping improves the bidding p erformance signifiThe Algorithm Online-MCKP-Threshold is a generalizacantly while exhausting the budget. Table 5 seems to tell tion of Alg Online-KP-Threshold, and it works as follows: us, for almost all values, with parameter tuning of L, the ) Let (zs and z (t) b e the same .as b efore. At time t, let p erformance ratio (ALG/OPT) is around 70%-75% without vs (t) Et Nt | ws (t) (z (t)) If Et = , pick element sniping, and 90%-95% with sniping. s Et with maximum vs (t). Theorem 4.1. Online-MCKP-Threshold has a competitive ratio of (ln(U /L) + 2). Multiple-Slot Bidding. Next we translate Alg. OnlineMCKP-Threshold to bidding strategies for b oth profit and revenue maximization. It turns out the revenue maximization strategy is the same as the single-slot case, thus omitted. The profit-maximization bidding strategy is b elow: Bidding Strategy Profit-Maximizing Multiple-Slot Fix > 0. Let (z ) (U e/ )z ( /e). At time t, let z (t) b e fraction of budget sp ent, s , V Et | bs (t ) 1 + ( z (t )) bid bs (t) where s = arg maxsEt (V - bs (t))(s). V 8 10 12 Profit-Maximization Bidding Performance OPT ALG ALG/ budget ALG ALG/ OPT left (sniping) OPT 3779 2751 73% 225.5 3541 94% 4974 4059 82% 116.1 4607 93% 6169 4463 72% 240.8 5842 95% In this section we design comp etitive algorithms for the Online-KP with assumptions (2)(i),(ii). We describ e two (ln(U /L) + 1)-comp etitive algorithms for the problem. Randomized Algorithm: Let D b e the continuous distribution from 0 to U , with the following density function: c f (x) = x , for L x U , and f (x) = c/L for 0 x L, 1 where c = 1+ln(U /L) Algorithm Online-KP-Randomized simply picks a threshhold from the distribution D; at each time, it picks item t iff its efficiency is at least and its budget allows. Deterministic Algorithm: Our deterministic algorithm for Online-KP works against all adversaries.. 6. REFERENCES [1] Overture view bids, available until Febuary 2007. http://uv.bidtool.overture.com/d/search/tools/bidtool [2] B. Awerbuch, Y. Azar, and S. A. Plotkin. Throughputcomp etitive on-line routing. In FOCS, pages 32­40, 1993. [3] N. Buchbinder, K. Jain, and J. S. Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In Proc. ESA, pages 253­264, 2007. [4] A. Marchetti-Spaccamela and C. Vercellis. Sto chastic on-line knapsack problems. Math. Programming, 68:73­104, 1995. [5] A. Mehta, A. Sab eri, U. V. Vazirani, and V. V. Vazirani. Adwords and generalized on-line matching. In Proc. FOCS, pages 264­273, 2005. [6] Y. Zhou, D. Chakrabarty, and R. Lukose. Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems. HP Labs tech rep ort HPL-2008-9, 2008. 1244