Support enumeration - solutions¶

1. Define the support of a strategy.

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.

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)|=2$.

5. Describe the 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, 2), (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))$$

Previous

Next