Games Played by Exponential Weights Algorithms

Published Online:https://doi.org/10.1287/moor.2025.1310

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 pt 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 pt, 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, pt 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].

INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.