WWW2008 Posters - WWW 2008: Posters
Skip to main content.

Poster


Track: Posters

Paper Title:
Budget Constrained Bidding in Keyword Auctions and Online Knapsack Problems

Authors:

  • Yunhong Zhou(Hewlett-Packard Laboratories)
  • Deeparnab Chakrabarty(Georgia Institute of Technology)
  • Rajan Lukose(Hewlett-Packard Laboratories)

Abstract:
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 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 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.

PDF version












Inquiries can be sent to: Email contact: program-chairs at www2008.org

Valid XHTML 1.0 Transitional