Research map / Bandits and online learning / Online convex optimization and games
Learning Safe Strategies for Value Maximizing Buyers in Uniform 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 learning to bid for value-maximizing RoI-constrained buyers in repeated uniform price auctions, characterizing finite safe undominated m-uniform strategies and learning them via a DAG-based Hedge/EXP3 implementation with richness-ratio guarantees.
Problem
Bidding in repeated uniform price multi-unit auctions by a value-maximizing buyer subject to per-round return-on-investment constraints, against strategic or adversarial competing bids, with m-uniform bidding (m bid-quantity pairs).
Approach
Defines safe strategies that satisfy RoI for any competing bids; shows they reduce to a finite class where bids equal average valuations w_{Q_j}, so the offline optimum is a max-weight path in a poly-size DAG; runs a weight-pushing Hedge (full info) or EXP3-like (bandit) update over edges to get poly(m,M) time learning, and introduces a richness ratio to compare against richer benchmark classes.
Key results
- Full-information regret O(M sqrt(m T log M)) and bandit regret O(M^2 m^{3/2} sqrt(T)) with matching Omega(M sqrt T) lower bound
- Richness ratios: 1/2 vs RoI-feasible m-pair strategies, m/m' vs safe m'-pair strategies, m/(2m') vs RoI-feasible m'-pair strategies, all tight in worst case
- On EU ETS data, empirical richness ratios are far above worst-case bounds (e.g., ~0.8 for 1-uniform vs 10-pair safe, vs worst-case 0.1)
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the DAG-based learning algorithm to learn safe strategies with at most m bid-quantity pairs | Value-maximizing buyers in repeated uniform price auctions · Full-information feedback | regret: O(M\sqrt{m T\log M}) | Helped |
| Use edge-weight estimators with the DAG-based learner | Value-maximizing buyers in repeated uniform price auctions · Bandit feedback | regret: O(M^2\sqrt{m^3 T\log M}) | Helped |
| Use the structured DAG-based bandit learner instead of a naive EXP3 implementation over paths | Safe bidding strategies with at most m bid-quantity pairs · Bandit feedback | regret bound: T^{2/3} to \sqrt{T} | Helped |
| Restrict the learner to safe strategies with at most m bid-quantity pairs | Value-maximizing buyers · RoI-feasible strategies with at most m bid-quantity pairs | richness ratio: \alpha=1/2 | Hurt |
| Allow the clairvoyant m' bid-quantity pairs instead of the learner's m | Safe bidding strategies · Safe strategies with at most m' bid-quantity pairs | richness ratio: \alpha=m/m' | Hurt |
| Allow the clairvoyant m' bid-quantity pairs and strategies that are only RoI-feasible for the bid history | Safe bidding strategies with at most m bid-quantity pairs · RoI-feasible strategies with at most m' bid-quantity pairs | richness ratio: \alpha=m/2m' | Hurt |
| Evaluate safe strategies against RoI-feasible strategies on semi-synthetic EU ETS data | Safe bidding strategies with at most m bid-quantity pairs · EU ETS emission permit auction data, 2022 and 2023 | empirical richness ratio lower bound: 0.95 | Helped |
| Increase the safe-strategy class from 1 to 10 bid-quantity pairs | Safe bidding strategies on semi-synthetic EU ETS data · EU ETS emission permit auction data, 2022 and 2023 | empirical richness ratio: \sim0.8 | Helped |
Surprising findings
- Empirical 1-uniform safe strategies achieve about 0.8 of the optimal 10-pair safe value, far above the worst-case 0.1 bound
- Safe strategies lose at most a factor 2 against the best RoI-feasible strategies with the same number of pairs, independent of m
Limitations
- Worst-case richness ratios can be as small as m/m' for fixed m, implying poor performance against richer classes in pathological instances
- Assumes fixed valuation curve and oblivious adversary in the main model; RoI enforced per round only
- Empirical study uses synthesized bid data reconstructed from aggregate statistics
Experimental setup
Datasets: EU ETS emission permit auction data (2022, 2023, aggregate statistics, semi-synthetic reconstruction)
Benchmarks: EU ETS semi-synthetic auction data
Metrics: regret richness ratio
Baselines: naive Hedge over paths naive EXP3 over paths quasilinear bidding learning algorithms
Builds on: Hedge EXP3 weight-pushing algorithm
Closest papers by meaning
- Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization (NeurIPS 2025 · similarity 0.90)
- Learning Optimal Reserve Price against Non-myopic Bidders (NeurIPS 2018 · similarity 0.90)
- Learning Auctions with Robust Incentive Guarantees (NeurIPS 2019 · similarity 0.89)
- Weakly Consistent Optimal Pricing Algorithms in Repeated Posted-Price Auctions with Strategic Buyer (ICML 2018 · similarity 0.89)
- Improved learning rates in multi-unit uniform price auctions (NeurIPS 2024 · similarity 0.88)
- Adaptive Market Making with Inventory Constraints via Online Learning (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.