nucleation

LIT-1521: A Simple Adaptive Procedure Leading to Correlated Equilibrium

2 min read

Properties4
StatusActive — read in full 2026-10-24 (NOTE-1142) from the published article as posted on Sergiu Hart's homepage; worth reading as the theorem that correlated equilibrium is reachable by simple adaptive play: if every player switches from its last action to each alternative with probability proportional to its positive regret for not having made that switch in the past, the empirical joint distribution of play converges almost surely to the set of correlated equilibria. No device, no forecasts and no best replies are needed; the common history is the correlating device. The limits matter: convergence is to the set, not to a point; correlated equilibria that are interior and not pure Nash cannot be the limit of the empirical distribution; and the players must observe one another's past play.
Tagsgame-theory, learning-theory, anthology-candidate
Cited as “paper” byNOTE-1142 — Hart & Mas-Colell — A simple adaptive procedure leading to correlated equilibrium
Cited as “source” byTHEORY-941 — If every player of a finite game switches from its last action to each other action with probability proportional to its positive conditional regret, the empirical distribution of play converges almost surely to the set of correlated equilibria

Graph View

Hart, S. & Mas-Colell, A. (2000). A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5): 1127–1150. doi:10.1111/1468-0262.00153.

Key takeaways

From the reading, NOTE-1142. Page numbers are the journal’s.

  • Regret matching. A player’s regret R_t(j, k) is the positive part of how much better its average payoff would have been had it played k every time it played j. Next period it switches from its last action j to k with probability R_t(j, k)/μ, and otherwise repeats j (Eq. 2.2, p. 1130).
  • The theorem. If every player does this, the empirical distribution of play converges almost surely to the set of correlated equilibria (Main Theorem, p. 1131; THEORY-941).
  • Regret and correlated equilibrium are the same condition. All conditional regrets tend to zero exactly when the empirical distribution approaches the correlated-equilibrium set (Proposition, pp. 1133–1134).
  • The device is the history. “In our procedure, as in most others, there is a natural coordination device: the common history, observed by all players” (p. 1129).
  • Limits. Convergence is to a set and need not be to a point; interior correlated equilibria that are not pure Nash equilibria cannot be the limit of the empirical distribution (p. 1132); and without inertia the result fails (p. 1141).

Why this is here

Filed 2026-10-24 when the owner asked how the record stands on multi-agent reinforcement learning. THEORY-414 reads institutions as correlated equilibria that the players represent as rules. This paper shows how a correlated equilibrium can be reached with no device and no representation at all, which bears on which half of THEORY-414 does the work. It carries anthology-candidate because regret matching underlies counterfactual regret minimization in game-playing AI. It carries no instruction for ML practice.

Backlinks