mlsanityData to 7 Oct 2026

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

arXiv 2301.13306 ↗First posted 30 Jan 2023cs.GT cs.LGcited by 20

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 20 papers in the map (data through 7 Oct 2026). Builds on 25 of its 46 references that are in the map. First posted on arXiv 30 Jan 2023.

Builds on

25 of 46 references.

References · 25

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Introduction to Multi-Armed Banditscited by 475
  3. 2017Training GANs with Optimismcited by 217
  4. 2013Bandits with Knapsackscited by 163
  5. 2015Fast Convergence of Regularized Learning in Gamescited by 149
  6. 2017Cycles in adversarial regularized learningcited by 122
  7. 2018Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimizationcited by 97
  8. 2021Near-Optimal No-Regret Learning in General Gamescited by 85
  9. 2018Adversarial Bandits with Knapsackscited by 73
  10. 2020The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problemscited by 58
  11. 2020Tight last-iterate convergence rates for no-regret learning in multi-player gamescited by 47
  12. 2019Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Gamescited by 24
13 more
  1. 2021Robust Auction Design in the Auto-bidding Worldcited by 21
  2. 2022Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergencecited by 18
  3. 2022Online Bidding Algorithms for Return-on-Spend Constrained Advertiserscited by 17
  4. 2017Multiplicative Pacing Equilibria in Auction Marketscited by 16
  5. 2018Pacing Equilibrium in First-Price Auction Marketscited by 14
  6. 2016The Price of Anarchy in Auctionscited by 11
  7. 2022Bidding Agent Design in the LinkedIn Ad Marketplacecited by 7
  8. 2020Non-quasi-linear Agents in Quasi-linear Mechanismscited by 6
  9. 2013Efficiency Guarantees in Auctions with Budgetscited by 5
  10. 2021Contextual Standard Auctions with Budgets: Revenue Equivalence and Efficiency Guaranteescited by 5
  11. 2021The Complexity of Pacing for Second-Price Auctionscited by 5
  12. 2023Auctions without commitment in the auto-bidding worldcited by 3
  13. 2015Liquid Price of Anarchycited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 3; 2025: 8; 2026: 4.

20 papers.

Sort:

  1. 2023Online Advertisements with LLMs: Opportunities and Challengescited by 17
  2. 2023Multi-channel Autobidding with Budget and ROI Constraintscited by 14
  3. 2024No-Regret Algorithms in non-Truthful Auctions with Budget and ROI Constraintscited by 9
  4. 2024Impact of Decentralized Learning on Player Utilities in Stackelberg Gamescited by 5
  5. 2025Learning to Bid in Non-Stationary Repeated First-Price Auctionscited by 5
  6. 2023Online Learning in Contextual Second-Price Pay-Per-Click Auctionscited by 4
  7. 2023Learning in Repeated Multi-Unit Pay-As-Bid Auctionscited by 3
  8. 2024Games with Payments between Learning Agentscited by 3
  9. 2023Adaptive maximization of social welfarecited by 2
  10. 2025Online Bidding under RoS Constraints without Knowing the Valuecited by 2
  11. 2025BAT: Benchmark for Auto-bidding Taskcited by 2
  12. 2025Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learnerscited by 1
8 more
  1. 2025Autobidding Arena: unified evaluation of the classical and RL-based autobidding algorithmscited by 1
  2. 2026Learning to Bid with Unknown Private Values in Budget-Constrained First-Price Auctionscited by 1
  3. 2025Online Bidding Algorithms with Strict Return on Spend (ROS) Constraintcited by 0
  4. 2025Large-Scale Auto-bidding with Nash Equilibrium Constraintscited by 0
  5. 2025Plan-Driven Adaptive Bidding for First-Price Auctions with Budget Constraints under Nonstationaritycited by 0
  6. 2026Efficiency of Proportional Mechanisms in Online Auto-Bidding Advertisingcited by 0
  7. 2026Decision-Calibrated Conformal Uncertainty for Pacing Decisions in Streaming Advertisingcited by 0
  8. 2026Inference Auctionscited by 0