Regret Matching → Correlated Equilibrium

Hart & Mas-Colell (2000) — No-regret learning converges to correlated equilibrium

Chicken Game — Mixed Strategy Distribution

Cumulative Regret Over Time

Joint Action Frequency (Empirical CE)

Algorithm & Statistics

Regret Matching:
Ri+(a→a') = [Ui(a',a-i) − Ui(a)] / t
σi(a') ∝ max(0, Ri+(a→a'))
CE condition: E[ui(si,s-i)] ≥ E[ui(si',s-i)]
Time-avg converges to CE set as t→∞
Iterations0
P1 avg regret0.000
P2 avg regret0.000
CE violation0.000
Nash distance0.000