Learning, No-Regret, and the Correlated Equilibrium¶
Job: develop the no-regret / online (OCO), the fictitious play / convergence, the correlated equilibrium (Aumann), and the replicator / ESS — with the no-regret → correlated / replicator as the worked example.
Core¶
The no-regret and the online¶
| No-regret / regret / OCO / IT | Description |
|---|---|
| No-regret | \(\frac1T\sum\ell_t(x_t)-\min\frac1T\sum\ell_t(x)\to0\) (the optimization / online) |
| OCO | the online convex optimization (the optimization / online, the information theory) |
The fictitious play and the convergence¶
| Fictitious play / best-response / convergence | Description |
|---|---|
| Fictitious play | best-response to empirical, converges in zero-sum (the dynamical systems) |
| Convergence | zero-sum / potential \(\to\) NE; general: Shapley cycles (the dynamical systems) |
The correlated and the Aumann¶
| Correlated / Aumann / public signal / IT | Description |
|---|---|
| Correlated equilibrium | Aumann: public signal, the Pareto-improve NE (the information theory) |
| Aumann | the correlated, the information theory |
The replicator and the evolutionary¶
| Replicator / ESS / Maynard Smith / dynamical | Description |
|---|---|
| Replicator dynamics | \(\dot x_i=x_i(\pi_i-\bar\pi)\) (the dynamical systems) |
| ESS | evolutionarily stable strategy, Maynard Smith (the dynamical systems) |
See it¶
No-regret → correlated equilibrium (Aumann) and the replicator / ESS. The no-regret: the \(\frac1T\sum\ell_t(x_t)-\min\frac1T\sum\ell_t(x)\to0\) (the regret \(\to0\), the optimization / online). The correlated: the no-regret \(\to\) the correlated equilibrium (the Aumann, the information theory). The replicator: the \(\dot x_i=x_i(\pi_i-\bar\pi)\) (the dynamical systems, the ESS the Maynard Smith). The key point: the no-regret the correlated, the replicator the ESS.
Check¶
Show that no-regret dynamics converge to the correlated equilibrium, and explain the Aumann.
The no-regret: the \(\frac1T\sum\ell_t(x_t)-\min\frac1T\sum\ell_t(x)\to0\) (the regret \(\to0\), the optimization / online). The correlated: the empirical distribution of the play \(\to\) the correlated equilibrium (the Aumann, the public signal the mediator, the no-regret the convergence, the information theory). The Aumann: the correlated equilibrium (the CE \(\supset\) the convex hull of NE, the Pareto-improve, the information theory). So the no-regret \(\to\) the correlated, the Aumann.
Explain the fictitious play and the replicator / ESS.
The fictitious play: the best-response to the empirical distribution (the \(\sigma_t^i=\mathrm{BR}(\bar\sigma_{-i})\), the dynamical systems). The convergence: the zero-sum / potential the convergence (the Robinson 1951), the general the Shapley cycles (the non-convergence, the dynamical systems). The replicator: the \(\dot x_i=x_i(\pi_i(x)-\bar\pi(x))\) (the fitness, the dynamical systems). The ESS: the Maynard Smith (the evolutionarily stable, the \(\pi(x,x)>\pi(y,x)\), the dynamical systems). So the fictitious the best-response, the replicator the fitness, the ESS the stable.
Pitfalls¶
- The no-regret the [optimization / online] (the regret, the optimization / online) — the no-regret the regret, the OCO the online.
- The fictitious play the convergence (the zero-sum, the dynamical systems) — the zero-sum the convergence, the general the Shapley.
- The correlated the Aumann (the public signal, the information theory) — the CE the Pareto-improve, the Aumann.
- The replicator the ESS (the fitness, the dynamical systems) — the replicator the \(\dot x\), the ESS the Maynard Smith.
Refs¶
- Aumann, "Subjectivity and correlation in randomized strategies" (1974); the correlated
- Robinson, "An iterative method for solving a game" (1951); the fictitious play
- Maynard Smith, Evolution and the Theory of Games (1982); the ESS
- Cesa-Bianchi–Lugosi, Prediction, Learning, and Games (2006); the no-regret / the optimization / online
Next¶
GT index · Foundations · Mechanism Design · Repeated & Folk · Cooperative & Combinatorial · Optimization / online · Dynamical systems · Information theory