Research map / Bandits and online learning / Online convex optimization and games
Randomized Truthful Auctions with Learning Agents
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.
Shows that with mean-based no-regret bidders, deterministic truthful auctions can fail to make the runner-up bid truthfully, while randomized strictly-IC auctions restore convergence, beat SPA with reserve on revenue, and achieve auctioneer regret of T^{3/4} (fixed auction) or sqrt(T) (auction schedule).
Problem
Repeated single-item auctions where bidders use no-regret (mean-based) learning algorithms rather than being fully rational: deterministic truthful auctions may fail to induce truthful bidding, and revenue guarantees of standard second-price auctions with reserve break down.
Approach
Characterize convergence of MWU bidders in deterministic truthful auctions as a function of learning-rate ratio, then introduce strictly-IC randomized auctions (and a black-box transformation of any truthful auction into a nearby strictly-IC one) that force last-iterate convergence to truthful bidding, enabling revenue gains and finite-horizon regret bounds.
Key results
- Strictly-IC auctions, or a black-box transformation of any truthful auction into a strictly-IC one, make mean-based learners converge to truthful bidding for any learning rates, with auction changes of o(1) in allocation and payment.
- For fixed auctions, auctioneer regret of order T^{3/4} is achievable and tight against MWU with rate 1/sqrt(T); with an oblivious auction schedule switching once, regret improves to order sqrt(T), and this is optimal.
- For uniform i.i.d. valuations, SPA with any reserve is strictly suboptimal in the learning setting, and a randomized auction can recover Myerson revenue up to o(1) as T grows.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a constant mixture of a strictly IC auction and SPA | Repeated prior-free auctions with learning bidders · Prior-free repeated auctions, constant auction policy | auctioneer regret: \widetilde O(T^{3/4}) upper bound; \widetilde{Reg}_T(A_T;v_L,v_H) \geq C_\Delta \cdot T^{3/4} lower bound | Mixed |
| Use a strictly IC auction for an initial phase, then switch to SPA | Repeated prior-free auctions with learning bidders · Prior-free repeated auctions, auction schedule | auctioneer regret: \widetilde O(\sqrt{T}) | Helped |
| Use an auction schedule, even allowing a different auction each round | Repeated auctions with MWU bidders · Prior-free repeated auctions, auction schedule | auctioneer regret lower bound: \Omega(\sqrt{T}) | Hurt |
| Use staircase auction for the initial phase, then SPA | Repeated prior-free auctions with learning bidders · Prior-free repeated auctions with discretization Δ | auctioneer regret: \widetilde O\left( \Delta^2\sqrt{T} \right) | Helped |
| Use a deterministic truthful auction rather than a randomized strictly IC auction | Repeated auctions with persistent valuations and mean-based learners · Persistent valuations | runner-up truthfulness | Hurt |
| Make the runner-up learner's learning rate strictly faster than the winner's | MWU bidders in a non-degenerate deterministic truthful auction · Persistent valuations | runner-up truthfulness | Helped |
| Use a strictly IC auction | Mean-based no-regret learners in repeated auctions · Repeated strictly IC auctions | truthful bidding convergence | Helped |
| Use randomized auctions rather than SPA with reserve | Repeated auctions with mean-based no-regret learners · Asymptotic revenue maximization | revenue guarantee | Helped |
| Use SPA with reserve with learning bidders rather than truthful rational bidders | Second-price auction with reserve · Uniform valuations on U[B_Δ] | revenue: < rational-bid revenue − c | Hurt |
Surprising findings
- The runner-up bidder may fail to converge to truthful bidding in deterministic truthful auctions even as T goes to infinity, when learning rates are comparable.
- Separating exploration and exploitation into two phases (first a strictly-IC auction, then SPA) gives sqrt(T) auctioneer regret, unlike the intermixed strategy typical in bandits.
Limitations
- Analysis restricted to two bidders (mostly), full-feedback MWU, and persistent i.i.d. valuations.
- Assumes bidders never bid above their value.
- Auctioneer regret bounds depend on discretization parameter Delta and are stated up to log factors.
Experimental setup
Metrics: auctioneer regret revenue last-iterate convergence to truthful bidding
Baselines: second-price auction with reserve second-price auction Myerson optimal auction
Builds on: Kolumbus and Nisan 2022a Myerson optimal auction mean-based no-regret learning multiplicative weights update
Closest papers by meaning
- Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions (AAAI 2021 · similarity 0.90)
- No-Regret Online Autobidding Algorithms in First-price Auctions (NeurIPS 2025 · similarity 0.88)
- Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization (NeurIPS 2025 · similarity 0.87)
- Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions (ICML 2025 · similarity 0.87)
- Increasing Revenue in Efficient Combinatorial Auctions by Learning to Generate Artificial Competition (AAAI 2025 · similarity 0.86)
- Beyond Monotonicity: On the Convergence of Learning Algorithms in Standard Auction Games (AAAI 2025 · similarity 0.86)
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.