AE - Support enumeration¶

Corresponding chapters¶

Duration: 50 minutes

Objectives¶

• Obtain the Nash equilibria of a game using support enumeration.

Notes¶

Play a knockout RPSLS tournament¶

Tell students to works in pairs.

Invite students to obtain the Nash equilibria, using support enumeration for the following game:

$\begin{split}A = \begin{pmatrix} 1 & -1\\ -2 & 2\\ \end{pmatrix}\end{split}$

Ask students to apply the support enumeration algorithm.

For supports of size one: there are no pairs of best response so now we only consider $$k=2$$. This implies the following pair of linear equations:

\begin{split}\begin{align*} -{\sigma_r}_1 + 2{\sigma_r}_2 &= {\sigma_r}_1 - 2{\sigma_r}_2\\ {\sigma_r}_1 &= \frac{1}{2}{\sigma_r}_2 \end{align*}\end{split}
\begin{split}\begin{align*} {\sigma_c}_1 - {\sigma_c}_2 &= -2{\sigma_c}_1 + 2{\sigma_c}_2\\ {\sigma_c}_1 &= {\sigma_c}_2 \end{align*}\end{split}

Setting this to be probability distributions gives the final result:

\begin{split}\begin{align*} {\sigma_r} &= (1/3, 2/3)\\ {\sigma_c} &= (1/2, 1/2) \end{align*}\end{split}

We don’t need to really check the best response condition as the players have no where to deviate to but we can:

$\begin{split}A\sigma_c^T = \begin{pmatrix} 0\\ 0\\ \end{pmatrix}\end{split}$

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

$\sigma_rB =\sigma_r(-A) = (0, 0)$

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

We can confirm all of this using nashpy:

>>> import nashpy as nash
>>> import numpy as np
>>> A = np.array([[1, -1],
...               [-2, 2]])
>>> game = nash.Game(A)
>>> list(game.support_enumeration())
[(array([0.666..., 0.333...]), array([0.5, 0.5]))]


As a second example consider:

$\begin{split}A = \begin{pmatrix} 0 & -2 & 2\\ 1 & 0 & -1\\ -1 & 1 & 0\\ \end{pmatrix}\end{split}$
1. We see there are no pairs of best response, so consider $$k\in\{2,3\}$$.
2. We have the following set of utilities to consider:
1. $$I=\{1, 2\}$$
1. $$J=\{1, 2\}$$
2. $$J=\{1, 3\}$$
3. $$J=\{2, 3\}$$
2. $$I=\{1, 3\}$$
1. $$J=\{1, 2\}$$
2. $$J=\{1, 3\}$$
3. $$J=\{2, 3\}$$
3. $$I=\{2, 3\}$$
1. $$J=\{1, 2\}$$
2. $$J=\{1, 3\}$$
3. $$J=\{2, 3\}$$
4. $$I=J=\{1, 2, 3\}$$

The case for k=2 leads to contradictions (let students identify some of these).

1. $$I=J=\{1, 2, 3\}$$

In this case we have:

\begin{split}\begin{align*} -{\sigma_r}_2 + {\sigma_r}_3 &= 2{\sigma_r}_1 - {\sigma_r}_3\\ 2{\sigma_r}_1 - {\sigma_r}_3 &= -2{\sigma_r}_1 + {\sigma_r}_2\\ \end{align*}\end{split}

which has solution:

$2{\sigma_r}_1 = {\sigma_r}_2 = {\sigma_r}_3$

Similarly:

\begin{split}\begin{align*} -2{\sigma_c}_2 + 2{\sigma_c}_3 &= {\sigma_c}_1 - {\sigma_c}_3\\ {\sigma_c}_1 - {\sigma_c}_3 &= -{\sigma_c}_1 + {\sigma_c}_2\\ \end{align*}\end{split}

which has solution:

${\sigma_c}_1 = {\sigma_c}_2 = {\sigma_c}_3$
1. Now we consider which of those supports give valid mixed strategies:

1. $$I=J=\{1, 2, 3\}$$

\begin{split}\begin{align*} {\sigma_r} &= (1/5, 2/5, 2/5)\\ {\sigma_c} &= (1/3, 1/3, 1/3) \end{align*}\end{split}
2. The final step is to check the best response condition:

1. $$I=J=\{1, 2, 3\}$$

$\begin{split}A\sigma_c^T = \begin{pmatrix} 0\\ 0\\ 0\\ \end{pmatrix}\end{split}$

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

$\sigma_rB = (0, 0, 0)$

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

We can confirm all of this using nashpy:

>>> import nashpy as nash
>>> A = np.array([[0, -2, 2],
...               [1, 0, -1],
...               [-1, 1, 0]])
>>> rps = nash.Game(A)
>>> list(rps.support_enumeration())
[(array([0.2..., 0.4..., 0.4...]), array([0.333..., 0.333..., 0.333...]))]


Discuss with students about what happens when we have a 3 by 2 game?