How to cite

@misc{mit-multiagent-learning-lecture-S2,
  author = {Daskalakis, Constantinos and Farina, Gabriele},
  title = {Supplementary reading S2: Centralized algorithms for Nash equilibrium computation},
  booktitle = {MIT Topics in Multiagent Learning Lecture Notes},
  note = {MIT 6.7980, Fall 2026},
  year = {2026},
  url = {https://www.mit.edu/~6.7980/nash_algorithms.html}
}

Supplementary reading S2

Centralized algorithms for Nash equilibrium computation

Instructor

Prof. Constantinos Daskalakis

Edition

Fall 2026

In previous lectures, we saw the basic game theory formalism, and some of the most fundamental equilibrium concepts, and their existence proofs. Nash’s proof that a Nash equilibrium in randomized strategies exists in every finite game makes use of Brouwer’s fixed point theorem, which does not immediately suggest an algorithm for computing Nash equilibria. On the other hand, we saw that the existence of Nash equilibrium in two-player zero-sum games can also be established using strong linear programming duality, which suggests a polynomial-time algorithm for computing Nash equilibria in these games.

Similarly, correlated and coarse correlated equilibria in general-sum games can also be computed in time polynomial in the game description using linear programming, as the equilibrium constraints can be written as a system of linear inequalities in the joint distribution over actions. Moreover, linear programming methods can be leveraged to obtain polynomial-time algorithms for certain families of what are called “succinct games,” wherein the payoffs are sparse or have other structure that makes an explicit representation of a joint distribution over actions super-polynomial in size compared to the game’s natural description. Still a correlated or coarse correlated equilibrium can be computed efficiently in many cases, using linear programming approaches such as Ellipsoid Against Hope [PR08[PR08] Papadimitriou, C. H., & Roughgarden, T. (2008). Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3), 1–29.].

In this lecture, we revisit Nash equilibrium computation in general games. We will discuss several algorithms for computing Nash equilibria. Roughly speaking those algorithms fall into two buckets. One bucket contains algorithms that directly target the equilibrium constraints, using linear programming, and more generally algorithms for solving systems of polynomial equations and inequalities. The other bucket contains algorithms that make tighter use of the fixed point nature of Nash equilibrium, and the directed parity argument underlying its existence proofs. In all cases, our algorithms will have super-polynomial complexity, unless the game has special structure. In future lectures, we will offer complexity theoretic justification is a deep reason why polynomial-time

S2.1 Support Enumeration Algorithms

To develop support enumeration algorithms, we will study whether knowing the support of a Nash equilibrium, i.e. the actions that are assigned non-zero probability, can reduce the computational complexity of solving for a Nash equilibrium. We will start with two-player games and proceed to general-sum games.

S2.1.1 Two-player games

Suppose we have a two-player game where one player has $$m$$ actions and the other player has $$n$$ actions. As described in earlier lectures, such games are commonly represented by a pair of $m \times n$ matrices $$( R , C )$$ . The actions of one player, called “Row,” are in one-to-one correspondence with the integers $\{1 , \dots , m\}$ which index the rows of these matrices, and the actions of the other player, called “Column,” are in one-to-one correspondence with the integers $\{1 , \dots , n\}$ which index the columns of these matrices. In particular, when Row plays action $$i$$ and Column plays action $$j$$ , they receive payoffs $R_{i j}$ and $C_{i j}$ respectively. When Row uses a distribution $$x$$ over $\{1 , \dots , m\}$ and Column uses a distribution $$y$$ over $\{1 , \dots , n\}$ , they receive expected payoffs $x^{T} R y$ and $x^{T} C y$ respectively. We will assume that each payoff entry in $$R$$ and $$C$$ is a rational number whose numerator and denominator can be described using $$L$$ bits.

Now, suppose that someone told us the supports $S_{R}$ and $S_{C}$ of the Row and Column players’ mixed strategies, respectively, in some Nash equilibrium of the game. Using this information, we can construct the following linear program to find a Nash equilibrium $$( x , y )$$ :

\displaystyle \mathord{\text{max }} 1

\displaystyle \mathord{\text{s.t. }} e_{i}^{T} R y

\displaystyle \ge e_{k}^{T} R y , \forall i \in S_{R} , \forall k \in \left[ m \right]

\displaystyle x^{T} C e_{j}

\displaystyle \ge x^{T} C e_{k} , \forall j \in S_{C} , \forall k \in \left[ n \right]

\displaystyle \sum x_{i} = 1

\displaystyle \mathord{\text{ and }} \sum y_{i} = 1

\displaystyle x_{i} \ge 0 , \forall i \in S_{R}

\displaystyle \mathord{\text{ and }} x_{i} = 0 , \forall i \in \left[ m \right] \ S_{R}

\displaystyle y_{j} \ge 0 , \forall j \in S_{C}

\displaystyle \mathord{\text{ and }} y_{j} = 0 , \forall j \in \left[ n \right] \ S_{C}

The feasibility of this linear program follows from the fact that $S_{R}$ and $S_{C}$ are the supports in some Nash equilibrium of the game. This Nash equilibrium is a feasible solution to this linear program. In the other direction, any feasible solution to the above linear program is a Nash equilibrium. This is because if $$( x , y )$$ is a feasible solution to the above linear program, then $$x$$ places positive probability only on a subset of $S_{R}$ and $$y$$ places positive probability only on a subset of $S_{C}$ . At the same time, the first couple of constraints imply that any action in $S_{R}$ must be a best response to $$y$$ and any action in $S_{C}$ must be a best response to $$y$$ . Putting these together we have the implications, which mean that $$( x , y )$$ is a Nash equilibrium:

\displaystyle \forall i : \hspace{0.22em} \hspace{0.22em} x_{i} > 0 \hspace{0.22em} \hspace{0.22em} ⇒ i \in S_{R} \hspace{0.22em} \hspace{0.22em} ⇒ i \hspace{0.22em} \mathord{\text{is a best response to }} y ; \hspace{0.22em} \mathord{\operatorname{and}}

\displaystyle \forall j : \hspace{0.22em} \hspace{0.22em} y_{j} > 0 \hspace{0.22em} \hspace{0.22em} ⇒ j \in S_{C} \hspace{0.22em} ⇒ j \hspace{0.22em} \mathord{\text{is a best response to }} x .

If we don’t know the supports of some Nash equilibrium, we can enumerate over all possible pairs of supports $( S_{R} , S_{C} ) \subseteq [ m ] \times [ n ]$ , and try to find a feasible solution of the corresponding linear program. As a Nash equilibrium always exists, at least one of these linear programs will be feasible. So the overall running time will be $2^{m + n} ⋅ \mathord{\operatorname{poly}} ( | R | , | C | )$ , where the $2^{m + n}$ factor is due to trying all possible pairs of supports, and the polynomial factor in the descriptions of the matrices $$R$$ and $$C$$ is determined by the complexity of solving a linear program.

As a corollary of the correctness of the above algorithm, we also get a proof of the existence of Nash equilibria that use rational numbers of polynomial bit complexity in the size of the game.

Corollary S2.1 .

In any two-player game, there exists a Nash equilibrium whose mixed strategies use only rational numbers in their probability distributions. Moreover, these numbers have polynomial bit complexity in the bit complexity required to represent the payoff matrices of the game.

Proof.

This follows from the correctness of the support enumeration algorithm. If there is a Nash equilibrium with supports

S_{R}

and

S_{C}

, then the polytope of the corresponding LP is non-empty and any feasible solution is a Nash equilibrium. In particular, any vertex is a Nash equilibrium, and any vertex is a vector of rational numbers whose bit complexity is polynomial in the description of the LP, and hence the description of the game.

As remarked in Lecture 3, however, the corollary is not true for $$k$$ -player games where $$k > 2$$ . Indeed, Nash’s 1951 paper [Nas51[Nas51] Nash, J. (1951). Non-Cooperative Games. Annals of Mathematics, 54(2), 286–295. link] already gave an example of a 3-player game that only has irrational equilibria.

S2.1.2 $$n$$ -player games

Now, let’s consider how to generalize the approach to $$n$$ -player games, for $$n > 2$$ . Suppose that someone told us the support $S_{i} \subseteq A_{i}$ of each player $$i$$ ‘s mixed strategy in some Nash equilibrium of the game. Given this information, we could solve the following program to find a Nash equilibrium $x = ( x_{1} , \dots , x_{n} ) \in \Delta ( A_{1} ) \times \dots \times \Delta ( A_{n} )$ :

\displaystyle \forall \hspace{0.22em} \mathord{\operatorname{player}} \hspace{0.22em} i : \hspace{0.22em} \hspace{0.22em} \hspace{0.22em}

\displaystyle u_{i} \left( a_{i} ; x_{- i} \right) \ge u_{i} \left( a_{i}' ; x_{- i} \right) , \forall a_{i} \in S_{i} , \forall a_{i}' \in A_{i} ;

\displaystyle \sum_{a_{i} \in A_{i}} x_{i} \left( a_{i} \right) = 1 ;

\displaystyle x_{i} \left( a_{i} \right) \ge 0 , \forall a_{i} \in S_{i} ;

\displaystyle x_{i} \left( a_{i} \right) = 0 , \forall a_{i} \in A_{i} \ S_{i} .

Indeed, if there is a Nash equilibrium $x = ( x_{1} , \dots , x_{n} )$ where each $x_{i}$ has support $S_{i}$ , then this Nash equilibrium is a solution to the above system of polynomial equations and inequalities. In the other direction, any feasible solution $x = ( x_{1} , \dots , x_{n} )$ to the above system is a Nash equilibrium. Indeed, any feasible solution satisfies that for all players $$i$$ , $x_{i}$ assigns positive probability to a subset of $S_{i}$ . Moreover, any action in $S_{i}$ is a best response to $x_{- i}$ . Putting these together we have the following implications, which mean that $$x$$ is a Nash equilibrium:

\displaystyle \forall \hspace{0.22em} \mathord{\operatorname{players}} \hspace{0.22em} i , \forall a_{i} \in A_{i} : \hspace{0.22em} \hspace{0.22em} x_{i} \left( a_{i} \right) > 0 \hspace{0.22em} \hspace{0.22em} ⇒ a_{i} \in S_{i} \hspace{0.22em} \hspace{0.22em} ⇒ a_{i} \hspace{0.22em} \mathord{\text{is a best response to }} x_{- i} .

However, notice that now $u_{i} ( a_{i} ; x_{- i} )$ is not linear in $$x$$ , but a polynomial of degree $$n - 1$$ . So the above problem amounts to solving a system of polynomial equations and inequalities in the variables $$x$$ .

To analyze the running time, let us suppose for simplicity that every player has $$k$$ actions. Then the above problem is a system of $M = O ( n ⋅ k^{2} )$ polynomial equations and inequalities, of degree $$D = n - 1$$ in $$N = n \cdot k$$ variables.¹1We can reduce the number of constraints to $$M = O ( n \cdot k )$$ as, if we are a bit less wasteful, we can write $$O ( k )$$ as opposed to $O ( k^{2} )$ constraints per player. But this won’t affect the running-time asymptotics. This can be solved, to $$B$$ bits of accuracy per variable, using tools from the existential theory of the reals [Ren92[Ren92] Renegar, J. (1992). On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier elimination. Journal of Symbolic Computation, 13(3), 329–352.], in time

\displaystyle B ⋅ \left( n k^{n} \right) ⋅ L ⋅ \left( M D \right)^{O \left( N \right)} = B ⋅ L ⋅ \left( n k \right)^{O \left( n k \right)} ,

where $$L$$ is the number of bits needed to represent a single payoff entry in the game.²2The factor of $( n k^{n} )$ on the left hand side of the afore-stated running time is for converting all the payoffs in the game, which are rational numbers with $$L$$ bits in the numerator and the denominator, to integers by multiplying all numbers with their least common multiple. Enumerating over all possible supports incurs an additional factor of $2^{n k}$ so the overall running time to compute a Nash equilibrium with $$B$$ bits of accuracy per entry is:

\displaystyle B ⋅ L ⋅ \left( n k \right)^{O \left( n k \right)} .

Recall that the bits required to represent a $$n$$ -player game with $$k$$ actions per player is $L ⋅ n ⋅ k^{n}$ . So the running time of our algorithm could be exponential in the description of the game, e.g. when $$n$$ stays constant and $$k$$ goes to infinity. On the other hand, the running time is quasi-polynomial if the growth of $$k$$ is bounded by a polynomial in $$n$$ .³3A quasi-polynomial-time algorithm for some computational task is an algorithm that solves an instance $$Π$$ of the task in time $2^{\mathord{\operatorname{poly}} ( \operatorname{log} d ( Π ) )}$ , where $$d ( Π )$$ is the description complexity of instance $$Π$$ . If the polynomial in the exponent of the running time is of degree $$1$$ the algorithm is called polynomial-time.

S2.2 Algorithms for Symmetric Games

We will now discuss whether the running times of our algorithms from the previous section can be improved for the class of symmetric games.

Definition S2.2 .

A $$n$$ -player game is called symmetric iff:

All players have the same set of actions: $A_{1} = \dots = A_{n} = \{1 , . . . , k\}$ ; and
there exists some function $$f$$ of $$k + 1$$ arguments such that every player $$i$$ ‘s utility can be written as: $u_{i} ( a_{i} ; a_{- i} ) = f ( a_{i} ; n_{1} ( a_{- i} ) , . . . , n_{k} ( a_{- i} ) )$ , where $n_{j} ( a_{- i} )$ is the number of players choosing action $$j$$ in action profile $a_{- i}$ .

That is, all players have the same set of actions, and all players have the same utility function that depends on their own action and the number of other players choosing each action.

For example, rock-paper-scissors is a two-player symmetric game. Guess- $\frac{2}{3}$ -of-the-average,⁴4wikipedia where $$n$$ players submit numbers in $\{0 , \dots , 100\}$ and whoever is closest to $$2 / 3$$ s of the average wins $\$ 1$ , which is split uniformly if there are ties, is a multi-player symmetric game. Also, congestion games, where players choose paths between the same source and destination nodes in some network and they suffer traffic depending on the number of players using each edge on their path, are symmetric games. Notice that describing symmetric games can be done much more succinctly than general games. In particular, a $$n$$ -player $$k$$ -action symmetric game can be described by specifying $O ( \operatorname*{min} \{k n^{k - 1} , k^{n}\} )$ numbers, which are exponentially fewer compared to the $O ( n k^{n} )$ numbers needed to describe an abitrary game, when $$n$$ is large and $$k$$ is small.

S2.2.1 Symmetric equilibria: existence and computation

In rock-paper-scissors, the unique Nash equilibrium of the game is symmetric, i.e. both players use the uniform mixture over their actions. More generally, a symmetric Nash equilibrium is defined as follows.

Definition S2.3 .

In a symmetric game, a Nash equilibrium

x = ( x_{1} , \dots , x_{n} )

is called symmetric if

x_{1} = x_{2} = \dots = x_{n}

, i.e. all players use the same mixed strategy.

While rock-paper-scissors has a symmetric Nash equilibrium, it is a priori not clear whether symmetric games ought to have a symmetric Nash equilibrium. As it turns out, this must be the case, as was shown by Nash in his 1951 paper. Indeed, Nash showed a more general statement than the statement below.

Theorem S2.4 ([Nas51]) .

In every symmetric game, there exists a symmetric Nash equilibrium.

Proof.

Recall Nash’s function $f : \times_{i} \Delta ( A_{i} ) \to \times_{i} \Delta ( A_{i} )$ , which maps some $$x$$ to a $$y$$ defined as follows, for all players $$i$$ and actions $a_{i} \in A_{i}$ :

\displaystyle y_{i} \left( a_{i} \right) = \frac{x_{i} \left( a_{i} \right) + \operatorname*{max} \left( 0 , u_{i} \left( a_{i} ; x_{- i} \right) - u_{i} \left( x \right) \right)}{1 + \sum_{a_{i}' \in A_{i}} \operatorname*{max} \left( 0 , u_{i} \left( a_{i}' ; x_{- i} \right) - u_{i} \left( x \right) \right)} .

Suppose we restrict the domain of Nash’s function to the set:

\displaystyle \times_{i} \Delta \left( A_{i} \right) ∩ \left\{x_{1} = x_{2} = . . . = x_{n}\right\} .

Then the range of the function will be a subset of this same restricted set, since every player performs the same “update” in the function $$f$$ . So $$f$$ maps points of the restricted set to points in the same set. Moreover, the set is convex, closed and bounded. So we can use Brouwer’s fixed point theorem to show the existence of a fixed point in the restricted set. This fixed point is a Nash equilibrium as we saw in the proof of Nash’s theorem in Lecture 1. And since it belongs to the restricted set, it must be a symmetric one.

A symmetric Nash equilibrium $x = ( x_{1} , \dots , x_{n} )$ , where $x_{1} = \dots = x_{n} ,$ of a $$n$$ -player $$k$$ -action symmetric game can be found as follows:

Guess the support of $x_{i}$ : $2^{k}$ possibilities;
Write down a system of polynomial equations and inequalities corresponding to the Nash equilibrium conditions for the guessed support. This is a simplified version of the system we wrote down for general games in Section S2.1.2. Done well, the total number of constraints is $$M = O ( k )$$ . The polynomials involved have degree $$D = n - 1$$ in $$N = k$$ variables (c.f. $$k \cdot n$$ variables for general games), so the system can be solved to $$B$$ bits of accuracy per variable using the existential theory of the reals in a number of operations equal to:

$\displaystyle \operatorname*{min} \left\{k n^{k - 1} , k^{n}\right\} ⋅ L ⋅ \left( D ⋅ M \right)^{O \left( N \right)} ≡ \operatorname*{min} \left\{k n^{k - 1} , k^{n}\right\} ⋅ L ⋅ \left( k n \right)^{O \left( k \right)} ,$

where $$L$$ is the number of bits needed to represent a single payoff entry in the game.⁵5As above, the factor of $\operatorname*{min} \{k n^{k - 1} , k^{n}\}$ in the afore-stated running time is for converting all the payoffs in the game, which are rational numbers with $$L$$ bits in the numerator and the denominator, to integers by multiplying all numbers with their least common multiple.

So the overall running time is $\operatorname*{min} \{k n^{k - 1} , k^{n}\} ⋅ L ⋅ ( k n )^{O ( k )} ,$ which is polynomial in the description of the game if $$k = O ( n )$$ .

S2.2.2 Symmetrization

In the previous section, we saw that, when the number of actions $$k = O ( n )$$ and the game is symmetric, Nash equilibria can be computed in polynomial time via support enumeration and solving systems of polynomial equations and inequalities. Can we hope to get a polynomial-time algorithm when $$k = ω ( n )$$ ?

We will show that this is impossible for two-player symmetric games, unless there is a polynomial-time algorithms for arbitrary two-player games. In particular, we will show a polynomial-time reduction from the problem of computing a Nash equilibrium in general two-player games to the problem of computing a Nash equilibrium in two-player symmetric games. The reduction we present is due to Gale, Kuhn and Tucker [GKT52[GKT52] Gale, D., Kuhn, H. W., & Tucker, A. W. (1952). On Symmetric Games. Contributions to the Theory of Games (AM-24), 1, 81–87.].

Suppose that we are given an arbitrary two-player game $\mathcal{G}_{1} \coloneqq ( R , C )$ and we want to compute a Nash equilibrium of this game. Given the following simple exercise, we will assume, without loss of generality, that $$R$$ and $$C$$ have strictly positive entries, i.e. that $R , C \in \mathbb{R}_{+}^{m \times n} ,$ where $$m$$ and $$n$$ are, respectively, the number of actions of the row and column players.

Exercise S2.5 .

Show that computing a Nash equilibrium of an arbitrary game

\mathcal{G}

can be polynomial-time reduced to the problem of computing a Nash equilibrium of a game

\mathcal{G}'

whose payoff entries are all strictly positive.

Next, we will construct a $( m + n ) \times ( m + n )$ symmetric game $\mathcal{G}_{2}$ , with the following payoff matrices in block form:

\displaystyle \mathcal{G}_{2} \coloneqq \begin{pmatrix}0 , 0 & R , C \\ C^{T} , R^{T} & 0 , 0\end{pmatrix} .

Theorem S2.6 .

Given a Nash equilibrium of

\mathcal{G}_{2}

, we can efficiently compute a Nash equilibrium of

\mathcal{G}_{1}

Proof.

Suppose we are given a Nash equilibrium of $\mathcal{G}_{2}$ . We denote this equilibrium by $( [ x_{1} ; y_{1} ] , [ x_{2} ; y_{2} ] )$ , where $[ x_{1} ; y_{1} ]$ is the mixed strategy of the row player and $[ x_{2} ; y_{2} ]$ the mixed strategy of the column player in block form, as shown in the following diagram:

	$x_{2}$	$y_{2}$
$x_{1}$	$$0 , 0$$	$$R , C$$
$y_{1}$	$C^{T} , R^{T}$	$$0 , 0$$

First, at least one of $x_{1}$ and $y_{1}$ must be nonzero. Assume WLOG that $x_{1} \ne 0$ . We claim the following:

Claim S2.7 .

x_{1} \ne 0

implies that

y_{2} \ne 0

Proof.

Using our positivity assumption for the entries of the game, if

y_{2} = 0

, then the row player in game

\mathcal{G}_{2}

could improve her expected payoff by setting

x_{1} = 0

and adding

\Vert x_{1}\Vert_{1}

probability to any action in the bottom block. This contradicts that

( [ x_{1} ; y_{1} ] , [ x_{2} ; y_{2} ] )

is a Nash equilibrium.

Claim S2.8 .

Let

\hat{x}_{1} = \frac{x_{1}}{\Vert x_{1}\Vert_{1}}

and

\hat{y}_{2} = \frac{y_{2}}{\Vert y_{2}\Vert_{1}}

. Then

( \hat{x}_{1} , \hat{y}_{2} )

is a Nash equilibrium of

\(( R , C )\)

Proof.

By contradiction. Suppose $( \hat{x}_{1} , \hat{y}_{2} )$ is not a Nash equilibrium of $\mathcal{G}_{1}$ . Then without loss of generality the row player can improve her expected payoff by switching to some $\tilde{x}_{1}$ . Then

\displaystyle \tilde{x}_{1}^{T} R \hat{y}_{2} > \hat{x}_{1}^{T} R \hat{y}_{2} .

(1)

Subclaim S2.9 .

1 implies that the row player in

\mathcal{G}_{2}

can improve her payoff by switching to

[ \tilde{x}_{1} ⋅ \Vert x_{1}\Vert_{1} ; y_{1} ]

from

[ \hat{x}_{1} ⋅ \Vert x_{1}\Vert_{1} ; y_{1} ]

Proof Subclaim S2.9.

The expected payoff of the row player in $\mathcal{G}_{2}$ from mixed strategy $[ \tilde{x}_{1} ⋅ \Vert x_{1}\Vert_{1} ; y_{1} ]$ is

\displaystyle \left\Vert x_{1}\right\Vert_{1} ⋅ \tilde{x}_{1}^{T} R y_{2} + y_{1}^{T} C^{T} x_{2} .

Her expected payoff from the mixed strategy $[ \hat{x}_{1} ⋅ \Vert x_{1}\Vert_{1} ; y_{1} ]$ is

\displaystyle \left\Vert x_{1}\right\Vert_{1} ⋅ \hat{x}_{1}^{T} R y_{2} + y_{1}^{T} C^{T} x_{2} .

The first of these payoffs is strictly larger, due to 1. This concludes the proof of the subclaim.

Given Subclaim S2.9, we get a contradiction to our assumption that $( [ x_{1} ; y_{1} ] , [ x_{2} ; y_{2} ] )$ is a Nash equilibrium of $\mathcal{G}_{2}$ .

We conclude that finding a Nash equilibrium in general two-player games can be polynomial-time reduced to the same problem for symmetric two-player games. An interesting open problem is whether this kind of symmetrization reduction can be generalized to games with more than $$2$$ players.

Open Problem S2.10 .

Is there a polynomial-time reduction from general

\(3\)

-player games to symmetric

\(3\)

-player games?

S2.3 The Lemke-Howson Algorithm

Switching gears from the previous sections, we turn to algorithms for computing equilibria that exploit the fixed point nature of Nash equilibrium at a deeper level. In particular, we describe the celebrated Lemke and Howson algorithm [LH64[LH64] Lemke, C. E., & Howson, J. T., Jr. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413–423.], which was proposed in 1964 as a method to compute an exact Nash equilibrium of a two-player game $$( R , C )$$ whose entries are rational numbers. This is a feasible task, as there always exists a Nash equilibrium using rational probabilities, as we have seen earlier. Indeed, the correctness proof this algorithm not only proves this fact but also that a Nash equilibrium exists. As such, the correctness proof of this algorithm provides an alternative proof of the existence of Nash equilibria in two-player games, which does not make use of Brouwer’s fixed point theorem. As we will see, the proof will be reminiscent of our proof of Sperner’s lemma from Lecture 2, and there is a deeper reason for that, as we will see in future lectures.

S2.3.1 Preparation: symmetry and non-degeneracy

To simplify our presentation, we will assume that the input game is a symmetric $n \times n$ game, i.e. $C = R^{T}$ , and we will target finding a symmetric equilibrium of this game, which is guaranteed to exist by Theorem S2.4. From our work in Section S2.2.2, we can make this assumption that the game is symmetric without loss of generality. Indeed, if a given game is asymmetric we can polynomial-time reduce it to a symmetric one. The original version of the Lemke-Howson algorithm applies directly to asymmetric games, but we believe that its presentation for symmetric games is a bit simpler.

The idea of the algorithm is to perform pivoting steps between the vertices of a polytope related to the game until a Nash equilibrium is found. The ( $$n$$ -dimensional) polytope of interest is given by

\displaystyle R ⋅ z \le 1 , z \ge 0 ,

where $$z$$ is an $$n$$ -dimensional vector.

We now make an additional assumption: at every vertex of the above polytope, exactly $$n$$ out of the $$2 n$$ inequalities are tight. We can make this assumption because if it is not true, we can perturb the original game entries with exponentially small noise to make it happen. The equilibria of the perturbed game will be approximate equilibria of the original game, and these can be converted to exact equilibria, as long as the noise that was added to the original game is sufficiently small. This is what the following exercise asks you to do:

Exercise S2.11 .

Part 1. Show that the Lemke-Howson polytope can be perturbed with exponentially small noise so that at every vertex exactly

\(n\)

of the inequalities are tight. Part 2. Show that, given a Nash equilibrium of the perturbed game, an equilibrium of the original game can be recovered in polynomial time.

S2.3.2 Main description of the algorithm

With the above setup, let us proceed to the meat of the algorithm. We make the following definition.

Definition S2.12 .

Action $$i$$ is represented at a vertex $$z$$ of the polytope if at least one of the following inequalities is tight:

\displaystyle z_{i} \ge 0

\displaystyle R_{i} z \le 1

Furthermore, we call any vertex of the polytope where all actions are represented a democracy.

Notice that $( 0 , 0 , \dots , 0 )$ is a democracy according to our definition. We make an interesting observation about democracies.

Lemma S2.13 .

If a vertex

z \ne 0

of the polytope is a democracy, then

( \frac{z}{\Vert z\Vert_{1}} , \frac{z}{\Vert z\Vert_{1}} )

is a Nash equilibrium.

Proof.

At a democracy we have the following implication:

\displaystyle \forall i : \hspace{0.22em} \hspace{0.22em} \hspace{0.22em} z_{i} > 0 ⟹ R_{i} z = 1 .

Hence

\displaystyle \forall i : \hspace{0.22em} \hspace{0.22em} \hspace{0.22em} z_{i} > 0 ⟹ R_{i} z \ge R_{j} z , \forall j

and after normalization:

\displaystyle \forall i : \hspace{0.22em} \hspace{0.22em} \hspace{0.22em} \frac{1}{\left\Vert z\right\Vert_{1}} ⋅ z_{i} > 0 ⟹ e_{i}^{T} R ⋅ \frac{z}{\left\Vert z\right\Vert_{1}} \ge e_{j}^{T} R ⋅ \frac{z}{\left\Vert z\right\Vert_{1}} , \forall j .

Notice that these are exactly the equilibrium conditions for $( \frac{z}{\Vert z\Vert_{1}} , \frac{z}{\Vert z\Vert_{1}} )$ to be a symmetric Nash equilibrium of the game.

The goal of the Lemke-Howson algorithm is to find a democracy in the given polytope. The algorithm operates as follows. Let’s call $$n$$ the “special action,” albeit this choice is arbitrary.

Step $$0$$ : Start at vertex $v_{0} \coloneqq ( 0 , 0 , \dots , 0 )$ .
Comment: By non-degeneracy, there are exactly $$n$$ edges of the polytope adjacent to $v_{0}$ . Each of these edges corresponds to un-tightening one of the $z_{i} \ge 0$ inequalities which are tight at $v_{0}$ .
Keeping all other inequalities tight, un-tighten the inequality $z_{n} \ge 0$ (which corresponds to our special action $$n$$ ). This defines an edge of the polytope adjacent to $v_{0}$ .
Step 1: Go to the other endpoint of this edge. If the obtained vertex $v_{1}$ is a democracy, then a Nash equilibrium has been found because $v_{1} \ne 0$ .
Otherwise, one of the actions $1 , \dots , n - 1$ , say action $j_{1}$ , is represented twice, by both $z_{j_{1}} = 0$ (which was already tight) and $R_{j_{1}} z = 1$ (which just became tight).
Comment: For the next step, we will un-tighten one of the two inequalities that are tight for $j_{1}$ . If we un-tighten $R_{j_{1}} z \le 1$ , this would define the same edge $( v_{0} v_{1} )$ that brought us to $v_{1}$ . To make progress we will un-tighten instead the other inequality representing action $j_{1}$ .
Un-tightening $z_{j_{1}} \ge 0$ while keeping tight all other inequalities that were tight defines an edge $( v_{1} v_{2} ) \ne ( v_{0} v_{1} )$ of the polytope.
Step 2: Go to vertex $v_{2}$ . If $v_{2}$ is a democracy, then stop.

Comment: It will be shown (in the correctness analysis below) that it must be that $v_{2} \ne 0$ , and hence if $v_{2}$ is a democracy then $v_{2} / \Vert v_{2}\Vert_{1}$ is a symmetric Nash equilibrium.
Otherwise, again some action $j_{2} \ne n$ is doubly represented at $v_{2}$ , all other actions in $\{1 , \dots , n - 1\}$ are represented once, and the special action $$n$$ is not represented at all.

/*Proof: This is because, for all actions who were singly represented at $v_{1}$ , i.e. before the step was taken, their corresponding inequalities were maintained tight during the step. So they are still represented. Action $j_{1}$ was doubly represented at vertex $v_{1}$ and we only un-tightened one of its tight inequalities. So it is still represented at vertex $v_{2}$ via the inequality that we did not un-tighten. Finally, action $$n$$ was not represented before the step and since $v_{2}$ is not a democracy it is still not represented.*/
…
Step $$t$$ : At the generic step $$t$$ of the algorithm, the algorithm arrives at vertex $v_{t}$ and performs the following case analysis:
- if $v_{t}$ is a democracy, stop. Comment: It will be shown that it must be that $v_{t} \ne 0$ .
- if vertex $v_{t}$ is not a democracy then one action $j_{t}$ is represented twice, all other actions in $\{1 , \dots , n - 1\}$ are represented once, and action $$n$$ is not represented at all; the proof of this property can be done by induction on $$t$$ assuming that this property holds for $v_{1} , \dots , v_{t - 1}$ and that the generic steps of the algorithm follow the description below.
- between $R_{j_{t}} z \le 1$ and $z_{j_{t}} \ge 0$ , un-tighten the one that defines an edge $( v_{t} v_{t + 1} ) \ne ( v_{t - 1} v_{t} )$ .
- for Step $$t + 1$$ , jump to $v_{t + 1}$ .

We are now ready to show that the algorithm is guaranteed to terminate at a non-zero democracy, thereby recovering a Nash equilibrium of the game.

Theorem S2.14 .

The Lemke-Howson algorithm will terminate and it will terminate at a non-zero democracy.

Proof.

The Lemke-Howson algorithm defines a walk $v_{0} , \dots , v_{t} , \dots$ on the vertices of the polytope. We show that the vertices encountered in this walk satisfy a special property.

Claim S2.15 .

For all $$t$$ , $v_{t}$ is either a democracy, or it satisfies the following property:

\(Π:\)

All of the actions in

\{1 , \dots , n - 1\}

are represented at

v_{t}

, exactly one of them is represented twice, and action

\(n\)

is not represented at all.

Proof.

v_{0}

is a democracy. In the description of the algorithm, we justified that

v_{1}

is either a democracy or satisfies property

\(Π\)

. In the description of the algorithm we also justified that if

v_{t - 1}

satisfied property

\(Π\)

then

v_{t}

is either a democracy or it satisfies property

\(Π\)

Consider now all the vertices of the polytope that satisfy property $$Π$$ , as well as all the vertices of the polytope that are democracies. We define an auxiliary graph $$G$$ on these vertices, where the vertices satisfying property $$Π$$ have exactly two neighbors in $$G$$ , and those that are democracies have exactly one neighbor in $$G$$ . In particular,

The two neighbors (in $$G$$ ) of a vertex $$v$$ satisfying property $$Π$$ are obtained from the polytope as follows: If $$j$$ is the action that is represented twice at $$v$$ , consider un-tightening either $z_{j} \ge 0$ or $R_{j} z \le 1$ . Either one will define an edge of the polytope adjacent to $$v$$ whose other endpoint is either a democracy or a vertex satisfying property $$Π$$ . Set those two vertices to be the neighbors of $$v$$ in $$G$$ .
The single neighbor (in $$G$$ ) of a vertex $$v$$ that is a democracy is obtained from the polytope as follows: Since $$v$$ is a democracy, either $z_{n} \ge 0$ or $R_{n} z \le 1$ is tight. Consider un-tightening whichever inequality is tight. This defines an edge of the polytope whose other endpoint is either a democracy or a vertex satisfying property $$Π$$ . Set that vertex to be the neighbor of $$v$$ in $$G$$ .

Clearly $$G$$ comprises paths and cycles, as every vertex has degree either $$1$$ or $$2$$ . Moreover, all democracies are endpoints of paths in $$G$$ , since they have degree $$1$$ . Let’s call “main path” the path that has $v_{0} = ( 0 , \dots , 0 )$ as one of its endpoints and some democracy $v^{∗} \ne v_{0}$ as its other endpoint. The following can be easily shown by induction.

Claim S2.16 .

The Lemke-Howson algorithm traverses the main path starting from

v_{0}

, moving in the direction of

v^{∗}

, visiting every vertex in this path once, and terminating at

v^{∗}

Given the claim, the proof is concluded.

We make some final remarks about the Lemke-Howson algorithm.

The algorithm provides an alternative proof that a Nash equilibrium exists in 2-player games. In particular, the existence of a Nash equilibrium is implied by the correctness of the algorithm.
Moreover, it shows that there always exists a rational equilibrium in 2-player games.
The proof works by virtue of a parity argument, reminiscent of the proof of Sperner’s lemma. It identifies a directed path on the vertices of the polytope whose sink is a solution.
Its worst-case running time is exponential in the number of actions. This lower bound was established by Savani and von Stengel [SV06[SV06] Savani, R., & Von Stengel, B. (2006). Hard-to-solve bimatrix games. Econometrica, 74(2), 397–429.].
There are generalizations of the Lemke-Howson algorithm for multi-player games working with manifolds instead of polytopes. See Rosenmüller [Ros71[Ros71] Rosenmüller, J. (1971). On a generalization of the Lemke–Howson algorithm to noncooperative N-person games. SIAM Journal on Applied Mathematics, 21(1), 73–79.] and Wilson [Wil71[Wil71] Wilson, R. (1971). Computing equilibria of n-person games. SIAM Journal on Applied Mathematics, 21(1), 80–87.].

S2.4 Bibliography for this lecture

[PR08]	Papadimitriou, C. H., & Roughgarden, T. (2008). Computing correlated equilibria in multi-player games. Journal of the ACM (JACM), 55(3), 1–29.
[Nas51]	Nash, J. (1951). Non-Cooperative Games. Annals of Mathematics, 54(2), 286–295. `http://www.jstor.org/stable/1969529`
[Ren92]	Renegar, J. (1992). On the computational complexity and geometry of the first-order theory of the reals. Part III: Quantifier elimination. Journal of Symbolic Computation, 13(3), 329–352.
[GKT52]	Gale, D., Kuhn, H. W., & Tucker, A. W. (1952). On Symmetric Games. Contributions to the Theory of Games (AM-24), 1, 81–87.
[LH64]	Lemke, C. E., & Howson, J. T., Jr. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12(2), 413–423.
[SV06]	Savani, R., & Von Stengel, B. (2006). Hard-to-solve bimatrix games. Econometrica, 74(2), 397–429.
[Ros71]	Rosenmüller, J. (1971). On a generalization of the Lemke–Howson algorithm to noncooperative N-person games. SIAM Journal on Applied Mathematics, 21(1), 73–79.
[Wil71]	Wilson, R. (1971). Computing equilibria of n-person games. SIAM Journal on Applied Mathematics, 21(1), 80–87.

Notes

1We can reduce the number of constraints to $$M = O ( n \cdot k )$$ as, if we are a bit less wasteful, we can write $$O ( k )$$ as opposed to $O ( k^{2} )$ constraints per player. But this won’t affect the running-time asymptotics.

2The factor of $( n k^{n} )$ on the left hand side of the afore-stated running time is for converting all the payoffs in the game, which are rational numbers with $$L$$ bits in the numerator and the denominator, to integers by multiplying all numbers with their least common multiple.

3A quasi-polynomial-time algorithm for some computational task is an algorithm that solves an instance $$Π$$ of the task in time $2^{\mathord{\operatorname{poly}} ( \operatorname{log} d ( Π ) )}$ , where $$d ( Π )$$ is the description complexity of instance $$Π$$ . If the polynomial in the exponent of the running time is of degree $$1$$ the algorithm is called polynomial-time.

4wikipedia

5As above, the factor of $\operatorname*{min} \{k n^{k - 1} , k^{n}\}$ in the afore-stated running time is for converting all the payoffs in the game, which are rational numbers with $$L$$ bits in the numerator and the denominator, to integers by multiplying all numbers with their least common multiple.

	$x_{2}$	$y_{2}$
$x_{1}$	$\(0 , 0\)$	$\(R , C\)$
$y_{1}$	$C^{T} , R^{T}$	$\(0 , 0\)$

Centralized algorithms for Nash equilibrium computation

S2.1 Support Enumeration Algorithms

S2.1.1 Two-player games

S2.1.2 \(n\)-player games

S2.2 Algorithms for Symmetric Games

S2.2.1 Symmetric equilibria: existence and computation

S2.2.2 Symmetrization

S2.3 The Lemke-Howson Algorithm

S2.3.1 Preparation: symmetry and non-degeneracy

S2.3.2 Main description of the algorithm

S2.4 Bibliography for this lecture

Notes

S2.1.2 $\(n\)$ -player games