Games played by Exponential Weights Algorithms
This provides theoretical guarantees for algorithm behavior in game theory, but it is incremental as it builds on existing exponential weights methods.
The paper analyzes the last-iterate convergence of exponential weights algorithms with constant learning rates in repeated games, showing that the probability of playing a strict Nash equilibrium converges to 0 or 1, and in strong coordination games, the algorithm almost surely converges to a strict Nash equilibrium.
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 $p^t$ played at stage $t$ 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 $p^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, $p^t$ converges almost surely to one of the strict Nash equilibria. We conclude with open questions.