Source
Sergiu Hart and Andreu Mas-Colell, “A simple adaptive procedure leading to correlated equilibrium”, Econometrica 68(5):1127–1150 (2000), LIT-1521, read in full in NOTE-1142: Main Theorem (p. 1131), the Proposition and Theorem A (pp. 1133–1138), and the appendix.
What was actually shown
- The procedure. Having last played j, play k ≠ j with probability R_t(j, k)/μ, where R_t(j, k) is the positive part of the average gain i would have had by playing k in every period it played j; otherwise play j. Players know their own payoffs and observe the history.
- The theorem. If all players follow it, z_t, the empirical distribution of action profiles, converges almost surely to the set of correlated equilibria.
- Why regrets are the right measure. D_t(j, k) is exactly the correlated-equilibrium constraint for (i, j, k) evaluated at z_t, so regrets vanish if and only if z_t approaches the set (Proposition, re-derived in the reading).
- What it needs. A positive probability of repeating: without it, in a 2×2 coordination game, play can alternate forever between the two miscoordinated profiles (p. 1141).
What this does not say
- That play converges to a correlated equilibrium. The time average approaches the set; it either converges to a pure Nash equilibrium or is infinitely often outside the set, and correlated equilibria that are interior and not pure Nash cannot be its limit (p. 1132).
- Which correlated equilibrium. Nothing selects among them.
- That the procedure is robust to sophisticated opponents. Only Theorem A’s invariant-distribution variant is universally calibrated.
Connections
- THEORY-414. Correlated-equilibrium play without a device or a represented rule. It supports THEORY-414’s view that equilibrium alone is not institution, and shows what adaptive play lacks: selection and stability of one equilibrium.
- CLAIM-443. Inertia as a condition of convergence, not only of persistence.