Research map / Bandits and online learning / Online convex optimization and games
Dynamic Budget Throttling in Repeated Second-Price Auctions
Read the paperCheck your idea against 108,967 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.
Studies dynamic budget throttling (probabilistic pacing via binary entry decisions) for a single buyer in repeated second-price auctions, proving regret and competitive-ratio bounds and proposing OGD-CB, then compares throttling with pacing.
Problem
How should a single advertiser dynamically throttle (select which auctions to enter) under a budget in repeated second-price auctions, with stochastic or adversarial values and i.i.d. stochastic highest competing bids, and how does throttling compare to pacing?
Approach
OGD-CB combines an online gradient descent update on a dual pricing variable with a DKW-based confidence-bound estimate of the expected reward and cost given the value; it is value-model oblivious and works under full and partial (win-only) price feedback without assuming any distribution form.
Key results
- OGD-CB achieves O(sqrt(T log T)) expected regret against the fluid benchmark under stochastic values with full or partial feedback.
- Any throttling strategy's asymptotic competitive ratio under adversarial values is at most rho/v_bar, which OGD-CB matches.
- Under stochastic values, pacing outperforms the optimal throttling by Theta(T) in general; under adversarial values with stochastic competing bids, throttling (OGD-CB) is asymptotically optimal.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use OGD-CB throttling with full information feedback | Throttling under stochastic values · Stochastic values | regret: O(\sqrt{T \log T}) | Helped |
| Use OGD-CB throttling with partial information feedback | Throttling under stochastic values · Stochastic values | regret: O\left(\sqrt{T \log T}\right) | Helped |
| Use OGD-CB throttling | Throttling under adversarial values and stochastic competing bids · Adversarial values, full or partial information | asymptotic competitive ratio: \rho / \bar{v} | Helped |
| Use adaptive pacing instead of throttling | Budget control under stochastic values and the stated general-case assumptions · Stochastic values | expected revenue: \Theta\left(T\right) | Helped |
| Use adaptive pacing instead of throttling | Budget control when the highest competing bid is fixed or expected cost is at most \rho · Stochastic values | expected revenue difference: O\left(\sqrt{T}\right) | No clear effect |
| Use throttling when values are adversarial and competing bids are stochastic | Dynamic bidding · Adversarial values, stochastic competing bids | asymptotic competitive ratio: \rho / \bar{v} | Helped |
| Use throttling when competing bids are adversarial | Any throttling strategy · Adversarial competing bids | asymptotic competitive ratio: any \mu>0 | Hurt |
Surprising findings
- With adversarial highest competing bids, no throttling strategy can achieve any positive asymptotic competitive ratio, even with fixed values.
- Throttling matches pacing's asymptotic optimality when values are adversarial and competing bids are stochastic, despite pacing being generally superior under stochastic values.
Limitations
- Assumes i.i.d. stochastic highest competing bids; adversarial competing bids make throttling impossible.
- Regret guarantees with partial feedback degrade as rho becomes small relative to v_bar (larger constant).
Experimental setup
Metrics: expected regret asymptotic competitive ratio
Baselines: adaptive pacing
Builds on: pacing (dual/adaptive bidding) network revenue management contextual bandits with knapsacks Yao's principle
Closest papers by meaning
- Learning to Bid in Repeated First-Price Auctions with Budgets (ICML 2023 · similarity 0.91)
- Coordinated Dynamic Bidding in Repeated Second-Price Auctions with Budgets (ICML 2023 · similarity 0.90)
- Robust Budget Pacing with a Single Sample (ICML 2023 · similarity 0.89)
- Percentile Risk-Constrained Budget Pacing for Guaranteed Display Advertising in Online Optimization (AAAI 2024 · similarity 0.87)
- Online Resource Allocation With General Constraints (NeurIPS 2026 · similarity 0.87)
- Non-stochastic Budgeted Online Pricing with Semi-Bandit Feedback (AAAI 2025 · similarity 0.87)
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.