No-regret dynamics and fictitious play

• 成果类型: Article
• 署名作者: Viossat, Yannick; Zapechelnyuk, Andriy
• 署名单位: Universite PSL; Universite Paris-Dauphine; University of London
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2012.07.003
• 发表日期: 2013
• 页码: 825-842
• 关键词: Regret minimization; No-regret strategy; Fictitious play; Best-reply dynamics; Nash equilibrium; Hannan set; Curb set

摘要

Potential based no-regret dynamics are shown to be related to fictitious play. Roughly, these are epsilon-best reply dynamics where a is the maximal regret, which vanishes with time. This allows for alternative and sometimes much shorter proofs of known results on convergence of no-regret dynamics to the set of Nash equilibria. (C) 2013 Elsevier Inc. All rights reserved.