Correlated Equilibrium (Aumann 1974)
CE conditions (no regret to deviate):
∀a_i, a_i': Σ_{a_{-i}} p(a)·[u_i(a) - u_i(a_i',a_{-i})] ≥ 0
p(a): joint distribution over actions
CE polytope ⊇ conv(Nash equilibria)
Regret minimization → CE:
If all players use no-regret algorithms,
time-avg play converges to CE set
Traffic light: CE with p(go,stop)=
p(stop,go)=1/2, social optimum!
Correlated equilibrium generalizes Nash: a mediator draws a joint action profile from distribution p and privately tells each player their action. If no player can profitably deviate given their recommendation, p is a CE. Every Nash equilibrium is a CE, but the CE set is strictly larger — and contains social optima unreachable by Nash play alone.