CS364A: Algorithmic Game Theory Lecture #18: From External Regret to Swap Regret and the Minimax Theorem
Tim Roughgarden · 2013
Last lecture we proved that coarse correlated equilibria (CCE) are tractable, in a satisfy-ing sense: there are simple and computationally efficient learning procedures that converge quickly to the set of CCE. Of course, if anything in our equilibrium hierarchy (Figure 1) was going to be tractable, it was going to be CCE, the biggest set. The good researcher is never satisfied and always seeks stronger results. What can we say if we zoom in to the next-biggest set, the correlated equilibria? The first part of this lecture shows that correlated equilibria are also tractable. We’ll give computationally efficient — if not quite as simple — learning procedures that converge fairly quickly to this set. Remark 1.1 (Learning vs. Linear Programming) The computational tractability of cor-related and coarse correlated equilibria — and mixed Nash equilibria of two-player zero-sum games, see Section 3 — can also be demonstrated by formulating linear programs for them. A bonus of the linear programming approach is that an exact, rather than an approximate, equilibrium can be computed in polynomial time. Another advantage is that linear optimiza-tion over the set of equilibria remains computationally tractable, while learning procedures merely guide behavior to somewhere in the set. On the other hand, exact linear programming algorithms seem wholly unrelated to any reasonable model of how agents learn in games. Recall from Lecture 13 and Exercise 59 that a correlated equilibrium of a cost-minimization game is a distribution σ over outcomes such that, for every player i with strategy set Si and every switching function δ: Si → Si, Es∼σ[Ci(s)] ≤ Es∼σ[Ci(δ(si), s−i)]. ∗ c©2013, Tim Roughgarden.