The Query Complexity of Correlated Equilibria

on YouTube ↗27m

" summary

Correlated equilibria with two actions per player admit randomized algorithms find ε-CE with poly(n) queries, produced by regret‑based dynamics that run O((log n)/ε^2) steps and yield an empirical distribution of support O((log n)/ε^2). By contrast deterministic or exact algorithms require Ω(2^n) queries (or count support plus queries) via a hypercube construction that labels edges by regrets and a hypercube random-path construction that hides the unique exact equilibrium endpoint, forcing exponential pure‑query exploration.

AI-written summary · about

" chapters (6)

1. 0:00Start
2. 8:04Correlated Equilibria (recall)
3. 8:52Query Complexity of CE
4. 15:44Query Complexity of COARSE CE
5. 16:08Idea of Proof of Theorem A
6. 17:03Idea of Proof of Theorem B