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?