What the paper does
Correlated equilibrium (pp. 1127–1129). A distribution ψ over action profiles such that, for each player i and each pair of its actions j, k, Σ_{s: s_i = j} ψ(s)[u_i(k, s_−i) − u_i(s)] ≤ 0: following a private instruction from a device is a best response given that others follow theirs. Nash equilibria are the product distributions among them. The set is a convex polytope, and in a game like chicken it can contain distributions outside the convex hull of the Nash equilibria. The authors add that “it is hard to exclude a priori the possibility that correlating signals are amply available to the players, and thus find their way into the equilibrium” (p. 1128).
The procedure (pp. 1130–1131). Each player knows its own payoff function and the history of play. D_t(j, k) is the average, over periods 1 to t, of what it would have gained by playing k in every period it played j; R_t(j, k) is its positive part. Having last played j, the player plays k ≠ j with probability R_t(j, k)/μ and j with the rest, μ being a constant large enough that repeating always has positive probability.
Main Theorem (p. 1131). If every player uses the procedure, the empirical distributions z_t of play converge almost surely to the set of correlated equilibria. That is, for every ε the trajectory eventually stays within ε of the set; it need not converge to a point.
Regret is the gap from correlated equilibrium (Proposition, pp. 1133–1134). D_t(j, k) = Σ_{s: s_i = j} z_t(s)[u_i(k, s_−i) − u_i(j, s_−i)], so all regrets have limsup ≤ ε exactly when z_t approaches the correlated ε-equilibria. I re-derived it: grouping the periods in which i played j by the profile played gives the sum, which is the correlated-equilibrium constraint evaluated at z_t.
Theorem A, the stylized procedure (pp. 1132–1138). If a player plays the invariant distribution q of its regret transition matrix, Σ_k q(k)R(k, j) = q(j)Σ_k R(j, k), its regrets go to zero almost surely whatever the others do. The proof applies Blackwell’s approachability theorem to the vector of payoff differences with the nonpositive orthant as target: with λ the regret vector, Σ_{(j,k)} λ(j, k)q(j)[u(k, ·) − u(j, ·)] collects to Σ_j u(j, ·)[Σ_k q(k)λ(k, j) − q(j)Σ_k λ(j, k)], which the invariance makes zero. I checked the collection of terms. Expected regrets are of order 1/√t. Unconditional regret matching (Theorem B, proof omitted) gives Hannan consistency.
Discussion (pp. 1138–1143). Earlier procedures reaching correlated equilibrium (Foster and Vohra; Fudenberg and Levine) are best-reply based and need an eigenvector computation each step; this one plays all better replies in proportion to their regret. Its “inertia” and “friction” are essential: if one rescales so that a player switches whenever any regret is positive, then in a 2×2 coordination game started uncoordinated “the play alternates between the two uncoordinated pairs” (p. 1141), and no distribution on those pairs is a correlated equilibrium. The breaking of the cycle “is obtained not by ergodic arguments but by the probability of staying put” (p. 1141). The main procedure is not universally calibrated: an opponent who knows it can keep its regrets positive. With trembles of size δ, the limit is the set of correlated ε(δ)-equilibria. A variant for a player who does not know the game and sees only its own payoffs is sketched, with the formal treatment in a companion paper.
Appendix. The Main Theorem’s procedure does not satisfy Blackwell’s condition each period, so the proof works over blocks of periods, comparing the actual process with one whose transition matrix is frozen at period t, and uses the fact that a stochastic matrix with positive diagonal has Π^{w+1} − Π^w = O(w
What it establishes and what it does not
It establishes a theorem: a simple, separable, better-reply procedure with inertia drives the time-averaged joint distribution of play into the correlated-equilibrium set. It does not establish that play converges to any particular correlated equilibrium, or to one at all as a point. By the authors’ comment (4), the empirical distribution either converges to a pure Nash equilibrium or is infinitely often outside the set, so that interior “points of the set of correlated equilibria that are not pure Nash equilibria are unreachable as the limit” of the empirical distributions, though they may be limits of a subsequence (p. 1132). It says nothing about which correlated equilibrium is approached, about speed in the main procedure, or about players who do not see one another’s play, beyond a sketch.
How it bears on the record
- Institutions as correlated equilibria (THEORY-414). It complicates THEORY-414 and supports its representation condition. Hindriks and Guala’s institution is a correlated equilibrium of a coordination game, with the device a rule the players represent (LIT-481). Here a correlated equilibrium is approached with no device, no rule and no representation: the shared history does the correlating, and each player only tracks its own regrets. So correlated-equilibrium play is cheap. Reaching it does not need anything like an institution, which supports THEORY-414’s insistence that representation, not equilibrium, is what separates an institution from the butterflies’ bourgeois convention. It also shows what such adaptive play does not give: the empirical distribution need not settle on one equilibrium, and it cannot settle on most of the mixed ones. A rule that picks one correlated equilibrium and holds it does work that regret matching does not. That bears on THEORY-414’s promote_when, which asks for a test that separates human institutions from animal correlated equilibria. Regret-matching play is a third baseline, between them.
- Inertia (CLAIM-443). The claim reads the owner’s momentum term as a switching cost that resists small transient changes. Here inertia is more than persistence: a positive probability of repeating is what breaks the miscoordination cycle and makes convergence possible. It supports the claim’s switching-cost reading and adds a function the claim does not name.
- Cycles (CLAIM-451). An exact example of the claim’s distinction. Switching to the better reply whenever there is one cycles between miscoordinated profiles; the same rule with friction does not. Whether the record of winning moves cycles depends on the update rule as well as on the game.
- Lock-in (CLAIM-446). Regret matching uses counterfactual payoffs, what k would have earned in the periods j was played, so evidence about unchosen actions keeps arriving. That is the condition under which the protective-regime trap cannot form. The unknown-game variant, which estimates counterfactuals from the periods k was actually played, reweighted by play probabilities, is the case in which that evidence has to be gathered by playing k, as in the trap; the paper only sketches it.
- Replicator readings (CLAIM-444). Not a replicator dynamic. It is a better-reply process on actions, with convergence of time averages, and sits beside the replicator tools rather than among them.