Lecture 3

Properties and relaxations of the Nash equilibrium

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.

L3.1 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.

L3.1.1 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.

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.

Computation As we will see shortly, Theorem L3.2 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,

The key insight is that this problem can be rewritten as

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.

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.

• The proof of von Neumann’s minimax theorem essentially hides an optimization duality argument. Indeed, we have the following:

  \(\operatorname*{max}_{x \in \Delta ( A_{1} )} \operatorname*{min}_{y \in \Delta ( A_{2} )} x^{\top} U_{1} y\)		\(\operatorname*{min}_{y \in \Delta ( A_{2} )} \operatorname*{max}_{x \in \Delta ( A_{1} )} x^{\top} U_{1} y\)
  \(↕\)		\(↕\)
  \[\displaystyle \begin{cases}\operatorname*{max} v \\ v \le x^{\top} U_{1} a_{2} \quad \forall a_{2} \\ 1^{\top} x = 1 \\ x \ge 0 .\end{cases}\]	\(\mathop{⟷}\limits_{\mathord{\operatorname{duality}}}^{\mathord{\text{ linear programming }}}\)	\[\displaystyle \begin{cases}\operatorname*{min} w \\ w \ge a_{1}^{\top} U_{1} y \quad \forall a_{1} \\ 1^{\top} y = 1 \\ y \ge 0 .\end{cases}\]

• The connection between linear programming and two-player zero-sum games is bidirectional: as it turns out, solving linear programming and finding a Nash equilibrium in a two-player zero-sum game are computationally equivalent. This means that 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 [BR23[BR23] Brooks, B., & Reny, P. J. (2023). A canonical game—75 years in the making—showing the equivalence of matrix games and linear programming. Econ. Theory Bull., 11(2), 171–180. link; Von23[Von23] Stengel, B. von. (2023). Zero-Sum Games and Linear Programming Duality. Math. Oper. Res.; Adl13[Adl13] Adler, I. (2013). The equivalence of linear programs and zero-sum games. International Journal of Game Theory, 42, 165–177.].

• 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!

  « 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 Dantzig [Dan82[Dan82] Dantzig, G. B. (1982). Reminiscences about the origins of linear programming. Oper. Res. Lett., 1(2), 43–48. link])

• 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.

Topological properties It is important to realize that what Theorem L3.2 is saying is that in two-player zero-sum games, each player can plan their own strategy independently. 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, any product of maxmin strategies is an equilibrium. We have just arrived at the following corollary.

Since Cartesian products of nonempty, convex, and compact sets are themselves nonempty, convex, and compact, Corollary L3.3 immediately implies the following as well.

It is worth remarking again that what does the heavy lifting here is really Theorem L3.2 the rest follows as a direct corollary.

L3.1.2 Nash equilibrium in two-player general-sum games

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

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.

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

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:

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\)-approximate Nash equilibria is due to Lipton, Markakis and Mehta [LMM03[LMM03] Lipton, R. J., Markakis, E., & Mehta, A. (2003). Playing large games using simple strategies. Proceedings of the 4th ACM Conference on Electronic Commerce, 36–41. link], and is based on the observation that every game admits an \(\epsilon\)-approximate Nash equilibrium where the strategy of Player 1 is supported on at most \(w \coloneqq O (\frac{\operatorname{log} | A_{2} |}{\epsilon^{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^{\operatorname{log} s / \epsilon^{2}})\), where \(s\) is the size of input) for computing an \(\epsilon\)-approximate Nash equilibrium.

L3.1.3 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.

Analytic properties As a start, rational numbers might not be enough anymore to store the probabilities of each player’s actions at equilibrium.

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 represent the output equilibrium needs attention. In general, we cannot hope for an exact value. However, even asking for a 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 [PNS08[PNS08] Porter, R., Nudelman, E., & Shoham, Y. (2008). Simple search methods for finding a Nash equilibrium. Games Econom. Behav., 63(2), 642–662. link]) still apply.

L3.2 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 correlated equilibria [Aum74[Aum74] Aumann, R. J. (1974). Subjectivity and correlation in randomized strategies. J. Math. Econom., 1(1), 67–96. link] and coarse correlated equilibria [MV78[MV78] Moulin, H., & Vial, J. P. (1978). Strategically zero-sum games: the class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory, 7, 201–221.], 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.¹1A 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 [BS19[BS19] Brown, N., & Sandholm, T. (2019). Superhuman AI for multiplayer poker. Science, 365(6456), 885–890. DOI].

L3.2.1 Coarse correlated equilibrium

Remember that in a Nash equilibrium we are seeking a strategy profile \((x_{1} , \dots , x_{n}) \in \Delta (A_{1}) \times \dots \times \Delta (A_{n})\) such that no player can unilaterally deviate to improve their payoff, that is,

Here, \(u_{i}\) was defined as the expected payoff when all the players randomize independently.

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

Properties and computation We can turn Definition L3.9 into an optimization problem. The variables are the entries of the probability distribution \(\mu\). This is a \((A_{1} \times \dots \times A_{n})\)-dimensional nonnegative vector whose entries must satisfy the linear equality constraint

Furthermore, expanding the expectation in inequality 1 defines a set of linear constraints

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 (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 \times | A_{n} |\).

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.

L3.2.2 Correlated equilibrium

The concept of correlated equilibrium is an intermediate relaxation between Nash equilibrium and coarse correlated equilibrium.

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 \(ϕ\) in those games might be too large to control.

L3.2.3 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 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 before the recommendation is made. In a correlated equilibrium, the players commit to the recommended action after the recommendation is made.

L3.3 Bibliography for this lecture