Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems
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 (multiplechoice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either pro.t 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 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.
Sponsored search auction keyword bidding online knapsack problem multiple-choice knapsack problem
Yunhong Zhou Deeparnab Chakrabarty Rajan Lukose
HP Labs 1501 Page Mill Rd Palo Alto CA 95304 College of Computing Georgia Tech Atlanta, GA 30332
国际会议
第十七届国际万维网大会(the 17th International World Wide Web Conference)(WWW08)
北京
英文
2008-04-21（万方平台首次上网日期，不代表论文的发表时间）