Games Played by Exponential Weights Algorithms
This paper studies the last-iterate convergence properties of the exponential weights algorithm with constant learning rates. We consider a repeated interaction in discrete time, where each player uses an exponential weights algorithm characterized by an initial mixed action and a fixed learning rate so that the mixed action profile [Formula: see text] played at stage t follows an homogeneous Markov chain. At first, we show that the probability to play a strict Nash equilibrium at the next stage converges almost surely to zero or one. Second, we show that the limit of [Formula: see text], whenever it exists, belongs to the set of Nash equilibria with equalizing payoffs. Finally, we show that in strong coordination games, where the payoff of a player is positive on the diagonal and zero elsewhere, [Formula: see text] converges almost surely to one of the strict Nash equilibria. Funding: This research benefited from financial support from the AI Institute Artificial and Natural Intelligence Toulouse Institute (ANITI) [Grants ANR-19-PI3A-0004 and ANR-23-IACL-P0002] and the ANR Chess [Grant ANR-17-EURE-0010]. J. Renault acknowledges funding from the Agence nationale de la recherche (ANR) [Grant MaSDOL-19-CE23-0017-01].
Authors
- Fabien Gensbittel (ORCID: https://orcid.org/0000-0002-0949-9456)
- Jérôme Renault (ORCID: https://orcid.org/0000-0003-2220-3143)
- Maurizio d'Andrea (ORCID: https://orcid.org/0009-0001-6918-2389)
Institutions
- National University of Singapore (SG)
- Toulouse School of Economics (FR)
- Université de Toulouse (FR)
- Université Toulouse Capitole (FR)
- Toulouse School of Economics Research (FR)
- Libera Università Internazionale degli Studi Sociali Guido Carli (IT)
Publication Details
- Journal
- Mathematics of Operations Research
- Published
- 2026-11-16
- DOI
- https://doi.org/10.1287/moor.2025.1310
- Primary Topic
- Game Theory and Applications
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Agence Nationale de la Recherche