How to cite

@misc{mit-multiagent-learning-lecture-S1,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Supplementary reading S1: 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 S1

A second look at the minimax theorem

Instructor

Prof. Gabriele Farina

Edition

Fall 2026

In Lecture 3, we 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 multi-agent setting, in a distributed fashion.)

We have seen at the end of Lecture 3 that a coarse correlated equilibrium can be computed by solving a linear program, 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 $\Phi$ -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.

S1.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 $\mu \in \Delta (A_{1} \times \dots \times A_{n})$ such that

\displaystyle \mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i}' , a_{- i}\right)\right] \le \mathbb{E}_{a \sim \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}_{i \in \left[ n \right]\\ a_{i}' \in A_{i}} \mathbb{E}_{a \sim \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}_{\mu} \operatorname*{max}_{i \in \left[ n \right]\\ a_{i}' \in A_{i}} \mathbb{E}_{a \sim \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 $$ν$$ over deviations $(i , a_{i})$ , and we will rewrite the problem as

\displaystyle \operatorname*{min}_{\mu} \operatorname*{max}_{ν} \mathbb{E}_{a \sim \mu} \mathbb{E}_{\left( i , a_{i}' \right) \sim ν} \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}_{ν} \operatorname*{min}_{\mu} \mathbb{E}_{\left( i , a_{i}' \right) \sim ν} \mathbb{E}_{a \sim \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 $$ν$$ , we can find a $\mu$ in closed form—in fact, a product distribution—such that the value is $\le 0$ .

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

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

\displaystyle \mathbb{E}_{\left( i , a_{i}' \right) \sim ν} \mathbb{E}_{a \sim \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}_{ν} \operatorname*{min}_{\mu} \mathbb{E}_{\left( i , a_{i}' \right) \sim ν} \mathbb{E}_{a \sim \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.

S1.2 Turning the minimax theorem into an efficient algorithm

Like what we did for the Nash equilibrium in Lecture 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}_{\mu} \operatorname*{max}_{ν} g ( \mu , ν ) \le 0$ , for an appropriate $$g$$ that is linear in both $\mu$ and $$ν$$ . That is, we want to show that there exists a $\mu$ such that for all $$ν$$ , $g ( \mu , ν ) \le 0$ .
To do that, we instead show that for all $$ν$$ , there exists a $\mu$ (dependent on $$ν$$ ) such that $g ( \mu , ν ) \le 0$ . This shows that $\operatorname*{max}_{ν} \operatorname*{min}_{\mu} g ( \mu , ν ) \le 0$ .
Then, we use the minimax theorem to swap the order of the quantifiers, and conclude that $\operatorname*{min}_{\mu} \operatorname*{max}_{ν} g ( \mu , ν ) \le 0$ . The use of the minimax theorem in our case was justified because $g ( \mu , ν )$ is linear in both $\mu$ and $$ν$$ .

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 $\mu^{∗}$ that works for all $$ν$$ (Step 1). However, the minimax theorem (Step 3) tells us that as long as for any specific $$ν$$ we can construct a $\mu ( ν )$ that works for that $$ν$$ specifically, then a $\mu^{∗}$ that works for any $$ν$$ (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 $ν_{t}$ , and for each of them, construct the corresponding $\mu ( ν_{t} )$ that works for that specific $ν_{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 $\mu ( ν_{t} )$ we have constructed into a single $\mu^{∗}$ that works for all $$ν$$ . In particular, the $\mu^{∗}$ will be a convex combination of the $\mu ( ν_{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 $\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 S1.2 .

There exists an algorithm that computes an

\epsilon

-coarse correlated equilibrium in time polynomial in the sum of the number of actions of the players and

\operatorname{log} ( 1 / \epsilon )

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

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

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

\displaystyle \left\{ν \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 ν} \mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i} , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] > 0\\ \forall \mu \in \Delta \left(A_{1} \times \dots \times A_{n}\right)\right\} .

Furthermore, for any $$ν$$ , 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 $ν_{t}$ of the set. Then, it will find a violated constraint using the distribution $\mu_{t} \coloneqq \mu ( ν_{t} )$ in the proof of Theorem S1.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. In the process, it takes $O (\operatorname{log} (1 / \epsilon ))$ iterations for the search space to shrink to size $\epsilon$ . By the last iteration $$T$$ , the algorithm will have produced several violated constraints, each of which is associated with a mediator strategy $\mu_{t}$ . The set

\displaystyle \left\{ν \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 ν} \mathbb{E}_{a \sim \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 ν} \mathbb{E}_{a \sim \mu_{T}} \left[u_{i} \left(a_{i} , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right] > 0\right\} .

The constraints of the set are all linear in $$ν$$ , 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$ such that

\displaystyle \sum_{t = 1}^{T} \alpha_{t} \mathbb{E}_{a \sim \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{\mu} \coloneqq \sum_{t = 1}^{T} \alpha_{t} \mu_{t}$ , we can then write

\displaystyle \mathbb{E}_{a \sim \hat{\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{\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 \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.

S1.2.2 Applications beyond normal-form games

The above argument mostly uses ideas from convex optimization. In particular, it generalizes verbatim to any convex game, that is, any setting with the following properties:

Player $$i$$ ‘s strategy set is a convex set of some dimension $d_{i}$ . For normal-form games, a strategy is an element of $\Delta ( A_{i} )$ , that is, a distribution over the player’s strategies. We assume we have oracle access to the set, which runs in time polynomial in $d_{i}$ .
The utility function $u_{i} ( x_{1} , \dots , 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} ( x_{1} , \dots , x_{n} )$ can be evaluated efficiently, let’s say in time $$R$$ .

The Ellipsoid-Against-Hope algorithm can then be applied and runs in time polynomial in $\sum_{i}^{n} d_{i}$ , $$R$$ , and $\operatorname{log} ( 1 / \epsilon )$ . Examples of games that satisfy the above properties include polymatrix games, congestion games, and sequential imperfect-information (extensive-form) games. We will see some of these games later in this course.

S1.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. `http://www.jstor.org/stable/3689835`

S1.A Appendix: Proof of Theorem S1.1

The key here is to pick $\mu$ in a way that depends on $$ν$$ . In particular, we will pick $\mu$ to be the product distribution that outputs

\displaystyle \left(a_{1} , \dots , a_{n}\right) \mathord{\text{ with probability proportional to }} ν_{1 , a_{1}} ⋅ \dots ⋅ ν_{n , a_{n}} .

With this choice and some simple manipulations,

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

\displaystyle = \sum_{i} \sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'} \mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i}' , a_{- i}\right) - u_{i} \left(a_{i} , a_{- i}\right)\right]

\displaystyle = \sum_{i} \sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'} \left(\mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i}' , a_{- i}\right)\right] - \mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i} , a_{- i}\right)\right]\right)

\displaystyle = \sum_{i} \left(\sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'} \mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i}' , a_{- i}\right)\right] - \sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'} \mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i} , a_{- i}\right)\right]\right)

\displaystyle = \sum_{i} \left( \underbrace{\sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'} \mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i}' , a_{- i}\right)\right]}_{\left(♠\right)} - \underbrace{\left(\sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'}\right) \mathbb{E}_{a \sim \mu} \left[u_{i} \left(a_{i} , a_{- i}\right)\right]}_{\left(♣\right)} \right) .

We now expand $$(♠)$$ , using the symbol $ν_{- i , a_{- i}}$ to mean the product of $ν_{1 , a_{1}}$ , $\dots$ , $ν_{i - 1 , a_{i - 1}}$ , $ν_{i + 1 , a_{i + 1}}$ , $\dots$ , $ν_{n , a_{n}}$ . Using the construction of $$m u$$ as a product distribution, we can write

\displaystyle \left(♠\right)

\displaystyle = \sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'} \sum_{a_{i} \in A_{i}} \sum_{a_{- i} \in A_{- i}} ν_{i , a_{i}} ν_{- i , a_{- i}} u_{i} \left(a_{i} , a_{- i}\right)

\displaystyle = \sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'} \left(\left(\sum_{a_{- i} \in A_{- i}} ν_{- i , a_{- i}} u_{i} \left(a_{i} , a_{- i}\right)\right) \left(\sum_{a_{i} \in A_{i}} ν_{i , a_{i}}\right)\right)

\displaystyle = \left(\sum_{a_{i}' \in A_{i}} ν_{i , a_{i}'} \sum_{a_{- i} \in A_{- i}} ν_{- i , a_{- i}} u_{i} \left(a_{i} , a_{- i}\right)\right) \left(\sum_{a_{i} \in A_{i}} ν_{i , a_{i}}\right)

\displaystyle = \left(\sum_{a_{i}' \in A_{i}} \sum_{a_{- i} \in A_{- i}} ν_{i , a_{i}'} ν_{- i , a_{- i}} u_{i} \left(a_{i} , a_{- i}\right)\right) \left(\sum_{a_{i} \in A_{i}} ν_{i , a_{i}}\right) = \left(♣\right) .

Hence,

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

completing the proof.