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.
- Can anyone point out a different specification/explanation of the algorithm or describe it in different words?
-
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."
Best Answer
For your first question: In a Nash equilibrium, all strategies chosen with positive probability by a particular player yield the same expected payoff. The reason is that if they didn't, then a player could do better by moving some of his probability from a worse strategy to a better strategy. For a fixed support for each player, this condition gives several linear equations in the probabilities. The nondegeneracy assumption implies that such equations have a unique solution.
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.
To answer your second question: a Nash equilibrium of a "subgame" (if I understand your terminology this is different from what is usually meant by subgame) is not necessarily a Nash equilibrium of the original game. In particular, Equation (3.2) holding for a subgame does not imply that it holds for the original game.