No-regret dynamics and fictitious play

Yannick Viossat; Andriy Zapechelnyuk

doi:10.1016/j.jet.2012.07.003

No-regret dynamics and fictitious play

Yannick Viossat, Andriy Zapechelnyuk^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

Abstract

Potential based no-regret dynamics are shown to be related to fictitious play. Roughly, these are ε-best reply dynamics where ε 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.

Original language	English
Pages (from-to)	825-842
Number of pages	18
Journal	Journal of Economic Theory
Volume	148
Issue number	2
DOIs	https://doi.org/10.1016/j.jet.2012.07.003
Publication status	Published - Mar 2013

Keywords

Best-reply dynamics
Curb set
Fictitious play
Hannan set
Nash equilibrium
No-regret strategy
Regret minimization

Access to Document

10.1016/j.jet.2012.07.003

Cite this

@article{2a929711c7994736bcd7243773adb62d,

title = "No-regret dynamics and fictitious play",

abstract = "Potential based no-regret dynamics are shown to be related to fictitious play. Roughly, these are ε-best reply dynamics where ε 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.",

keywords = "Best-reply dynamics, Curb set, Fictitious play, Hannan set, Nash equilibrium, No-regret strategy, Regret minimization",

author = "Yannick Viossat and Andriy Zapechelnyuk",

year = "2013",

month = mar,

doi = "10.1016/j.jet.2012.07.003",

language = "English",

volume = "148",

pages = "825--842",

journal = "Journal of Economic Theory",

issn = "0022-0531",

publisher = "Academic Press/Elsevier ",

number = "2",

}

TY - JOUR

T1 - No-regret dynamics and fictitious play

AU - Viossat, Yannick

AU - Zapechelnyuk, Andriy

PY - 2013/3

Y1 - 2013/3

N2 - Potential based no-regret dynamics are shown to be related to fictitious play. Roughly, these are ε-best reply dynamics where ε 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.

AB - Potential based no-regret dynamics are shown to be related to fictitious play. Roughly, these are ε-best reply dynamics where ε 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.

KW - Best-reply dynamics

KW - Curb set

KW - Fictitious play

KW - Hannan set

KW - Nash equilibrium

KW - No-regret strategy

KW - Regret minimization

UR - http://www.scopus.com/inward/record.url?scp=84875375293&partnerID=8YFLogxK

U2 - 10.1016/j.jet.2012.07.003

DO - 10.1016/j.jet.2012.07.003

M3 - Article

AN - SCOPUS:84875375293

SN - 0022-0531

VL - 148

SP - 825

EP - 842

JO - Journal of Economic Theory

JF - Journal of Economic Theory

IS - 2

ER -

No-regret dynamics and fictitious play

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this