跳到正文
arXiv cs.AI· Maurizio d'Andrea (TSE-R), Fabien Gensbittel (TSE-R), J\'er\^ome Renault (TSE-R)·· 2 小时前AI 评分23

指数权重算法所玩博弈的最后一迭代收敛性研究

Games played by Exponential Weights Algorithms

AI 导读

这篇发表于 Mathematics of Operations Research 的论文研究了固定学习率下指数权重算法的最后一迭代收敛性质,将离散时间重复博弈建模为齐次马尔可夫链。论文证明:当存在严格 Nash 均衡时,下一阶段执行该均衡的概率几乎必然收敛到 0 或 1;p^t 的极限若存在,必属于“等收益 Nash 均衡”集合;在强协调博弈中 p^t 几乎必然收敛到某个严格 Nash 均衡。

正文 · 原文

View PDF HTML (experimental)

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