<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Support enumeration
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.
Definition of support
Video
For a given strategy $\sigma$, the support of $\sigma$
Step1:  Definition of nondegenerate games
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
Step2:  This leads to the following algorithm for identifying Nash equilibria
Step3:  If you recall the degenerate game mentioned previously
<ASSISTANT_TASK:>
Python Code:
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
sigma = np.array([0, 0, 1, 0])
np.where(sigma > 0)  # Recall Python indexing starts at 0
Explanation: Support enumeration
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.
Definition of support
Video
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:
If $\sigma=(1/3, 1/2, 0, 0, 1/6)$: $\mathcal{S}(\sigma)={1, 2, 5}$
If $\sigma=(0, 0, 1, 0)$: $\mathcal{S}(\sigma)={3}$
End of explanation
A = np.array([[1, 1, 0], [2, 3, 0]])
sigma_c = np.array([0, 0, 1])
(np.dot(A, sigma_c))
Explanation: Definition of nondegenerate games
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.
End of explanation
import nashpy as nash
A = np.array([[1,-1], [-1, 1]])
game = nash.Game(A)
list(game.support_enumeration())
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())
Explanation: This leads to the following algorithm for identifying Nash equilibria:
Support enumeration algorithm
Video
For a nondegenerate 2 player game $(A, B)\in{\mathbb{R}^{m\times n}}^2$ the following algorithm returns all nash equilibria:
For all $1\leq k\leq \min(m, n)$;
For all pairs of support $(I, J)$ with $|I|=|J|=k$
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
$\sum_{i=1}^{m}{\sigma_{r}}i=1$ and ${\sigma{r}}_i\geq 0$ for all $i$
$\sum_{j=1}^{n}{\sigma_{c}}j=1$ and ${\sigma{c}}_j\geq 0$ for all $j$
Check the best response condition.
Repeat steps 3,4 and 5 for all potential support pairs.
2 by 2 example of support enumeration
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.
Thus we start again with $k=2$.
There is only one pair of best responses to be considered: $I=J=(1, 2)$.
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}
   $$
It is immediate to note that there are no pairs of pure best responses.
All possible support pairs are:
$I=(1, 2)$ and $J=(1,2)$
$I=(1, 2)$ and $J=(1,3)$
$I=(1, 2)$ and $J=(2,3)$
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:
End of explanation
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())
Explanation: If you recall the degenerate game mentioned previously:
End of explanation
<END_TASK>