Pacing with ROI: Budget Allocation in Sponsored Search

Sponsored search is a core revenue engine for online marketplaces, where ad slots are sold via auctions and advertisers bid on keywords subject to daily budgets. The central challenge is budget pacing—allocating spending over time to balance immediate opportunities against potentially better future ones. Existing pacing methods are largely heuristic, offering no Return-on-Investment (ROI) guarantees for advertisers and often ignoring minimum spending requirements from the platform's side. We propose new theoretically-motivated budget pacing algorithms that account for the budget and ROI constraints of the advertisers as well as minimum spending constraints of the platform. Evaluated in eBay’s sponsored search environment, our algorithms show that the form of the ROI constraint materially shapes the tradeoff between the advertiser's utilities (e.g., impressions, clicks, cost per click) and the platform's revenue, and they consistently outperform widely used PID-based pacing heuristics, and a state-of-the-art budget pacing approach.