Support enumeration - solutions

1. Define the support of a strategy.

   Bookwork: https://vknight.org/gt/chapters/05/#Definition-of-support

2. Obtain the supports for the following strategy vectors:

   1. $\sigma = (1, 0, 0, 0)$: $S(\sigma)=\{1\}$
   2. $\sigma = (.5, 0, .5, 0)$: $S(\sigma)=\{1, 3\}$
   3. $\sigma = (.25, .25, .25, .25)$: $S(\sigma)=\{1, 2, 3, 4\}$

3. Define a degenerate game.

   Bookwork: https://vknight.org/gt/chapters/05/#Definition-of-nondegenerate-games

4. Construct a degenerate $3\times 3$ game.

   Many possible solutions. Here is one:

   $$ A = \begin{pmatrix} 1 & 2 & 3\\ 1 & 3 & 2\\ 0 & 1 & 4 \end{pmatrix} \qquad B = \begin{pmatrix} -1 & -2 & -3\\ -1 & -3 & -2\\ 0 & -1 & -4 \end{pmatrix} $$

   Consider $\sigma_c = (1, 0, 0)$, we have $A\sigma_c^T=\begin{pmatrix}1 & 1 & 0\end{pmatrix}$. Thus, there are two best responses to $\sigma_c$ however $|S(\sigma_c)|=1$.

5. Describe the support enumeration algorithm.

   Bookwork: https://vknight.org/gt/chapters/05/#Support-enumeration-algorithm

6. Use support enumeration to find Nash equilibria for the following games:

   1. $ A = \begin{pmatrix} 3 & 3 & 2 \\ 2 & 1 & 3 \end{pmatrix} \qquad B = \begin{pmatrix} 2 & 1 & 3 \\ 2 & 3 & 2 \end{pmatrix} $

      We need to consider three possible supports for the column player: $J\in\{(1, 2), (1, 3), (2, 3)\}$:

      1. $I=(1, 2)$ and $J=(1, 2)$, the indifference condition gives:

         $$ 2{\sigma_{r}}_1+2{\sigma_{r}}_2={\sigma_{r}}_1+3{\sigma_{r}}_2 $$

         $$ {\sigma_{r}}_1={\sigma_{r}}_2 $$

         $$ 3{\sigma_{c}}_1+3{\sigma_{c}}_2=2{\sigma_{c}}_1+{\sigma_{c}}_2 $$

         $$ {\sigma_{c}}_1=-2{\sigma_{c}}_2 $$

         which would not give a valid probability vector.

      2. $I=(1, 2)$ and $J=(1, 3)$, the indifference condition gives:

         $$ 2{\sigma_{r}}_1+2{\sigma_{r}}_2=3{\sigma_{r}}_1+2{\sigma_{r}}_2 $$

         $$ -{\sigma_{r}}_1=0 $$

         which is not valid for this support. (No need to check the condition on $\sigma_c$).

      3. $I=(1, 2)$ and $J=(2, 3)$, the indifference condition gives:

         $$ {\sigma_{r}}_1+3{\sigma_{r}}_2=3{\sigma_{r}}_1+2{\sigma_{r}}_2 $$

         $$ {\sigma_{r}}_2=2{\sigma_{r}}_1 $$

         $$ 3{\sigma_{c}}_2+2{\sigma_{c}}_3={\sigma_{c}}_2+3{\sigma_{c}}_3 $$

         $$ 2{\sigma_{c}}_2={\sigma_{c}}_3 $$

         Normalising both these solutions gives:

         $$\sigma_r=(1/3, 2/3)\qquad\sigma_c=(0, 1/3, 2/3)$$

         We confirm these two vectors are best responses to each other:

         $$A\sigma_c^T=\begin{pmatrix}7/3\\7/3\end{pmatrix}$$

         thus $\sigma_r$ is a best response to $\sigma_c$.

         $$\sigma_rB=\begin{pmatrix}2&7/3&7/3\end{pmatrix}$$

         thus $\sigma_c$ is a best response to $\sigma_r$.

      Thus the unique Nash equilibrium for this game is:

      $$((1/3, 2/3), (0, 1/3, 2/3))$$

   2. $ A = \begin{pmatrix} 3 & -1\\ 2 & 7\end{pmatrix} \qquad B = \begin{pmatrix} -3 & 1\\ 1 & -6\end{pmatrix} $

      There is a single pair of supports to investigate here giving the pair of equations:

      $$ -3{\sigma_{r}}_1+{\sigma_{r}}_2={\sigma_{r}}_1-6{\sigma_{r}}_2 $$

      $$ {\sigma_{r}}_2=4/7{\sigma_{r}}_1 $$

      $$ 3{\sigma_{c}}_1-{\sigma_{c}}_2=2{\sigma_{c}}_1+7{\sigma_{c}}_2 $$

      $$ {\sigma_{c}}_1=8{\sigma_{c}}_2 $$

      Normalising these gives: ${\sigma_{r}}_1(4/7 + 1) = 1\Rightarrow {\sigma_{r}}_1=7/11$ and ${\sigma_{c}}_1(1/8 + 1) = 1\Rightarrow {\sigma_{c}}_1=8/9$. Giving the unique nash equilibrium (there is no need to check the best response, as there are no other strategies outside of these supports):

      $$((7/11, 4/11), (8/9, 1/9))$$