Budget constrained bidding in keyword auctions and online knapsack problems

TLDR

The budget‑constrained bidding problem in sponsored search auctions is modeled as an online multiple‑choice knapsack problem. The authors design deterministic and randomized algorithms that achieve a provably optimal competitive ratio, enabling fully automatic bidding strategies that maximize profit or revenue. They develop oblivious deterministic and randomized online knapsack algorithms, evaluate them on synthetic and real bidding data, and introduce a sniping heuristic that improves performance. With sniping and parameter tuning, the algorithms reach a performance ratio exceeding 90 % of the omniscient optimum.

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 (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. 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.