Research map / Bandits and online learning / Online convex optimization and games
Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization
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.
Compares uniform-price and discriminatory repeated multi-unit auctions from a single bidder's learning-to-bid perspective against stochastic adversaries, giving tight worst-case regret rates and showing uniform auctions can learn faster in some instances.
Problem
Learning to bid in repeated multi-unit auctions (uniform-price vs discriminatory) when opposing bids are stochastic, measuring regret under full-information and bandit feedback.
Approach
Uses deterministic CDF-estimation-based algorithms with concentration bands in continuous bid space (no discretization); shows uniform-price auctions under bandit feedback can achieve sqrt(T) regret in instances where discriminatory auctions remain at T^{2/3}, due to richer feedback from the uniform price revealing opposing bids.
Key results
- Both formats achieve tight worst-case regret of Õ(K√T) under full information; under bandit feedback both are Θ̃(T^{2/3}) worst case.
- Uniform-price auction under bandit feedback achieves Õ(√T) regret for unit-demand (0 regret), two-unit demand, Δ-separated distributions and i.i.d. symmetric unit-demand adversaries, while discriminatory remains Ω(T^{2/3}).
- Explore-then-commit for uniform auction with bandit feedback achieves Õ(K^{5/3} T^{2/3}) regret; new Ω(T^{2/3}) lower bound for uniform auction under bandit feedback.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use full-information feedback rather than bandit feedback | Learning in multi-unit uniform and discriminatory auctions · Multi-unit auctions, worst-case | regret: $\tilde{\Theta} ( \sqrt{T} )$ and $\tilde{\Theta} ( T^{2/3} )$ | Helped |
| Use uniform-price rather than discriminatory pricing | Repeated multi-unit auctions with bandit feedback, unit demand · Unit demand | regret: 0 regret; $\Omega \left( T^{2/3} \right)$ | Helped |
| Use uniform-price rather than discriminatory pricing | Repeated multi-unit auctions with bandit feedback, two-unit demand · Two-unit demand | regret: $\mathcal{O} ( \sqrt{T})$; $\Omega ( T^{2/3})$ | Helped |
| Use uniform-price rather than discriminatory pricing | Repeated multi-unit auctions with bandit feedback · Δ-separated distributions | regret: $\mathcal{O} ( \sqrt{T} )$; $\Omega ( T^{2/3} )$ | Helped |
| Exploit symmetry and i.i.d. unit-demand adversaries with UBIID | Uniform-price auction · I.i.d. symmetric unit-demand adversaries | regret: $\tilde{\mathcal{O}} \left ( \sqrt{T} \right ) $ | Helped |
| Use uniform-price rather than discriminatory pricing | Repeated multi-unit auctions with bandit feedback, Δ > 0 instances · Δ > 0 instances | regret: $\tilde{\mathcal{O}} ( K\sqrt{T} ) $; $\Omega \left ( T^{2/3} \right )$ | Helped |
Surprising findings
- Under bandit feedback, the uniform-price auction can have strictly faster learning (sqrt(T)) than the discriminatory auction in several instance families, despite matching worst-case rates.
Limitations
- Assumes opposing bids are stochastic (i.i.d. or fixed distribution), not strategic adversaries.
- Bidder valuations are assumed known.
- Some upper bounds have extra K factors (e.g. K^{5/3} for uniform bandit) and the i.i.d. setting assumes known number of adversaries N.
Experimental setup
Metrics: regret
Baselines: Potfer et al. Branzei et al. Galgana et al.
Builds on: Potfer et al. discriminatory auction learning Branzei et al. uniform price learning Galgana et al. uniform price learning DKW inequality successive elimination
Closest papers by meaning
- Improved learning rates in multi-unit uniform price auctions (NeurIPS 2024 · similarity 0.93)
- Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 2025 · similarity 0.90)
- Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions (AAAI 2021 · similarity 0.89)
- Learning and Collusion in Multi-unit Auctions (NeurIPS 2023 · similarity 0.89)
- Randomized Truthful Auctions with Learning Agents (NeurIPS 2024 · similarity 0.87)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (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.