Research map / Learning theory and algorithms / Submodular and game algorithms
A Field Guide for Pacing Budget and ROS Constraints
Santiago R. Balseiro, Kshipra Bhawalkar, Zhe Feng, Haihao Lu, Vahab Mirrokni, Balasubramanian Sivan, Di Wang
Read the paperCheck your idea against 137,217 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Compares three decoupled/coupled pacing architectures for value-maximizing bidders under budget and ROS constraints, proving min-pacing matches dual-optimal O(sqrt T) guarantees while sequential pacing can fail linearly.
Problem
Budget pacing and ROS pacing systems are often run by different units, so bids are adjusted independently; the paper asks how decoupled (sequential or min-combined) pacing compares to fully coupled dual-based pacing for value maximizers facing budget and return-on-spend constraints.
Approach
Proposes min pacing, which takes the minimum of the ROS-pacing bid and the budget-pacing bid (each from its own dual feedback loop), and proves it achieves the same O(sqrt T) regret and constraint violation as joint dual-optimal pacing, while sequential bid-lowering can incur linear violation or regret.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use min pacing instead of dual-optimal pacing | Budget and ROS pacing · Semi-synthetic campaigns, ROS violation ≤ 0.15 | cumulative total value (normalized): 0.81 -> 0.86 | Improved |
| Use sequential pacing instead of dual-optimal pacing | Budget and ROS pacing · Semi-synthetic campaigns, ROS violation ≤ 0.15 | cumulative total value (normalized): 0.81 -> 0.30 | Hurt |
| Use sequential pacing instead of dual-optimal pacing | Budget and ROS pacing · Semi-synthetic campaigns, ROS violation ≤ 0.20 | fraction of campaigns: 0.80 -> 0.26 | Hurt |
| Use min pacing instead of dual-optimal pacing | Budget and ROS pacing · Semi-synthetic campaigns, ROS violation ≤ 0.20 | fraction of campaigns: 0.80 -> 0.80 | No clear effect |
Limitations
- Analysis assumes a single bidder with i.i.d. draws, truthful auctions, and non-degeneracy and strong monotonicity assumptions.
- Empirical evaluation uses a semi-synthetic dataset generated from auction data rather than live traffic.
- Multi-bidder equilibrium behavior is left as a conjecture.
Experimental setup
Datasets: semi-synthetic dataset from online advertising platform auction data (10,000 campaigns)
Benchmarks: semi-synthetic advertising campaign dataset (10,000 campaigns)
Metrics: ROS relative constraint violation cumulative conversion value relative to fluid benchmark regret constraint violation
Baselines: dual-optimal pacing sequential pacing
Builds on: Balseiro et al. dual-based pacing Aggarwal et al. optimal auto-bidding online mirror descent
Closest papers by meaning
- Dynamic Budget Throttling in Repeated Second-Price Auctions (AAAI 2024 · similarity 0.87)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.86)
- Interference Among First-Price Pacing Equilibria: A Bias and Variance Analysis (ICLR 2025 · similarity 0.85)
- Online Budgeted Matching with General Bids (NeurIPS 2024 · similarity 0.84)
- No-Regret Online Autobidding Algorithms in First-price Auctions (NeurIPS 2025 · similarity 0.84)
- Percentile Risk-Constrained Budget Pacing for Guaranteed Display Advertising in Online Optimization (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
