The definition implies that a Nash equilibrium is a pair of best responses.
We can use this and the best response condition of the previous chapter to find Nash equilibrium.
For a given strategy $\sigma$, the support of $\sigma$: $\mathcal{S}(\sigma)$ is the set of strategies for which $\sigma_i>0$:
$$ i\in\mathcal{S}(\sigma)\Leftrightarrow \sigma_i > 0 $$For example:
In [1]:
import numpy as np
sigma = np.array([1/3, 1/2, 0, 0, 1/6])
np.where(sigma > 0) # Recall Python indexing starts at 0
Out[1]:
In [2]:
sigma = np.array([0, 0, 1, 0])
np.where(sigma > 0) # Recall Python indexing starts at 0
Out[2]:
A two player game is called nondegenerate if no mixed strategy of support size $k$ has more than $k$ pure best responses.
For example, the following game is degenerate:
$$ A = \begin{pmatrix} 1 & 1 & 0\\ 2 & 3 & 0 \end{pmatrix}\qquad B = \begin{pmatrix} 1/2 & -1 & -1/2\\ -1 & -1 & 2 \end{pmatrix} $$Indeed, consider $\sigma_c=(0, 0, 1)$, we have $|\mathcal{S}(\sigma_c)|=1$ and:
$$ A\sigma_c^T = \begin{pmatrix} 0\\ 0 \end{pmatrix} $$So the number of pure best responses to $\sigma_c$ is 2.
Thus the game considered is indeed degenerate.
In [3]:
A = np.array([[1, 1, 0], [2, 3, 0]])
sigma_c = np.array([0, 0, 1])
(np.dot(A, sigma_c))
Out[3]:
This leads to the following algorithm for identifying Nash equilibria:
For a nondegenerate 2 player game $(A, B)\in{\mathbb{R}^{m\times n}}^2$ the following algorithm returns all nash equilibria:
Solve the following equations (this ensures we have best responses):
$$\sum_{i\in I}{\sigma_{r}}_iB_{ij}=v\text{ for all }j\in J$$
$$\sum_{j\in J}A_{ij}{\sigma_{c}}_j=u\text{ for all }i\in I$$
Solve
Repeat steps 3,4 and 5 for all potential support pairs.
As an example consider the matching pennies game.
$$ A= \begin{pmatrix} 1 & -1\\ -1 & 1 \end{pmatrix}\qquad B= \begin{pmatrix} -1 & 1\\ 1 & -1 \end{pmatrix} $$Consider $k=1$: so here we are just considering supports of size 1, in other words pairs of pure best responses. The easiest way to identify these is by looking at the best responses:
$$ A= \begin{pmatrix} \underline{1} & -1\\ -1 & \underline{1} \end{pmatrix}\qquad B= \begin{pmatrix} -1 & \underline{1}\\ \underline{1} & -1 \end{pmatrix} $$
So there are no pairs.
The equations we need to solve are:
$$-{\sigma_{r}}_1+{\sigma_{r}}_2=v$$ $${\sigma_{r}}_1-{\sigma_{r}}_2=v$$
and
$${\sigma_{c}}_1-{\sigma_{c}}_2=u$$ $$-{\sigma_{c}}_1+{\sigma_{c}}_2=u$$
We don't actually care (or know!) the values of $u, v$ so we in fact solve:
$$-{\sigma_{r}}_1+{\sigma_{r}}_2={\sigma_{r}}_1-{\sigma_{r}}_2$$
$${\sigma_{c}}_1-{\sigma_{c}}_2=-{\sigma_{c}}_1+{\sigma_{c}}_2$$
which gives:
$${\sigma_{r}}_1={\sigma_{r}}_2$$
$${\sigma_{c}}_1={\sigma_{c}}_2$$
This gives:
$$\sigma_{r}=(1/2, 1/2)$$
$$\sigma_{c}=(1/2, 1/2)$$
Finally we check the best response condition: (we already did this in the previous chapter).
Note that for 2 player games with $m=n=2$ step 5 is trivial so in fact to find best mix strategy Nash equilibrium for games of this size simply reduces to finding a solution to 2 linear equations (step 3).
Let us consider a large game:
$$ A= \begin{pmatrix} 1 & 1 & -1\\ 2 & -1 & 0 \end{pmatrix}\qquad B= \begin{pmatrix} 1/2 & -1 & -1/2\\ -1 & 3 & 2 \end{pmatrix} $$
All possible support pairs are:
Let us solve the corresponding linear equations:
$I=(1, 2)$ and $J=(1, 2)$:
$$1/2{\sigma_{r}}_1-{\sigma_{r}}_2=-{\sigma_{r}}_1+3{\sigma_{r}}_2$$ $${\sigma_{r}}_1=8/3{\sigma_{r}}_2$$
$${\sigma_{c}}_1+{\sigma_{c}}_2=2{\sigma_{c}}_1-{\sigma_{c}}_2$$ $${\sigma_{c}}_1=2{\sigma_{c}}_2$$
$I=(1, 2)$ and $J=(1,3)$:
$$1/2{\sigma_{r}}_1-{\sigma_{r}}_2=-1/2{\sigma_{r}}_1+2{\sigma_{r}}_2$$ $${\sigma_{r}}_1=3{\sigma_{r}}_2$$
$${\sigma_{c}}_1-{\sigma_{c}}_3=2{\sigma_{c}}_1+0{\sigma_{c}}_3$$ $${\sigma_{c}}_1=-{\sigma_{c}}_3$$
$I=(1, 2)$ and $J=(2,3)$:
$$-{\sigma_{r}}_1+3{\sigma_{r}}_2=-1/2{\sigma_{r}}_1+2{\sigma_{r}}_2$$ $${\sigma_{r}}_1=2{\sigma_{r}}_2$$
$${\sigma_{c}}_2-{\sigma_{c}}_3=-{\sigma_{c}}_2+0{\sigma_{c}}_3$$ $$2{\sigma_{c}}_2={\sigma_{c}}_3$$
We check which supports give valid mixed strategies:
$I=(1, 2)$ and $J=(1, 2)$:
$$\sigma_r=(8/11, 3/11)$$ $$\sigma_c=(2/3, 1/3, 0)$$
$I=(1, 2)$ and $J=(1, 3)$:
$$\sigma_r=(3/4, 1/4)$$ $$\sigma_c=(k, 0, -k)$$
which is not a valid mixed strategy.
$I=(1, 2)$ and $J=(2, 3)$:
$$\sigma_r=(2/3, 1/3)$$ $$\sigma_c=(0, 1/3, 2/3)$$
Let us verify the best response condition:
$I=(1, 2)$ and $J=(1, 2)$:
$$\sigma_c=(2/3, 1/3, 0)$$
$$A\sigma_c^T= \begin{pmatrix} 1\\ 1 \end{pmatrix} $$
Thus $\sigma_r$ is a best response to $\sigma_c$
$$\sigma_r=(8/11, 3/11)$$ $$\sigma_r B=(1/11, 1/11, 2/11)$$
Thus $\sigma_c$ is not a best response to $\sigma_r$ (because there is a better response outside of the support of $\sigma_c$).
$I=(1, 2)$ and $J=(2, 3)$:
$$\sigma_c=(0, 1/3, 2/3)$$
$$A\sigma_c^T= \begin{pmatrix} -1/3\\ -1/3 \end{pmatrix} $$
Thus $\sigma_r$ is a best response to $\sigma_c$
$$\sigma_r=(2/3, 1/3)$$ $$\sigma_r B=(0, 1/3, 1/3)$$
Thus $\sigma_c$ is a best response to $\sigma_r$.
Thus the (unique) Nash equilibrium for this game is:
$$((2/3, 1/3), (0, 1/3, 2/3))$$Note that we can confirm all of this using nashpy:
In [4]:
import nashpy as nash
A = np.array([[1,-1], [-1, 1]])
game = nash.Game(A)
list(game.support_enumeration())
Out[4]:
In [5]:
A = np.array([[1, 1, -1], [2, -1, 0]])
B = np.array([[1/2, -1, -1/2], [-1, 3, 2]])
game = nash.Game(A, B)
list(game.support_enumeration())
Out[5]:
If you recall the degenerate game mentioned previously:
In [6]:
A = np.array([[1, 1, 0], [2, -1, 0]])
B = np.array([[1/2, -1, -1/2], [-1, 3, 2]])
game = nash.Game(A, B)
list(game.support_enumeration())
Out[6]: