.jpg)
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.
Inquiries can be sent to:
