Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems

Zhou, Yunhong ; Chakrabarty, Deeparnab ; Lukose, Rajan

HP Development Company

关键词: Auctions and Online Knapsack Problems;   

RP-ID  :  HPL-2008-9

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

We consider the budget-constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple-choice) knapsack problem. We design both deterministic and randomized algorithms for the online (multiple-choice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget-constrained advertiser. To maximize revenue from sponsored search advertising, our bidding strategy can be oblivious (i.e., without knowledge) of other bidders' prices and/or click-through-rates for those positions. We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding performance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a performance ratio above 90% against the optimum by the omniscient bidder. 10 Pages