// Port of Lectures/content/correlated.tex; Fall 2025 source.
#import "../meta/gabri_notes_bk.typ": *
#show: gabri_notes.with(lec_num: 3, date: [Tue, Sep 22, 2026], title: [Properties and relaxations of the Nash equilibrium], instructor: [Prof. Gabriele Farina])

In this lecture, we will continue analyzing the properties of Nash equilibria in normal-form games. We will then introduce the concept of correlated equilibrium, a relaxation of Nash equilibrium with desirable properties.

= Further properties of the Nash equilibrium

We ended Lecture 1 with the definition of a Nash equilibrium. Recall that a strategy profile is a Nash equilibrium if no player can unilaterally deviate from their strategy to improve their payoff. We also discussed the existence of Nash equilibria in finite games, which is guaranteed by the Brouwer fixed-point theorem.

== Nash equilibrium in two-player zero-sum games

As mentioned in the previous lecture, in two-player zero-sum games the Nash equilibria are exactly those strategy profiles for which both players are playing a maxmin strategy. We formalize this in the next theorem.  First, though, we introduce some notation which will make our life easier when dealing with two-player games.

#definition[Matrices $U_1$ and $U_2$ for two-player games][
Consider a generic two-player zero-sum game, as shown next. As usual, we denote the sets of actions for player by $A_1$ and $A_2$.

#align(center)[

    #image("../figures/L04/game_table.svg")
  ]

  Let $x in Delta (A_1)$ denote a strategy of Player 1, and $y in Delta (A_2)$ a strategy of Player 2. We can express the expected utilities for the players according to the bilinear expressions

$ u_1 (x \, y) = x^top U_1 y \, #h(2em) #h(2em) u_2 (x \, y) = x^top U_2 y \, $

  where

$ U_1 colon.eq mat(delim: "(", a_11, a_12, dots.h.c, a_(1 m); a_21, a_22, dots.h.c, a_(2 m); dots.v, dots.v, dots.down, dots.v; a_(n 1), a_(n 2), dots.h.c, a_(n m)) \, quad U_2 colon.eq mat(delim: "(", b_11, b_12, dots.h.c, b_(1 m); b_21, b_22, dots.h.c, b_(2 m); dots.v, dots.v, dots.down, dots.v; b_(n 1), b_(n 2), dots.h.c, b_(n m)) . $
]

From now on, we will assume that a two-player game has been defined, and we will use the notation with $U_1$ and $U_2$ defined above to refer to the utility matrices of the players.

#theorem[
Consider a two-player zero-sum game, that is, one for which $U_2 = - U_1$. Then, a strategy profile $(x^(*) \, y^(*)) in Delta (A_1) times Delta (A_2)$ is a Nash equilibrium if and only if it is a maxmin strategy, #emph[i.e.], if and only if

$ x^(*) in "arg max"_(x in Delta (A_1)) min_(y in Delta (A_2)) x^top U_1 y \, #h(2em) upright("and") #h(2em) y^(*) in "arg max"_(y in Delta (A_2)) min_(x in Delta (A_1)) x^top U_2 y . $
]#label("thm:nash is mm")

#proof[
We prove the result assuming we trust von Neumann's minimax theorem, which states that

$ max_(x in Delta (A_1)) min_(y in Delta (A_2)) x^top U_1 y = min_(y in Delta (A_2)) max_(x in Delta (A_1)) x^top U_1 y . $

  $(arrow.r.double.long)$~~Suppose that $(x^(*) \, y^(*))$ is a Nash equilibrium. Then, by the definition of Nash equilibrium and using the fact that $U_2 = - U_1$, we have that

$ (x^(*))^top U_1 y^(*) = max_(x in Delta (A_1)) x^top U_1 y^(*) \, #h(2em) upright("and") #h(2em) (x^(*))^top U_1 y^(*) = min_(y in Delta (A_2)) (x^(*))^top U_1 y . $

  Hence, we can write the chain of equalities and inequalities

$ min_(y in Delta (A_2)) max_(x in Delta (A_1)) x^top U_1 y lt.eq max_(x in Delta (A_1)) x^top U_1 y^(*) = min_(y in Delta (A_2)) (x^(*))^top U_1 y lt.eq max_(x in Delta (A_1)) min_(y in Delta (A_2)) x^top U_1 y . $

  By the minimax theorem, all inequalities must be equalities; hence, $(x^(*) \, y^(*))$ satisfies

$ min_(y in Delta (A_2)) max_(x in Delta (A_1)) x^top U_1 y & = max_(x in Delta (A_1)) x^top U_1 y^(*) &  & quad arrow.l.r.double quad y^(*) in "arg min"_(y in Delta (A_2)) max_(x in Delta (A_1)) x^top U_1 y\
max_(x in Delta (A_1)) min_(y in Delta (A_2)) x^top U_1 y & = min_(y in Delta (A_2)) (x^(*))^top U_1 y &  & quad arrow.l.r.double quad x^(*) in "arg max"_(x in Delta (A_1)) min_(y in Delta (A_2)) x^top U_1 y . $

  $(arrow.l.double.long)$~~Conversely, suppose that $x^(*)$ and $y^(*)$ are maxmin strategies. Let $v^(*)$ be the common value of both sides of the minimax theorem, that is,

$ v^(*) colon.eq max_(x in Delta (A_1)) min_(y in Delta (A_2)) x^top U_1 y = min_(y in Delta (A_2)) max_(x in Delta (A_1)) x^top U_1 y . $

  We now show that $(x^(*) \, y^(*))$ is a Nash equilibrium. By definition, this means we need to show that

$ (x^(*))^top U_1 y^(*) = max_(x in Delta (A_1)) x^top U_1 y^(*) & #h(2em) upright("and") #h(2em) (x^(*))^top U_1 y^(*) = min_(y in Delta (A_2)) (x^(*))^top U_1 y . $

  Using the hypothesis,

$ x^(*) & in "arg max"_(x in Delta (A_1)) min_(y in Delta (A_2)) x^top U_1 y \, quad &  & arrow.r.double.long quad v^(*) = min_(y in Delta (A_2)) (x^(*))^top U_1 y \,\
y^(*) & in "arg min"_(y in Delta (A_2)) max_(x in Delta (A_1)) x^top U_1 y \, quad &  & arrow.r.double.long quad v^(*) = max_(x in Delta (A_1)) x^top U_1 y^(*) . $

  These equalities imply that $v^(*) lt.eq (x^(*))^top U_1 y^(*)$ and $v^(*) gt.eq (x^(*))^top U_1 y^(*)$, and thus $v^(*) = (x^(*))^top U_1 y^(*)$. This shows that the players are best responding to the strategy of the opponent, completing the proof that $(x^(*) \, y^(*))$ is a Nash equilibrium.
]

#strong[Computation]  As we will see shortly, #ref(label("thm:nash is mm")) gives us nontrivial information about the structure of Nash equilibria in two-player zero-sum games. But it also gives us a computational tool. Indeed, the theorem above tells us that finding a Nash equilibrium in a two-player zero-sum game can be expressed as an optimization problem. Let's show that this optimization problem is a linear program. Without loss of generality, let's focus on Player 1's optimization problem, that is,

$ x^(*) in "arg max"_(x in Delta (A_1)) min_(y in Delta (A_2)) x^top U_1 y . $

The key insight is that this problem can be rewritten as

$ cases(max_v v, upright("s.t.") v lt.eq x^top U_1 a_2 quad forall a_2 in A_2, upright("") 1^top x = 1, x gt.eq 0 .) $

which is a linear program with a linear number of constraints in the number of actions of Player 2. We can use any linear programming solver to find such a solution. We will see more scalable methods to compute maxmin strategies from repeat play starting next week.

#strong[Connection with linear programming]  It is worth pausing for a moment to appreciate some historical context. We started the proof by assuming von Neumann's minimax theorem, which we justified as a consequence of linear programming duality. However, historically, von Neumann did not have the luxury of linear programming to prove his theorem.

#list(
[
The proof of von Neumann's minimax theorem essentially hides an optimization duality argument. Indeed, we have the following:

#align(center)[
          
#table(stroke: none, columns: 3, align: center+horizon, inset: .7em,
[$max_(x in Delta \( A_1 \)) min_(y in Delta \( A_2 \)) x^top U_1 y$],
[],
[$min_(y in Delta \( A_2 \)) max_(x in Delta \( A_1 \)) x^top U_1 y$],
[$arrow.t.b$],
[],
[$arrow.t.b$],
[$ cases(max v, v lt.eq x^top U_1 a_2 quad forall a_2, 1^top x = 1, x gt.eq 0 .) $],
[$limits(arrow.l.r.long)^(upright("  linear programming  "))_(upright("duality"))$],
[$ cases(min w, w gt.eq a_1^top U_1 y quad forall a_1, 1^top y = 1, y gt.eq 0 .) $]
)

        ]
],
[
The connection between linear programming and two-player zero-sum games is bidirectional: as it turns out, #emph[solving linear programming] and #emph[finding a Nash equilibrium in a two-player zero-sum game] are #emph[computationally equivalent]. This means that #emph[any] linear programming problem (with arbitrary constraints, variables, etc.) can be efficiently converted into a two-player zero-sum game. This is less obvious than it may seem. For one, the strategy sets in games are probability simplexes, while linear programs might have arbitrary linear equality and inequality constraints. Furthermore, linear programs might be unbounded or unfeasible; yet, a Nash equilibrium of a game always exists. It would have been perfectly reasonably to believe that linear programming was a significantly more general tool than equilibrium solvers for two-player zero-sum games, and we know today that that belief would have been wrong. For more on this, see #citep(label("Brooks2023Oct"), label("vonStengel2023Jul"), label("adler2013equivalence")).
],
[
All of this seems simple with the luxury of hindsight. But the two fields were not as closely connected as we might think. We know this from a transcript of the first encounter between Dantzig, one of the fathers of linear programming, and von Neumann, one of the fathers of game theory. And, perhaps in what is a plot twist, it was von Neumann to teach Dantzig about duality!

#quote(block: true)[
          « On October 3, 1947, I visited him (von Neumann) for the first time at the Institute for Advanced Study at Princeton. I remember trying to describe to von Neumann, as I would to an ordinary mortal, the Air Force problem. I began with the formulation of the linear programming model in terms of activities and items, etc. Von Neumann did something which I believe was uncharacteristic of him. “Get to the point,” he said impatiently. Having at times a somewhat low kindlingpoint, I said to myself “O.K., if he wants a quicky, then that's what he will get.” In under one minute I slapped the geometric and algebraic version of the problem on the blackboard. Von Neumann stood up and said “Oh that!” Then for the next hour and a half, he proceeded to give me a lecture on the mathematical theory of linear programs. At one point seeing me sitting there with my eyes popping and my mouth open (after I had searched the literature and found nothing), von Neumann said: “I don't want you to think I am pulling all this out of my sleeve at the spur of the moment like a magician. I have just recently completed a book with Oskar Morgenstern on the theory of games. What I am doing is conjecturing that the two problems are equivalent. The theory that I am outlining for your problem is an analogue to the one we have developed for games.” Thus I learned about Farkas' Lemma, and about duality for the first time.»

            (from #citet(label("Dantzig1982Apr")))
        ]
],
[
In light of the above you might be wondering how easy it would be to prove the minimax theorem without relying on linear programming duality. As we will show, the mere existence of learning dynamics in games is enough. We will also see a different proof next time.
]
)

#strong[Topological properties]  It is important to realize that what #ref(label("thm:nash is mm")) is saying is that in two-player zero-sum games, each player can plan their own strategy #emph[independently]. #emph[Any] combination of maxmin strategies for the players forms an equilibrium. This is in contrast with the general case: there, in order to specify a Nash equilibrium we need to provide a tuple of strategies for all players. In two-player zero-sum games, instead, #emph[any product of maxmin strategies is an equilibrium]. We have just arrived at the following corollary.

#corollary[
In a two-player zero-sum game, the set of Nash equilibria is a Cartesian product of nonempty, convex, compact sets.
]#label("cor:nash product")

Since Cartesian products of nonempty, convex, and compact sets are themselves nonempty, convex, and compact, #ref(label("cor:nash product")) immediately implies the following as well.

#corollary[
The set of Nash equilibria in a two-player zero-sum game is nonempty, convex, and compact.
]

It is worth remarking again that what does the heavy lifting here is really #ref(label("thm:nash is mm")); the rest follows as a direct corollary.

== Nash equilibrium in two-player general-sum games

In the general two-player case, often referred to as #emph[two-player general-sum games], many of the nice properties of the zero-sum case are lost.

#strong[Topological properties]  Perhaps the most striking is that not only the set of Nash equilibria is no longer guaranteed to be convex, but it is not even guaranteed to be contractible. We show this phenomenon with the next example.

#remark[Complex topology of Nash equilibria; Kohlberg-Mertens game #citep(label("kohlberg1986strategic"))][
Beyond two-player zero-sum games, the set of Nash equilibria in a game can be quite complex.

#wrapped-figure(side: right, text-width: 55%)[
For one, #emph[it is not at all guaranteed that the set is convex]. Even more, the set might be #emph[topologically complex], #emph[e.g.], exhibiting holes.  This phenomenon was already observed by #citet(label("kohlberg1986strategic")), who considered the two-player three-action game

#align(center)[
      #image("../figures/L03/km_game.svg", width: 118.75pt)
    ]

The figure on the right, similar to the one in #citep(label("Milionis2023Oct")), shows the projection of the set of all $0.27$-approximate Nash equilibria of this game, #emph[i.e.], all strategy profiles such that no player has a unilateral deviation that increases their utility by more than $0.27$.
][
#image("../figures/L03/kohlberg_mertens.svg", width: 175.392pt)
]
]

#strong[Computation]  In two-player general-sum games, computation of Nash equilibria is not a linear program. However, it is a #emph[linear complementarity problem] (LCP), a more general class of problems than linear feasibility programs, and which are written in the form

$ upright(f i n d) quad x \, w in bb(R)^d #h(2em) upright("s.t.") #h(2em) w = M x + q \, #h(2em) x \, w gt.eq 0 \, #h(2em) x^top w = 0 . $

The Lemke-Howson algorithm is a well-known algorithm to solve LCPs, and it can be used to find Nash equilibria in two-player general-sum games. However, the algorithm is not polynomial-time in the worst case, and it can be hard to find Nash equilibria in practice. An important corollary of the connection between two-player general-sum games and LCPs is the following:

#corollary[
Any two-player general-sum games with rational payoffs admits a Nash equilibrium with rational coordinates.
]

This follows directly from the way Lemke-Howson works, which is similar to the simplex algorithm. The algorithm moves along edges of a rational polytope until it finds a Nash equilibrium. Since the algorithm only moves along the edges of the polytope, it will only generate rational solutions.

An interesting result about the computation of $epsilon.alt$-approximate Nash equilibria is due to #citet(label("LMM03")), and is based on the observation that every game admits an $epsilon.alt$-approximate Nash equilibrium where the strategy of Player 1 is supported on at most $w colon.eq O (frac(log \| A_2 \|, epsilon.alt^2))$ strategies. This follows from using a Hoeffding bound on samples from the distribution of Player 1's strategy. One can then check any support for Player 1's strategy of size up to $w$, and for each such support, solve a linear program to verify if a Nash equilibrium with that support exists. This gives a subexponential-time algorithm (of order $O (s^(log s \/ epsilon.alt^2))$, where $s$ is the size of input) for computing an $epsilon.alt$-approximate Nash equilibrium.

== Nash equilibrium in games with more than two players

In games with more than two players, the behavior of Nash equilibria can be even more problematic.

#strong[Analytic properties]  As a start, #emph[rational numbers might not be enough anymore] to store the probabilities of each player's actions at equilibrium.

#example[
In his original paper, Nash showed a three-player game with rational payoffs and with the property that #emph[all] Nash equilibria prescribe probabilities that are irrational numbers #citep(label("Nash51:NonCooperative")). Another simple example is also reported by #citet(label("nau2004geometry")), as follows: 

#align(center)[
    #image("../figures/L03/nash_irrational.svg")
  ]

  A simple calculation shows that the only Nash equilibrium $(x^(*) \, y^(*) \, z^(*))$ of this game satisfies

$ (x_1^(*) \, y_1^(*) \, z_1^(*)) = (53 / 46 - sqrt(601) / 46 \, - 13 / 24 + sqrt(601) / 24 \, - 23 / 4 + sqrt(601) / 4) approx (0.619 \, 0.480 \, 0.379) . $

  From a computational point of view, this property raises the question of how a Nash equilibrium solver could even #emph[represent] such an output.
]

#proof[
Homework.
]

#remark[
The issues with irrational numbers do not stop at square roots. In fact, #emph[any polynomial root] might be required to represent a Nash equilibrium. This was shown by #citet(label("bubelis1979equilibria")), who showed how to construct games with arbitrary polynomial roots.

  Beyond the representation, the topology of Nash equilibria is also in general arbitrarily complex in three-player games. In particular, #citet(label("datta2003universality")) showed that for any real algebraic variety, one can come up with some three-player game whose set of Nash equilibria is isomorphic to that variety.
]

#strong[Computation]  On the computational side, the situation is even more dire. As a first consideration, because Nash equilibria might require irrational numbers, even the question of how to #emph[represent] the output equilibrium needs attention. In general, we cannot hope for an #emph[exact] value. However, even asking for a #emph[constant] approximation turns out to be hard. We will talk about this in more detail at the end of the course, where we relate the computation of (approximate) Nash equilibria to a complexity class called PPAD.

If one is willing to stomach a worst-case superpolynomial runtime, some methods exist. While the Lemke-Howson algorithm cannot be used beyond two-player games, other methods (such as #citep(label("Porter2008Jul"))) still apply.

= Correlated and coarse correlated equilibrium

The discussion above shows that Nash equilibria can be hard to compute and might not form a convex (or even contractible) set. This motivates the study of #emph[correlated equilibria] #citep(label("Aumann1974Mar")) and #emph[coarse correlated equilibria] #citep(label("moulin1978strategically")), which are a relaxation of Nash equilibria that are easier to compute, always form a convex set, and for which rational solutions always exist. As we will show starting in a few lectures, another major advantage of correlated equilibria is that they can be learned from repeated play, in a way that is fundamentally incompatible with Nash equilibria.#footnote[A paradigm that has been successful in applications is to learn a correlated equilibrium from repeated play, and then marginalize it into a profile that is hoped to be close to a Nash equilibrium. This was used for example to reach superhuman performance in multiplayer poker #citep(label("Brown2019Aug")).]

== Coarse correlated equilibrium

Remember that in a Nash equilibrium we are seeking a strategy profile $(x_1 \, dots.h \, x_n) in Delta (A_1) times dots.h.c times Delta (A_n)$ such that no player can unilaterally deviate to improve their payoff, that is,

$ u_i (a'_i \, x_(- i)) gt.eq u_i (x_i \, x_(- i)) #h(2em) forall i in \[ n \] \, a'_i in A_i . $

Here, $u_i$ was defined as the expected payoff when all the players randomize #emph[independently].

The concept of #emph[coarse correlated equilibrium] is a relaxation of this definition. In a coarse correlated equilibrium, instead of asking for the players to pick #emph[independent] strategies, we allow coordination. In particular, we define the following.

#definition[Coarse correlated equilibrium #citep(label("moulin1978strategically"))][
A #emph[coarse correlated equilibrium (CCE)] is a correlated strategy $mu in Delta (A_1 times dots.h times A_n)$ such that

#math.equation(block: true, numbering: "(1)", $bb(E)_((a_1 \, dots.h \, a_n) tilde.op mu) [u_i (a'_1 \, dots.h \, a_n)] lt.eq bb(E)_((a_1 \, dots.h \, a_n) tilde.op mu) [u_i (a_1 \, dots.h \, a_n)] #h(2em) forall i in \[ n \] \, a'_i in A_i .$.body)#label("eq:cce")
]#label("def:cce")

#remark[
The definition of a CCE is a relaxation of the definition of a Nash equilibrium. In a Nash equilibrium, the players randomize independently; in a CCE, they can randomize in a correlated way. #emph[A Nash equilibrium is a CCE $mu$ that happens to be a product distribution], that is, $mu = x_1 ⊗ dots.h.c ⊗ x_n .$

  This shows that the set of CCEs is a superset of the set of Nash equilibria. Thus, a coarse correlated equilibria always exists in every game.
]

#strong[Properties and computation]  We can turn #ref(label("def:cce")) into an optimization problem. The variables are the entries of the probability distribution $mu$. This is a $(A_1 times dots.h.c times A_n)$-dimensional nonnegative vector whose entries must satisfy the linear equality constraint

$ sum_(a_1 in A_1) dots.h.c sum_(a_n in A_n) mu_(a_1 \, dots.h \, a_n) = 1 . $

Furthermore, expanding the expectation in inequality #ref(label("eq:cce"), supplement: none) defines a set of linear constraints

$ sum_(a_1 in A_1) dots.h.c sum_(a_n in A_n) mu_(a_1 \, dots.h \, a_n) u_i (a'_i \, a_(- i)) lt.eq sum_(a_1 in A_1) dots.h.c sum_(a_n in A_n) mu_(a_1 \, dots.h \, a_n) u_i (a_i \, a_(- i)) $

for all $i in \[ n \]$ and $a'_i in A_i$.
Hence, the set of CCEs is the intersection of a finite set of linear constraints, and so it is a convex polytope. Note that the number of constraints is polynomial in the game (#emph[i.e.], in the size of the payoff table), and so we can use linear programming to compute and even optimize over the set of CCEs in time polynomial in $\| A_1 \| times dots.h times \| A_n \|$.

#corollary[
Since the coefficients of the linear constraints are the payoffs of the game, the set of CCEs is always a rational polytope.
]

It is worth knowing that a CCE can also be computed in polynomial time in imperfect-information sequential games, despite the number of "actions" there, which is the number of strategies in the tree, is exponential in the input. Unfortunately, we lose the ability to optimize over the set.

== Correlated equilibrium

The concept of #emph[correlated equilibrium] is an intermediate relaxation between Nash equilibrium and coarse correlated equilibrium.

#definition[Correlated equilibrium #citep(label("Aumann1974Mar"))][
A #emph[correlated equilibrium (CE)] is a correlated strategy $mu in Delta (A_1 times dots.h times A_n)$ such that

$ bb(E)_((a_1 \, dots.h \, a_n) tilde.op mu) [u_i (phi.alt_i (a_i) \, a_(- i))] lt.eq bb(E)_((a_1 \, dots.h \, a_n) tilde.op mu) [u_i (a_i \, a_(- i))] #h(2em) forall i in \[ n \] \, phi.alt_i : A_i arrow.r A_i \, $

  where the function $phi.alt_i : A_i arrow.r A_i$ is arbitrary.
]

#remark[
A CCE is a special case of a CE, where the functions $phi.alt_i$ considered are only #emph[constant] functions. Furthermore, it is not hard to show from expanding the definition that any Nash equilibrium is a CE. Thus, the set of CEs is a superset of the set of Nash equilibria and a subset of the set of CCEs.
]

All remarks made about the computation of CCEs in normal-form games apply to CEs as well. In particular, the set of CEs is a convex polytope, and a CE can be computed in polynomial time using linear programming.

However, the remark about computation in imperfect-information sequential games does not apply to CEs. Whether a CE can be computed efficiently in such games is an open question in the field. Some mild evidence suggests that the problem might be hard. Intuitively, the issue is that the number of functions $phi.alt$ in those games might be too large to control.

== How to think about correlated play in games

We can think of the correlation between the strategies of the players in a correlated or coarse correlated equilibrium as arising from some #emph[correlation device] in the game. This is a trusted mediator that can recommend but not enforce behavior. The distribution $mu$ from which the correlation device samples recommendations is public knowledge, but the players only get to observe the recommended action that was sampled for them. A correlated / coarse correlated equilibrium is then a distribution $mu$ such that no player can unilaterally deviate from the recommended action to improve their payoff.

The distinction between correlated and coarse correlated equilibrium is in when the players decide when to commit to the recommended action. In a coarse correlated equilibrium, the players commit to the recommended action #emph[before] the recommendation is made. In a correlated equilibrium, the players commit to the recommended action #emph[after] the recommendation is made.

= Bibliography for this lecture

#lec_bibliography("../meta/refs.bib", title: none)

#changelog[
- 2025-10-05: Fixed typos (thanks Eric Yang Yu!).
]