Games played by Exponential Weights Algorithms
<|reference_start|>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 $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.<|reference_end|>
@article{d'andrea2024games,
    title={Games played by Exponential Weights Algorithms},
    author={Maurizio d'Andrea, Fabien Gensbittel (TSE-R), J'er^ome Renault
  (TSE-R)},
    journal={arXiv preprint arXiv:2407.06676},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.06676},
    primaryClass={cs.AI math.PR}
}