# Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions

arXiv: https://arxiv.org/abs/2009.06136 · HTML: https://mlsanity.com/paper/2009.06136/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Sep 2020.

## Built on by (most cited first, 14 of 14)

- [Fast swap regret minimization and applications to approximate correlated equilibria](https://mlsanity.com/paper/2310.19647/) (2023)
- [Auctions Between Regret-Minimizing Agents](https://mlsanity.com/paper/2110.11855/) (2021)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions](https://mlsanity.com/paper/2110.03906/) (2021)
- [Strategizing against No-Regret Learners in First-Price Auctions](https://mlsanity.com/paper/2402.08637/) (2024)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (2024)
- [Adaptive maximization of social welfare](https://mlsanity.com/paper/2310.09597/) (2023)
- [From No-Regret to Strategically Robust Learning in Repeated Auctions](https://mlsanity.com/paper/2601.03853/) (2026)
- [Randomized Truthful Auctions with Learning Agents](https://mlsanity.com/paper/2411.09517/) (2024)
- [Markets with Heterogeneous Agents: Dynamics and Survival of Bayesian vs. No-Regret Learners](https://mlsanity.com/paper/2502.08597/) (2025)
- [Breaking Algorithmic Collusion in Human-AI Ecosystems](https://mlsanity.com/paper/2511.21935/) (2025)
- [Uncoupled Bandit Learning towards Rationalizability: Benchmarks, Barriers, and Algorithms](https://mlsanity.com/paper/2111.05486/) (2021)
- [Advancing Ad Auction Realism: Practical Insights & Modeling Implications](https://mlsanity.com/paper/2307.11732/) (2023)

## Abstract (arXiv)

The connection between games and no-regret algorithms has been widely studied in the literature. A fundamental result is that when all players play no-regret strategies, this produces a sequence of actions whose time-average is a coarse-correlated equilibrium of the game. However, much less is known about equilibrium selection in the case that multiple equilibria exist. In this work, we study the convergence of no-regret bidding algorithms in auctions. Besides being of theoretical interest, bidding dynamics in auctions is an important question from a practical viewpoint as well. We study repeated game between bidders in which a single item is sold at each time step and the bidder's value is drawn from an unknown distribution. We show that if the bidders use any mean-based learning rule then the bidders converge with high probability to the truthful pure Nash Equilibrium in a second price auction, in VCG auction in the multi-slot setting and to the Bayesian Nash equilibrium in a first price auction. We note mean-based algorithms cover a wide variety of known no-regret algorithms such as Exp3, UCB, ε-Greedy etc. Also, we analyze the convergence of the individual iterates produced by such learning algorithms, as opposed to the time-average of the sequence. Our experiments corroborate our theoretical findings and also find a similar convergence when we use other strategies such as Deep Q-Learning.