cs.AIJul 9, 2024

Games played by Exponential Weights Algorithms

Authors: Maurizio d'Andrea, Fabien Gensbittel, Jérôme Renault

Organizations: TSE-R

Abstract

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 ptp^t played at stage tt follows an homogeneous Markov chain. At first, we show that whenever a strict Nash equilibrium exists, the probability to play a strict Nash equilibrium at the next stage converges almost surely to 0 or 1. Secondly, we show that the limit of ptp^t, whenever it exists, belongs to the set of ``Nash Equilibria with Equalizing Payoffs''. Thirdly, we show that in strong coordination games, where the payoff of a player is positive on the diagonal and 0 elsewhere, ptp^t converges almost surely to one of the strict Nash equilibria. We conclude with open questions.

Explore similar work

CardsList
  1. Stability and Convergence of Optimistic Exponential Weights with Asymmetric Step Sizes in Bimatrix Games

    Jul 8, 2026Hédi Hadiji, Sarah SachsNash EquilibriumLast-Iterate Convergence

  2. The Harder Path: Last Iterate Convergence for Uncoupled Learning in Zero-Sum Games with Bandit Feedback

    Apr 17, 2026Côme Fiegel, Pierre Ménard, Tadashi Kozuno +2Nash EquilibriumLast-Iterate Convergence