arXiv cs.AI· Maurizio d'Andrea (TSE-R), Fabien Gensbittel (TSE-R), J\'er\^ome Renault (TSE-R)·· 10 小时前AI 评分18
指数权重算法在重复博弈中的末次迭代收敛性研究
Games played by Exponential Weights Algorithms
AI 导读
论文研究恒定学习率下指数权重算法的末次迭代收敛性,证明只要存在严格 Nash 均衡,下一阶段选择该均衡的概率几乎必然收敛至 0 或 1。算法产生的混合动作序列极限若存在,必属于"收益均等 Nash 均衡"集合;在强协调博弈中,该序列几乎必然收敛到某个严格 Nash 均衡。成果已发表于 Mathematics of Operations Research。
正文 · 原文
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 $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.
| Comments: | Published in Mathematics of Operations Research. Revised version with minor corrections and improvements in presentation |
| Subjects: | Artificial Intelligence (cs.AI); Probability (math.PR) |
| MSC classes: | 91A25, 60J05 |
| Cite as: | arXiv:2407.06676 [cs.AI] |
| (or arXiv:2407.06676v2 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2407.06676 arXiv-issued DOI via DataCite |
|
| Journal reference: | Mathematics of Operations Research (2026), Articles in Advance |
| Related DOI: | https://doi.org/10.1287/moor.2025.1310
DOI(s) linking to related resources |
Submission history
From: Maurizio D'Andrea [view email] [via CCSD proxy]
[v1]
Tue, 9 Jul 2024 08:49:51 UTC (32 KB)
[v2]
Wed, 18 Nov 2026 05:13:42 UTC (30 KB)
来源:arXiv cs.AI · arxiv.org