MIT 6.S890 — Topics in Multiagent Learning Tue, Nov 12th 2024
Lecture 15
Computation of exact equilibria
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
Today we briefly discuss an aspect that we have not investigated directly. We have talked many times
about how learning enables us to compute equilibria in games. In particular, we have connected
coarse correlated equilibrium (CCE) approximation to the ratio between the regret of the learning
algorithm and time. In practice, this means that most learning procedures recover a CCE at a rate
of 𝑂(1/√𝑇 ) or, in the best case, 𝑂(1/𝑇 ) using optimistic dynamics (Lecture 5). So, while learning
methods are today the most scalable way of computing CCEs in large games, it is clear that they
are only suitable for low-precision computations, i.e., for relatively small values of 𝜖. This begs the
following question: are there algorithms that can compute high-precision CCEs, and other types of
equilibria, in games?
1 The main ideas
The answer to the above question is positive, and comes from a very neat construction by Papadim7
itriou, C. H., & Roughgarden, T. [PR08]. Long story short, for any sufficiently nice choice of convex
strategy set 𝒳𝑖 per player, we know how to construct an algorithm that computes an 𝜖7equilibrium
in a number of steps that scales with the logarithm of 1/𝜖.
1.1 Hart & Schmeidler’s proof of existence of (coarse) correlated equilibria
So far in the course, we have proven 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, S., & Schmeidler, D.
[HS89], which includes some ideas that will set the stage for the Ellipsoid7Against7Hope algorithm.
The proof is based on linear programming duality.
While the original proof of Hart, S., & Schmeidler, D. [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 𝜇 ∈ Δ(𝑆1 × ... × 𝑆𝑛)
such that
𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)] ≤ 𝔼𝑠∼𝜇[𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ∀𝑖 ∈ [𝑛], 𝑠′
𝑖 ∈ 𝑆𝑖.
Finding a CCE is then equivalent to finding a distribution 𝜇 such that
min
𝜇 max
𝑖∈[𝑛]
𝑠′
𝑖∈𝑆𝑖
𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ≤ 0.
How can we prove the existence of such a 𝜇 without resorting to the existence of Nash equilibria?
The rescue comes from the minimax theorem (which itself can be shown using linear programming
duality or, as we discussed in Lecture 4, using the existence of no7regret algorithms).
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
(𝑖, 𝑠𝑖), and we will rewrite the problem as
min
𝜇 max
𝜈 𝔼𝑠∼𝜇𝔼(𝑖,𝑠′
𝑖)∼𝜈 [𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ≤ 0.
By the minimax theorem and swapping the order of the expectations, the above min7max value is
equal to
max
𝜈 min
𝜇 𝔼(𝑖,𝑠′
𝑖)∼𝜈 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)].
Can we show that this value is ≤ 0? The answer is yes, and constructive.
Theorem 1.1. The following inequality holds:
max
𝜈 min
𝜇 𝔼(𝑖,𝑠′
𝑖)∼𝜈 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ≤ 0.
Proof . The key here is to pick 𝜇 in a way that depends on 𝜈. In particular, we will pick 𝜇 to be
the product distribution that outputs
(𝑠1, ..., 𝑠𝑛) with probability ∝ 𝜈1,𝑠1 ⋅ ... ⋅ 𝜈𝑛,𝑠𝑛 .
With this choice and some simple manipulations,
𝔼(𝑖,𝑠′
𝑖)∼𝜈 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)]
= ∑
𝑖
∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)]
= ∑
𝑖
∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 (𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)] − 𝔼𝑠∼𝜇[𝑢𝑖(𝑠𝑖, 𝑠−𝑖)])
= ∑
𝑖 (
(( ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)] − ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 𝔼𝑠∼𝜇[𝑢𝑖(𝑠𝑖, 𝑠−𝑖)]
)
))
= ∑
𝑖 (
(( ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)]
⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟
(♠)
−
(
(( ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖
)
))𝔼𝑠∼𝜇[𝑢𝑖(𝑠𝑖, 𝑠−𝑖)]
⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟
(♣)
)
))
We now expand (♠), using the symbol 𝜈−𝑖,𝑠−𝑖 to mean the product of
𝜈1,𝑠1 , ..., 𝜈𝑖−1,𝑠𝑖−1 , 𝜈𝑖+1,𝑠𝑖+1 , ..., 𝜈𝑛,𝑠𝑛 .
(♠) = ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 ∑
𝑠𝑖∈𝑆𝑖
∑
𝑠−𝑖∈𝑆−𝑖
𝜈𝑖,𝑠𝑖 𝜈−𝑖,𝑠−𝑖 𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)
= ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 (( ∑
𝑠−𝑖∈𝑆−𝑖
𝜈−𝑖,𝑠−𝑖 𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖))( ∑
𝑠𝑖∈𝑆𝑖
𝜈𝑖,𝑠𝑖 ))
=
(
(( ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 ∑
𝑠−𝑖∈𝑆−𝑖
𝜈−𝑖,𝑠−𝑖 𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)
)
))( ∑
𝑠𝑖∈𝑆𝑖
𝜈𝑖,𝑠𝑖 )
=
(
(( ∑
𝑠′
𝑖∈𝑆𝑖
∑
𝑠−𝑖∈𝑆−𝑖
𝜈𝑖,𝑠′
𝑖 𝜈−𝑖,𝑠−𝑖 𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)
)
))( ∑
𝑠𝑖∈𝑆𝑖
𝜈𝑖,𝑠𝑖 ) = (♣).
Hence,
max
𝜈 min
𝜇 𝔼(𝑖,𝑠′
𝑖)∼𝜈 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ≤ max
𝜈 0 = 0.
□
1.2 Turning the proof into an algorithm
We now sketch the idea behind the Ellipsoid7Against7Hope algorithm. The full details behind the
algorithm are a bit involved, and the machinery a bit technical. However, the important idea is that
one can think of the Ellipsoid7Against7Hope algorithm as a computational, constructive proof of the
minimax theorem. In particular:
• The proof of Hart and Schmeidler constructively gives a strong response of the mediator to
any deviation. In particular, given any 𝜈, there exists a 𝜇 that gives the mediator value ≤ 0.
• The ellipsoid method can then be used to find a 𝜇∗ such that for all 𝜈 the value of the mediator
value is ≤ 0.
In more detail, what Theorem 1.1 implies is that the following open polytope must be empty:
{𝜈 ∈ Δ{(𝑖, 𝑠′
𝑖) : 𝑖 ∈ [𝑛], 𝑠′
𝑖 ∈ 𝑆𝑖} : 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] > 0 ∀𝜇 ∈ Δ(𝑆1 × ... × 𝑆𝑛)}.
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
ellispoid 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 Ellipsoid7Against7Hope by Papadimitriou, C. H., & Roughgarden,
T. [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, the algorithm will compute the center point 𝜈 of the set. Then,
it will find a violated constraint using the mediator’s strategy in the proof of Theorem 1.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 𝑂(log(1/𝜖))
iterations for the search space to shrink to size 𝜖. Along the way, the algorithm will have produced
several violated constraints, each of which is associated with a mediator strategy 𝜇. It can be shown
using the Farkas lemma, that at least one convex combination of these 𝜇 is a CCE.
2 Bibliographic remarks
If you are curious to read more, the following papers contains extensions and refinements of the idea
of Ellipsoid7Against7Hope.
[PR08] C. H. Papadimitriou and T. Roughgarden, “Computing correlated equilibria in multi7player
games,” Journal of the ACM (JACM), vol. 55, no. 3, pp. 1–29, 2008.
[HS89] S. Hart and D. Schmeidler, “Existence of Correlated Equilibria,” Mathematics of Operations
Research, vol. 14, no. 1, pp. 18–25, 1989, Accessed: Nov. 07, 2024. [Online]. Available:
http://www.jstor.org/stable/3689835
[JL11] A. X. Jiang and K. Leyton7Brown, “Polynomial7time computation of exact correlated
equilibrium in compact games,” in Proceedings of the 12th ACM conference on Electronic
commerce, 2011, pp. 119–126.
[FP24] G. Farina and C. Pipis, “Polynomial7Time Computation of Exact Φ7Equilibria in Polyhedral
Games”, in Neural Information Processing Systems (NeurIPS), 2024.
[HS08] W. Huang and B. von Stengel, “Computing an extensive7form correlated equilibrium in
polynomial time,” in International Workshop on Internet and Network Economics, 2008,
pp. 506–513.
★These notes are class material that has not undergone formal peer review. The TA and I are grateful for any
reports of typos.
Lecture 15
Computation of exact equilibria
Instructor: Prof. Gabriele Farina ( gfarina@mit.edu)★
Today we briefly discuss an aspect that we have not investigated directly. We have talked many times
about how learning enables us to compute equilibria in games. In particular, we have connected
coarse correlated equilibrium (CCE) approximation to the ratio between the regret of the learning
algorithm and time. In practice, this means that most learning procedures recover a CCE at a rate
of 𝑂(1/√𝑇 ) or, in the best case, 𝑂(1/𝑇 ) using optimistic dynamics (Lecture 5). So, while learning
methods are today the most scalable way of computing CCEs in large games, it is clear that they
are only suitable for low-precision computations, i.e., for relatively small values of 𝜖. This begs the
following question: are there algorithms that can compute high-precision CCEs, and other types of
equilibria, in games?
1 The main ideas
The answer to the above question is positive, and comes from a very neat construction by Papadim7
itriou, C. H., & Roughgarden, T. [PR08]. Long story short, for any sufficiently nice choice of convex
strategy set 𝒳𝑖 per player, we know how to construct an algorithm that computes an 𝜖7equilibrium
in a number of steps that scales with the logarithm of 1/𝜖.
1.1 Hart & Schmeidler’s proof of existence of (coarse) correlated equilibria
So far in the course, we have proven 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, S., & Schmeidler, D.
[HS89], which includes some ideas that will set the stage for the Ellipsoid7Against7Hope algorithm.
The proof is based on linear programming duality.
While the original proof of Hart, S., & Schmeidler, D. [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 𝜇 ∈ Δ(𝑆1 × ... × 𝑆𝑛)
such that
𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)] ≤ 𝔼𝑠∼𝜇[𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ∀𝑖 ∈ [𝑛], 𝑠′
𝑖 ∈ 𝑆𝑖.
Finding a CCE is then equivalent to finding a distribution 𝜇 such that
min
𝜇 max
𝑖∈[𝑛]
𝑠′
𝑖∈𝑆𝑖
𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ≤ 0.
How can we prove the existence of such a 𝜇 without resorting to the existence of Nash equilibria?
The rescue comes from the minimax theorem (which itself can be shown using linear programming
duality or, as we discussed in Lecture 4, using the existence of no7regret algorithms).
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
(𝑖, 𝑠𝑖), and we will rewrite the problem as
min
𝜇 max
𝜈 𝔼𝑠∼𝜇𝔼(𝑖,𝑠′
𝑖)∼𝜈 [𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ≤ 0.
By the minimax theorem and swapping the order of the expectations, the above min7max value is
equal to
max
𝜈 min
𝜇 𝔼(𝑖,𝑠′
𝑖)∼𝜈 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)].
Can we show that this value is ≤ 0? The answer is yes, and constructive.
Theorem 1.1. The following inequality holds:
max
𝜈 min
𝜇 𝔼(𝑖,𝑠′
𝑖)∼𝜈 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ≤ 0.
Proof . The key here is to pick 𝜇 in a way that depends on 𝜈. In particular, we will pick 𝜇 to be
the product distribution that outputs
(𝑠1, ..., 𝑠𝑛) with probability ∝ 𝜈1,𝑠1 ⋅ ... ⋅ 𝜈𝑛,𝑠𝑛 .
With this choice and some simple manipulations,
𝔼(𝑖,𝑠′
𝑖)∼𝜈 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)]
= ∑
𝑖
∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)]
= ∑
𝑖
∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 (𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)] − 𝔼𝑠∼𝜇[𝑢𝑖(𝑠𝑖, 𝑠−𝑖)])
= ∑
𝑖 (
(( ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)] − ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 𝔼𝑠∼𝜇[𝑢𝑖(𝑠𝑖, 𝑠−𝑖)]
)
))
= ∑
𝑖 (
(( ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)]
⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟
(♠)
−
(
(( ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖
)
))𝔼𝑠∼𝜇[𝑢𝑖(𝑠𝑖, 𝑠−𝑖)]
⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟⏟
(♣)
)
))
We now expand (♠), using the symbol 𝜈−𝑖,𝑠−𝑖 to mean the product of
𝜈1,𝑠1 , ..., 𝜈𝑖−1,𝑠𝑖−1 , 𝜈𝑖+1,𝑠𝑖+1 , ..., 𝜈𝑛,𝑠𝑛 .
(♠) = ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 ∑
𝑠𝑖∈𝑆𝑖
∑
𝑠−𝑖∈𝑆−𝑖
𝜈𝑖,𝑠𝑖 𝜈−𝑖,𝑠−𝑖 𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)
= ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 (( ∑
𝑠−𝑖∈𝑆−𝑖
𝜈−𝑖,𝑠−𝑖 𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖))( ∑
𝑠𝑖∈𝑆𝑖
𝜈𝑖,𝑠𝑖 ))
=
(
(( ∑
𝑠′
𝑖∈𝑆𝑖
𝜈𝑖,𝑠′
𝑖 ∑
𝑠−𝑖∈𝑆−𝑖
𝜈−𝑖,𝑠−𝑖 𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)
)
))( ∑
𝑠𝑖∈𝑆𝑖
𝜈𝑖,𝑠𝑖 )
=
(
(( ∑
𝑠′
𝑖∈𝑆𝑖
∑
𝑠−𝑖∈𝑆−𝑖
𝜈𝑖,𝑠′
𝑖 𝜈−𝑖,𝑠−𝑖 𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖)
)
))( ∑
𝑠𝑖∈𝑆𝑖
𝜈𝑖,𝑠𝑖 ) = (♣).
Hence,
max
𝜈 min
𝜇 𝔼(𝑖,𝑠′
𝑖)∼𝜈 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] ≤ max
𝜈 0 = 0.
□
1.2 Turning the proof into an algorithm
We now sketch the idea behind the Ellipsoid7Against7Hope algorithm. The full details behind the
algorithm are a bit involved, and the machinery a bit technical. However, the important idea is that
one can think of the Ellipsoid7Against7Hope algorithm as a computational, constructive proof of the
minimax theorem. In particular:
• The proof of Hart and Schmeidler constructively gives a strong response of the mediator to
any deviation. In particular, given any 𝜈, there exists a 𝜇 that gives the mediator value ≤ 0.
• The ellipsoid method can then be used to find a 𝜇∗ such that for all 𝜈 the value of the mediator
value is ≤ 0.
In more detail, what Theorem 1.1 implies is that the following open polytope must be empty:
{𝜈 ∈ Δ{(𝑖, 𝑠′
𝑖) : 𝑖 ∈ [𝑛], 𝑠′
𝑖 ∈ 𝑆𝑖} : 𝔼𝑠∼𝜇[𝑢𝑖(𝑠′
𝑖, 𝑠−𝑖) − 𝑢𝑖(𝑠𝑖, 𝑠−𝑖)] > 0 ∀𝜇 ∈ Δ(𝑆1 × ... × 𝑆𝑛)}.
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
ellispoid 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 Ellipsoid7Against7Hope by Papadimitriou, C. H., & Roughgarden,
T. [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, the algorithm will compute the center point 𝜈 of the set. Then,
it will find a violated constraint using the mediator’s strategy in the proof of Theorem 1.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 𝑂(log(1/𝜖))
iterations for the search space to shrink to size 𝜖. Along the way, the algorithm will have produced
several violated constraints, each of which is associated with a mediator strategy 𝜇. It can be shown
using the Farkas lemma, that at least one convex combination of these 𝜇 is a CCE.
2 Bibliographic remarks
If you are curious to read more, the following papers contains extensions and refinements of the idea
of Ellipsoid7Against7Hope.
[PR08] C. H. Papadimitriou and T. Roughgarden, “Computing correlated equilibria in multi7player
games,” Journal of the ACM (JACM), vol. 55, no. 3, pp. 1–29, 2008.
[HS89] S. Hart and D. Schmeidler, “Existence of Correlated Equilibria,” Mathematics of Operations
Research, vol. 14, no. 1, pp. 18–25, 1989, Accessed: Nov. 07, 2024. [Online]. Available:
http://www.jstor.org/stable/3689835
[JL11] A. X. Jiang and K. Leyton7Brown, “Polynomial7time computation of exact correlated
equilibrium in compact games,” in Proceedings of the 12th ACM conference on Electronic
commerce, 2011, pp. 119–126.
[FP24] G. Farina and C. Pipis, “Polynomial7Time Computation of Exact Φ7Equilibria in Polyhedral
Games”, in Neural Information Processing Systems (NeurIPS), 2024.
[HS08] W. Huang and B. von Stengel, “Computing an extensive7form correlated equilibrium in
polynomial time,” in International Workshop on Internet and Network Economics, 2008,
pp. 506–513.
★These notes are class material that has not undergone formal peer review. The TA and I are grateful for any
reports of typos.