# Finding Nash equilibria using Support Enumeration

Chapter 3 of the Book "Algorithmic Game Theory" introduces an algorithm (page 8 of that PDF) to find mixed Nash equilibria for a bimatrix game $(A, B)$, which I struggle to understand.

($M$ and $N$ are the strategy sets of player 1 and 2, $m$ and $n$ are the number of respective strategies. Further, $x$ and $y$ are the mixed strategy vectors of player 1 and 2.)

Quote:

Algorithm 3.4 (Equilibria by support enumeration) Input: A nondegenerate bimatrix game. Output: All Nash equilibria of the game. Method: For each $k = 1, \ldots, \min{\{m, n\}}$ and each pair $(I, J)$ of $k$-sized subsets of $M$ and $N$, respectively, solve the equations $\sum_{i \in I}{x_i b_{ij}} = v$ for $j \in J$, $\sum_{i \in I}{x_i} = 1$, $\sum_{j \in J}{a_{ij} y_j} = u$, for $i \in I$, $\sum_{j \in J}{y_j} = 1$, and check that $x \ge 0, y \ge 0$, and that (3.2) holds for $x$ and analogously $y$.

Equation (3.2) is defined as

$x_i > 0 \implies (Ay)_i = u = \max{\{ (Ay)_k \mid k \in M}\}$

I fail to make any sense of this.

1. Can anyone point out a different specification/explanation of the algorithm or describe it in different words?
2. Can anyone tell what is wrong with the following reasoning?

"The algorithm description suggests that if the solution vectors $x$ and $y$ pass all checks, that the profile $(x, y)$ is then a Nash equilibrium. However, a square subgame of size 1 is a game in which both players have only one choice, and thus every $x$ and $y$ will trivially fulfill the conditions. This implies that every combination of pure strategies is a Nash equilibrium, which clearly cannot be true."

• You should change "subgame" to "restricted game". – HAL9000 Mar 11 '14 at 21:33

But solving these equations is not enough to give a Nash equilibrium. Probabilities have to be nonnegative, so if the unique solution involves negative numbers it cannot be a Nash equilibrium. Furthermore, just because all strategies used with positive probability yield the same expected payoff doesn't mean that is the best possible payoff. Maybe it is the worst, or somewhere in the middle. So you need to check Equation (3.2) to ensure that no player can do better by deviating. If this is confusing, think about how replacing $A$ and $B$ with $-A$ and $-B$ changes the game but essentially does not change the linear equations involved. The inequalities are very important.
Any $x,y$ satisfying the equations, inequalities, and (3.2) define a pair of probability distributions such that players only choose best replies to their opponent's strategy with positive probability. Therefore such $x,y$ form a Nash equilibrium. That all Nash equilibria can be found this way (in particular that both players have the same support size in a Nash equilibrium) makes heavy use of the nondegeneracy assumption.