Conference proceeding
Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
THIRTY SEVENTH ANNUAL CONFERENCE ON LEARNING THEORY, Vol.247, pp.3642-3643
Proceedings of Machine Learning Research
01/01/2023
Abstract
We study a game between autobidding algorithms that compete in an online advertising platform. Each autobidder is tasked with maximizing its advertiser's total value over multiple rounds of a repeated auction, subject to budget and return-on-investment (ROI) constraints. We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret. Our algorithm uses only bandit feedback and can be used with the first- or second-price auction, as well as with any "intermediate" auction format. Our main result is that when these autobidders play against each other, the resulting expected liquid welfare over all rounds is at least half of the expected optimal liquid welfare achieved by any allocation.(1) Our analysis holds whether or not the bidding dynamics converges to an equilibrium, side-stepping the dearth of provable convergence guarantees in the literature and hardness results that preclude such guarantees for budget-constrained second-price auctions (Chen et al., 2021).
Our vanishing-regret result extends to an adversarial environment without any assumptions on the other agents. We adopt a non-standard benchmark: the sequence of bids such that each bid b(t) maximizes value for the round-t environment under time-averaged constraints. Hence, we side-step the impossibility results for the standard benchmark of best fixed bid (Balseiro and Gur, 2019). Our benchmark specializes to the standard one for a stationary environment.
When there is only a budget constraint, our algorithm specializes to an autobidding algorithm of Balseiro and Gur (2019), and our guarantees specialize to the regret and liquid welfare guarantees from Gaitonde et al. (2023). While our approach to bounding liquid welfare shares a common high-level strategy with Gaitonde et al. (2023), handling the ROI constraint, and particularly both constraints jointly, introduces a variety of new technical challenges. These challenges necessitate a new algorithm, changes to the way liquid welfare bounds are established, and a different methodology for establishing regret properties.
Details
- Title: Subtitle
- Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
- Creators
- Brendan Lucier - Microsoft Res, Cambridge, EnglandSarath Pattathil - MIT, 77 Massachusetts Ave, Cambridge, MA 02139 USAAleksandrs Slivkins - Microsoft Research New York CityMengxiao Zhang - Univ Southern Calif, Los Angeles, CA 90007 USA
- Contributors
- S Agrawal (Editor)A Roth (Editor)
- Resource Type
- Conference proceeding
- Publication Details
- THIRTY SEVENTH ANNUAL CONFERENCE ON LEARNING THEORY, Vol.247, pp.3642-3643
- Publisher
- JMLR-JOURNAL MACHINE LEARNING RESEARCH
- Series
- Proceedings of Machine Learning Research
- ISSN
- 2640-3498
- Number of pages
- 2
- Language
- English
- Date published
- 01/01/2023
- Academic Unit
- Business Analytics
- Record Identifier
- 9984798361802771
Metrics
1 Record Views