Logo image
Back
Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
Preprint   Open access

Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics

Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins and Mengxiao Zhang
ArXiv.org
Cornell University
06/12/2024
DOI: 10.48550/arxiv.2301.13306
url
https://doi.org/10.48550/arxiv.2301.13306View
Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

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 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. This holds whether or not the bidding dynamics converges to an equilibrium.
 Computer Science - Computer Science and Game Theory Computer Science - Learning

Details

Metrics

68 Record Views
Logo image