How to cite

@misc{mit-multiagent-learning-lecture-S2,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Supplementary reading S2: A second look at the minimax theorem},
  booktitle = {MIT Topics in Multiagent Learning Lecture Notes},
  note = {MIT 6.7980, Fall 2026},
  year = {2026},
  url = {https://www.mit.edu/~6.7980/eah.html}
}

Supplementary reading S2

A second look at the minimax theorem

Instructor

Prof. Gabriele Farina (gfarina@mit.edu)

Edition

Fall 2026

Definition L3.9 introduced the notion of coarse correlated equilibria. As we discussed, coarse correlated equilibria sidestep various difficulties (including topological and related to use of irrational numbers) that come with Nash equilibria. In this lecture, we show a powerful centralized algorithm for computing coarse correlated equilibria. (Soon in this course, we will also see that coarse correlated equilibria can also be learned efficiently in a distributed multi-agent setting (Section L4.2.4).)

The CCE incentive constraints (Section L3.2.1) give a linear program for computing a coarse correlated equilibrium, in which the variables correspond to the probabilities $\mu_{a_{1} , \dots , a_{n}}$ of the joint actions, and the constraints correspond to the incentive constraints of the players. While this is a perfectly valid way to compute a coarse correlated equilibrium, it has the drawback that the linear program has a number of variables that is exponential in the number of players. This becomes an issue quickly, if we want to consider games with many players. It also is a problem for those games in which the payoff tensor has a succinct representation (for example, a sparse factorization that we can exploit); there, we would ideally want an algorithm that runs in polynomial time in the size of such a succinct representation. The latter is often the case in structured games, which we will see later in this course.

In this lecture, we will see a different algorithm for computing coarse correlated equilibria, which does not suffer from the above issues and requires a number of variables that scales with the sum (rather than product!) of the number of actions of the players. The algorithm is called Ellipsoid-Against-Hope, and was introduced by Papadimitriou and Roughgarden [PR08[PR08] Papadimitriou, C. H., & Roughgarden, T. (2008). Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3), 1–29.], with later extensions by other authors [JL11[JL11] Jiang, A. X., & Leyton-Brown, K. (2011). Polynomial-time computation of exact correlated equilibrium in compact games. Proceedings of the 12th ACM Conference on Electronic Commerce, 119–126.; HV08[HV08] Huang, W., & Stengel, B. von. (2008). Computing an extensive-form correlated equilibrium in polynomial time. International Workshop on Internet and Network Economics, 506–513.; FP24[FP24] Farina, G., & Pipis, C. (2024). Polynomial-Time Computation of Exact Φ-Equilibria in Polyhedral Games. Neural Information Processing Systems (Neurips).].

The algorithm is based on a constructive proof of the minimax theorem, which we will also present in this lecture.

S2.1 Revisiting the existence of coarse correlated equilibria

In order to understand why there is hope to compute coarse correlated equilibria more efficiently, it is useful to understand better how we can prove that these equilibria exist in the first place. We will then turn such an existence proof into a computational algorithm.

So far, we have justified the existence of coarse correlated and correlated equilibria through the existence of Nash equilibria. However, one might wonder if there is a more direct way to prove the existence of CEs and CCEs, which does not rely on the existence of a much harder notion. The answer is yes, and the idea comes from a very neat proof by Hart and Schmeidler [HS89[HS89] Hart, S., & Schmeidler, D. (1989). Existence of Correlated Equilibria. Mathematics of Operations Research, 14(1), 18–25. link], which includes some ideas that will set the stage for the Ellipsoid-Against-Hope algorithm.

While the original proof of Hart and Schmeidler [HS89] is for CE, I will present here a version of the proof simplified for the case of CCEs.

As a reminder, by definition a coarse correlated equilibrium is a distribution $\boldsymbol{\mu } \in \Delta (A_{1} \times \dots \times A_{n})$ such that

\displaystyle \mathbb{E}_{a \sim \boldsymbol{\mu }} \left[u_{i} \left(a_{i}' , a_{- i}\right)\right] \le \mathbb{E}_{a \sim \boldsymbol{\mu }} \left[u_{i} \left(a_{i} , a_{- i}\right)\right] \qquad \forall i \in \left[ n \right] , a_{i}' \in A_{i} ,

or equivalently,

\displaystyle \operatorname*{max}_{\substack{i \in \left[ n \right]\\ a_{i}' \in A_{i}}} \mathbb{E}_{a \sim \boldsymbol{\mu }} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] \le 0 .

A CCE then exists if and only if

\displaystyle \operatorname*{min}_{\boldsymbol{\mu }} \operatorname*{max}_{\substack{i \in \left[ n \right]\\ a_{i}' \in A_{i}}} \mathbb{E}_{a \sim \boldsymbol{\mu }} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] \le 0 .

How can we prove the above inequality without resorting to the existence of Nash equilibria? The rescue comes from the minimax theorem.

Before we can use the minimax theorem, we have to “convexify” the inner problem however, since the maximum is currently on a discrete set. To convexity the problem, we will simply allow the possibility for the internal maximumization problem to propose a distribution $\boldsymbol{ν}$ over deviations $(i , a_{i})$ , and we will rewrite the problem as

\displaystyle \operatorname*{min}_{\boldsymbol{\mu }} \operatorname*{max}_{\boldsymbol{ν}} \mathbb{E}_{a \sim \boldsymbol{\mu }} \mathbb{E}_{\left( i , a_{i}' \right) \sim \boldsymbol{ν}} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] \le 0 .

By the minimax theorem and swapping the order of the expectations, the above min-max value is equal to

\displaystyle \operatorname*{max}_{\boldsymbol{ν}} \operatorname*{min}_{\boldsymbol{\mu }} \mathbb{E}_{\left( i , a_{i}' \right) \sim \boldsymbol{ν}} \mathbb{E}_{a \sim \boldsymbol{\mu }} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] .

Can we show that this value is $\le 0$ ? The answer is yes, and constructive: given any $\boldsymbol{ν}$ , we can find a $\boldsymbol{\mu }$ in closed form—in fact, a product distribution—such that the value is $\le 0$ .

Theorem S2.1 (Hart and Schmeidler [HS89]) .

Given any distribution $\boldsymbol{ν}$ over pairs $(i , a_{i}') : i \in [ n ] , a_{i}' \in A_{i}$ , we can explicitly and efficiently construct a product distribution $\boldsymbol{\mu } \in \Delta ( A_{1} ) ⊗ \dots ⊗ \Delta ( A_{n} )$ such that

\displaystyle \mathbb{E}_{\left( i , a_{i}' \right) \sim \boldsymbol{ν}} \mathbb{E}_{a \sim \boldsymbol{\mu }} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] \le 0 .

The above theorem immediately implies that

\displaystyle \operatorname*{max}_{\boldsymbol{ν}} \operatorname*{min}_{\boldsymbol{\mu }} \mathbb{E}_{\left( i , a_{i}' \right) \sim \boldsymbol{ν}} \mathbb{E}_{a \sim \boldsymbol{\mu }} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] \le 0 ,

and using the minimax theorem, we conclude the existence of coarse correlated equilibria.

S2.2 Turning the minimax theorem into an efficient algorithm

As in the analysis of the existence proof underlying Nash equilibrium (Section L2.2), it is worth inspecting where the “magic” happens in the above proof. If we squint our eyes a bit, the argument of the proof looked like this:

We want to prove that $\operatorname*{min}_{\boldsymbol{\mu }} \operatorname*{max}_{\boldsymbol{ν}} g ( \boldsymbol{\mu } , \boldsymbol{ν} ) \le 0$ , for an appropriate $$g$$ that is linear in both $\boldsymbol{\mu }$ and $\boldsymbol{ν}$ . That is, we want to show that there exists a $\boldsymbol{\mu }$ such that for all $\boldsymbol{ν}$ , $g ( \boldsymbol{\mu } , \boldsymbol{ν} ) \le 0$ .
To do that, we instead show that for all $\boldsymbol{ν}$ , there exists a $\boldsymbol{\mu }$ (dependent on $\boldsymbol{ν}$ ) such that $g ( \boldsymbol{\mu } , \boldsymbol{ν} ) \le 0$ . This shows that $\operatorname*{max}_{\boldsymbol{ν}} \operatorname*{min}_{\boldsymbol{\mu }} g ( \boldsymbol{\mu } , \boldsymbol{ν} ) \le 0$ .
Then, we use the minimax theorem to swap the order of the quantifiers, and conclude that $\operatorname*{min}_{\boldsymbol{\mu }} \operatorname*{max}_{\boldsymbol{ν}} g ( \boldsymbol{\mu } , \boldsymbol{ν} ) \le 0$ . The use of the minimax theorem in our case was justified because $g ( \boldsymbol{\mu } , \boldsymbol{ν} )$ is linear in both $\boldsymbol{\mu }$ and $\boldsymbol{ν}$ .

It is easy to brush away swapping the order of the quantifiers as just one of the many results in mathematics that are concerned with swapping orders of operators. But let us stop to consider how powerful this is. The original problem was to find a single $\boldsymbol{\mu }^{∗}$ that works for all $\boldsymbol{ν}$ (Step 1). However, the minimax theorem (Step 3) tells us that as long as for any specific $\boldsymbol{ν}$ we can construct a $\boldsymbol{\mu } ( \boldsymbol{ν} )$ that works for that $\boldsymbol{ν}$ specifically, then a $\boldsymbol{\mu }^{∗}$ that works for any $\boldsymbol{ν}$ (not for one specific) must exist (Step 2). It feels way less simple than it looks at first sight, right?

The Ellipsoid-Against-Hope algorithm can then be seen as a way to convert the minimax theorem from a tool guaranteeing existence into a computational algorithm. In particular, the idea is the following:

We will query a few “well-chosen” distributions $\boldsymbol{ν}_{t}$ , and for each of them, construct the corresponding $\boldsymbol{\mu } ( \boldsymbol{ν}_{t} )$ that works for that specific $\boldsymbol{ν}_{t}$ . The number of queries will be small, polynomial in the sum of the number of actions of the players and $\operatorname{log} ( 1 / \epsilon )$ .
Then, we will combine all the $\boldsymbol{\mu } ( \boldsymbol{ν}_{t} )$ we have constructed into a single $\boldsymbol{\mu }^{∗}$ that works for all $\boldsymbol{ν}$ . In particular, the $\boldsymbol{\mu }^{∗}$ will be a convex combination of the $\boldsymbol{\mu } ( \boldsymbol{ν}_{t} )$ we have constructed, with coefficients that can be computed efficiently by solving a linear program with a number of variables that is again polynomial in the sum of the number of actions of the players and $\operatorname{log} ( 1 / \epsilon )$ .

Combining the two steps above, we will have constructed a $\boldsymbol{\mu }^{∗}$ that is an $\epsilon$ -coarse correlated equilibrium, and that can be represented as a convex combination of product distributions. In other words, we have shown the following corollary.

Corollary S2.2 .

Assume rational, bounded payoffs and an oracle that evaluates expected payoffs under product distributions in polynomial time. Then an

\epsilon

-coarse correlated equilibrium can be computed in time polynomial in the representation size, payoff encoding length, the sum of the numbers of actions, and

\operatorname{log} ( 1 / \epsilon )

. Such a coarse correlated equilibrium is represented as a convex combination of product distributions.

S2.2.1 Sketch of the Ellipsoid-Against-Hope algorithm

In more detail, what Theorem S2.1 implies is that the following open polytope must be empty:

\displaystyle \left\{\begin{gathered}\boldsymbol{ν} \in \Delta \left\{\left(i , a_{i}'\right) : i \in \left[ n \right] , a_{i} \in A_{i}\right\} : \mathbb{E}_{\left( i , a_{i}' \right) \sim \boldsymbol{ν}} \mathbb{E}_{a \sim \boldsymbol{\mu }} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] > 0\\ \forall \boldsymbol{\mu } \in \Delta \left(A_{1} \times \dots \times A_{n}\right)\end{gathered}\right\} .

Furthermore, for any $\boldsymbol{ν}$ , we know how to prove that at least one of the constraints is violated. The key idea is then to use the ellipsoid method to certify the emptiness of the polytope. Normally, the ellipsoid method is used to find a point in a set, but in our case, the point does not exist and we want to use the ellipsoid method to isolate constraints that prove the emptiness of the set. For this reason, the algorithm was called Ellipsoid-Against-Hope by Papadimitriou and Roughgarden [PR08].

The ellipsoid will maintain a search space which can be thought of as a suitable subset of the deviator’s set. At every iteration $$t$$ , the algorithm will compute the center point $\boldsymbol{ν}_{t}$ of the set. Then, it will find a violated constraint using the distribution $\boldsymbol{\mu }_{t} \coloneqq \boldsymbol{\mu } ( \boldsymbol{ν}_{t} )$ in the proof of Theorem S2.1. The violated constraint implies that the deviator set must be curtailed, and the ellipsoid will be updated accordingly reducing the size of the search space by a constant. The algorithm will continue until the search space is small enough to guarantee that the set is empty. The iteration count also depends polynomially on the dimension and encoding/conditioning bounds. For an approximate guarantee, use constraints with a positive $\epsilon$ margin and the corresponding separation and volume bounds; shrinking an arbitrary open set does not by itself certify exact emptiness. The following algebra describes the exact finite certificate when one has been obtained. By the last iteration $$T$$ , the algorithm will have produced several violated constraints, each of which is associated with a mediator strategy $\boldsymbol{\mu }_{t}$ . The set

\displaystyle \left\{\begin{gathered}\boldsymbol{ν} \in \Delta \left\{\left(i , a_{i}\right) : i \in \left[ n \right] , a_{i} \in A_{i}\right\} : \mathbb{E}_{\left( i , a_{i}' \right) \sim \boldsymbol{ν}} \mathbb{E}_{a \sim \boldsymbol{\mu }_{1}} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] > 0\\ ⋮\\ \mathbb{E}_{\left( i , a_{i}' \right) \sim \boldsymbol{ν}} \mathbb{E}_{a \sim \boldsymbol{\mu }_{T}} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] > 0\end{gathered}\right\} .

The constraints of the set are all linear in $\boldsymbol{ν}$ , and the set is empty. By Farkas’ lemma, there must exist a convex combination of the constraints the makes all the coefficients on the left-hand size non-positive. In other words, there must exist $\alpha_{1} , \dots , \alpha_{T} \ge 0$ with $\sum_{t} \alpha_{t}=1$ such that

\displaystyle \sum_{t = 1}^{T} \alpha_{t} \mathbb{E}_{a \sim \boldsymbol{\mu }_{t}} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] \le 0 , \qquad \forall i \in \left[ n \right] , a_{i}' \in A_{i} .

Letting $\hat{\boldsymbol{\mu }} \coloneqq \sum_{t = 1}^{T} \alpha_{t} \boldsymbol{\mu }_{t}$ , we can then write

\displaystyle \mathbb{E}_{a \sim \hat{\boldsymbol{\mu }}} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] \le 0 , \qquad \forall i \in \left[ n \right] , a_{i}' \in A_{i} ,

and hence $\hat{\boldsymbol{\mu }}$ is a coarse correlated equilibrium. The only question is whether this combination $\{\alpha_{t}\}$ can computed efficiently. This is indeed the case, as we can use linear programming directly to find such a combination, by solving the feasibility program

\displaystyle \mathord{\operatorname{find}}

\displaystyle \alpha_{1} , \dots , \alpha_{T} \ge 0

\displaystyle \mathord{\text{s.t.}}

\displaystyle \sum_{t = 1}^{T} \alpha_{t} \mathbb{E}_{a \sim \boldsymbol{\mu }_{t}} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] \le 0 \qquad \forall i \in \left[ n \right] , a_{i}' \in A_{i}

\displaystyle \alpha_{1} + \dots + \alpha_{T} = 1 .

This completes the sketch of the proof of the correctness of the Ellipsoid-Against-Hope algorithm.

S2.2.2 Applications beyond normal-form games

The above argument mostly uses ideas from convex optimization. In particular, it extends, with suitable oracle and encoding assumptions, to multilinear games on compact convex domains, that is, any setting with the following properties:

Player $$i$$ ‘s strategy set is a nonempty compact convex set of some dimension $d_{i}$ , with suitable rational descriptions or geometric bounds for the ellipsoid method. For normal-form games, a strategy is an element of $\Delta ( A_{i} )$ , that is, a distribution over the player’s strategies. We assume an efficient separation oracle with the bit-complexity and geometric bounds required by convex optimization.
The utility function $u_{i} ( \boldsymbol{x}_{1} , \dots , \boldsymbol{x}_{n} )$ is linear in each player’s strategy. For normal-form games, this is true since the utility is just an expectation.
The utility function $u_{i} ( \boldsymbol{x}_{1} , \dots , \boldsymbol{x}_{n} )$ can be evaluated efficiently, let’s say in time $$R$$ .

The Ellipsoid-Against-Hope algorithm can then be applied and has polynomial complexity in $\sum_{i}^{n} d_{i}$ , oracle costs, encoding and geometric bounds, and $\operatorname{log} ( 1 / \epsilon )$ . Applications include polymatrix games and finite perfect-recall extensive-form games; a succinct game representation must be checked for the required oracles before applying the result. We will see some of these games later in this course.

S2.3 Bibliographic remarks

If you are curious to read more, the following papers contains extensions and refinements of the idea of Ellipsoid-Against-Hope.

[PR08]	Papadimitriou, C. H., & Roughgarden, T. (2008). Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3), 1–29.
[JL11]	Jiang, A. X., & Leyton-Brown, K. (2011). Polynomial-time computation of exact correlated equilibrium in compact games. Proceedings of the 12th ACM Conference on Electronic Commerce, 119–126.
[HV08]	Huang, W., & Stengel, B. von. (2008). Computing an extensive-form correlated equilibrium in polynomial time. International Workshop on Internet and Network Economics, 506–513.
[FP24]	Farina, G., & Pipis, C. (2024). Polynomial-Time Computation of Exact Φ-Equilibria in Polyhedral Games. Neural Information Processing Systems (Neurips).
[HS89]	Hart, S., & Schmeidler, D. (1989). Existence of Correlated Equilibria. Mathematics of Operations Research, 14(1), 18–25. link

S2.A Appendix: Proof of Theorem S2.1

Let $s_{i}=\sum_{a_{i} \in A_{i}} ν_{i,a_{i}}$ be the total mass assigned to player $$i$$ ‘s deviations. If $s_{i}>0$ , set $\mu_{i}(a_{i})=\frac{ν_{i,a_{i}}}{s_{i}}$ ; if $s_{i}=0$ , choose any distribution $\boldsymbol{\mu }_{i}$ on $A_{i}$ . Let $\boldsymbol{\mu }=\boldsymbol{\mu }_{1} \times \dots \times \boldsymbol{\mu }_{n}$ be their product distribution.

For $s_{i}>0$ , averaging the deviating action according to $\frac{\boldsymbol{ν}_{i,⋅}}{s_{i}}$ is exactly the same as drawing it from $\boldsymbol{\mu }_{i}$ , independently of the opponents. Therefore

\displaystyle \sum_{a_{i}'} ν_{i,a_{i}'} \mathop{\mathbb{E}}\limits_{a \sim \boldsymbol{\mu }}\left[u_{i}\left(a_{i}',a_{-i}\right)-u_{i}\left(a_{i},a_{-i}\right)\right] = s_{i}\left(\mathop{\mathbb{E}}\limits_{a \sim \boldsymbol{\mu }}\left[u_{i}\left(a\right)\right]-\mathop{\mathbb{E}}\limits_{a \sim \boldsymbol{\mu }}\left[u_{i}\left(a\right)\right]\right)=0.

If $s_{i}=0$ , the same expression is zero because all its coefficients vanish. Sum over players to obtain the theorem, with equality. This normalization also handles zero-mass players, for whom an unnormalized product of the $\boldsymbol{ν}$ entries would not define a probability distribution.