跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2407.06676 · v2

Games played by Exponential Weights Algorithms

首次提交 2024-07-09 16:49
版本更新 2026-11-18 13:13
雷达观测 2026-11-19 19:08
arXiv ↗PDF ↗

摘要

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.

作者备注:Published in Mathematics of Operations Research. Revised version with minor corrections and improvements in presentation

期刊信息:Mathematics of Operations Research (2026), Articles in Advance

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-18 13:13 · 最新观测版本

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 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.

查看此版本解读 →查看此版本原文 ↗