# Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 60 references that are in the map.
- First posted on arXiv 8 Oct 2021.

## Builds on (most cited first, 22 of 22)

- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [Selling to a No-Regret Buyer](https://mlsanity.com/paper/1711.09176/) (2017)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Learning Prices for Repeated Auctions with Strategic Buyers](https://mlsanity.com/paper/1311.6838/) (2013)
- [Learning to Bid Without Knowing your Value](https://mlsanity.com/paper/1711.01333/) (2017)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Contextual Bandits with Cross-learning](https://mlsanity.com/paper/1809.09582/) (2018)
- [Econometrics for Learning Agents](https://mlsanity.com/paper/1505.00720/) (2015)
- [Learning to Bid in Contextual First Price Auctions](https://mlsanity.com/paper/2109.03173/) (2021)
- [Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions](https://mlsanity.com/paper/2009.06136/) (2020)
- [Learning Optimal Reserve Price against Non-myopic Bidders](https://mlsanity.com/paper/1804.11060/) (2018)
- [Learning Utilities and Equilibria in Non-Truthful Auctions](https://mlsanity.com/paper/2007.01722/) (2020)
- [Perfect Bayesian Equilibria in Repeated Sales](https://mlsanity.com/paper/1409.3062/) (2014)
- [Bayesian Nash Equilibrium in First-Price Auction with Discrete Value Distributions](https://mlsanity.com/paper/1906.09403/) (2019)
- [Why Do Competitive Markets Converge to First-Price Auctions?](https://mlsanity.com/paper/2001.06074/) (2020)
- [On the Complexity of Equilibrium Computation in First-Price Auctions](https://mlsanity.com/paper/2103.03238/) (2021)
- [No-Regret Learning from Partially Observed Data in Repeated Auctions](https://mlsanity.com/paper/1912.09905/) (2019)
- [Dynamic Reserve Prices for Repeated Auctions: Learning from Bids](https://mlsanity.com/paper/2002.07331/) (2020)
- [A Game-Theoretic Analysis of the Empirical Revenue Maximization Algorithm with Endogenous Sampling](https://mlsanity.com/paper/2010.05519/) (2020)

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

- [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)
- [Learning in Repeated Multi-Unit Pay-As-Bid Auctions](https://mlsanity.com/paper/2307.15193/) (2023)
- [Games with Payments between Learning Agents](https://mlsanity.com/paper/2405.20880/) (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)
- [Learning to Coordinate Bidders in Non-Truthful Auctions](https://mlsanity.com/paper/2507.02801/) (2025)
- [Mean-based algorithms: A lower bound and regret](https://mlsanity.com/paper/2606.04931/) (2026)

## Abstract (arXiv)

The convergence properties of learning dynamics in repeated auctions is a timely and important question, with numerous applications in, e.g., online advertising markets. This work focuses on repeated first-price auctions where bidders with fixed values learn to bid using mean-based algorithms -- a large class of online learning algorithms that include popular no-regret algorithms such as Multiplicative Weights Update and Follow the Perturbed Leader. We completely characterize the learning dynamics of mean-based algorithms, under two notions of convergence: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium converges to 1; (2) last-iterate: the mixed strategy profile of bidders converges to a Nash equilibrium. Specifically, the results depend on the number of bidders with the highest value: - If the number is at least three, the dynamics almost surely converges to a Nash equilibrium of the auction, in both time-average and last-iterate. - If the number is two, the dynamics almost surely converges to a Nash equilibrium in time-average but not necessarily last-iterate. - If the number is one, the dynamics may not converge to a Nash equilibrium in time-average or last-iterate. Our discovery opens up new possibilities in the study of the convergence of learning dynamics.