Support enumeration

Motivating example: Coordination Game

In the Coordination game in how many situations do neither player have an incentive to independently change their strategy?

Neither player having a reason to change their strategy implies that both strategies are Best responses to each other.

To identify such pairs of strategies, we will use the General condition for a best response by considering all possible non zero valued elements \(\sigma_r\) and \(\sigma_c\).

Recall that for the Coordination game the matrices \(A\) and \(B\) are given by:

\[\begin{split}A = \begin{pmatrix} 3 & 1\\ 0 & 2 \end{pmatrix}\end{split}\]
\[\begin{split}B = \begin{pmatrix} 2 & 1\\ 0 & 3 \end{pmatrix}\end{split}\]

If we consider strategies that only play a single action there are two options for each strategy:

\[\sigma_r \in \{(1, 0), (0, 1)\}\]

and:

\[\sigma_c \in \{(1, 0), (0, 1)\}\]

We will inspect all four combinations:

  • \(\sigma_r = (1, 0)\) and \(\sigma_c = (1, 0)\) which corresponds to both players playing their first action which gives: \(u_r(\sigma_r, \sigma_c)=3\) and \(u_c(\sigma_r, \sigma_c)=2\). If the row player where to modify their strategy (while the column player stayed unchanged) to play the second action their utility would decrease. Likewise, if the column player were to modify their strategy their utility would also decrease.

  • \(\sigma_r = (1, 0)\) and \(\sigma_c = (0, 1)\) which corresponds to the row player playing their first action and the column player playing their second action which gives: \(u_r(\sigma_r, \sigma_c)=1\) and \(u_c(\sigma_r, \sigma_c)=1\). In this case, if either player were to move their utility would increase.

  • \(\sigma_r = (0, 1)\) and \(\sigma_c = (1, 0)\) which corresponds to the row player playing their second action and the column player playing their first action which gives: \(u_r(\sigma_r, \sigma_c)=0\) and \(u_c(\sigma_r, \sigma_c)=0\). In this case, if either player were to move their utility would increase.

  • \(\sigma_r = (0, 1)\) and \(\sigma_c = (0, 1)\) which corresponds to both players playing their second action which gives: \(u_r(\sigma_r, \sigma_c)=2\) and \(u_c(\sigma_r, \sigma_c)=3\). If the row player where to modify their strategy (while the column player stayed unchanged) to play the second action their utility would decrease. Likewise, if the column player were to modify their strategy their utility would also decrease.

If we now consider strategies that play both actions there is a single general form:

\[\sigma_r = (x, 1 - x)\text{ for } 0<x<1\]
\[\sigma_c = (y, 1 - y)\text{ for } 0<y<1\]

We can apply the General condition for a best response here.

If \(\sigma_r\) is a best response to \(\sigma_c\) then:

\[(A\sigma_cT)_i = \text{max}_{k\in\{1, 2\}} (A\sigma_c^T)_k \text{ for all }i \in \{1, 2\}\]

which gives:

\[\begin{split}3y + 1(1-y) &= \text{max}_{k \in\{1, 2\}} (A\sigma_c^T)_k\\ 0y + 2(1-y) &= \text{max}_{k \in\{1, 2\}} (A\sigma_c^T)_k\end{split}\]

which in turn corresponds to:

\[\begin{split}3y + 1(1 - y) & = 2(1-y)\\ y & = 1 / 4\end{split}\]

Thus \(\sigma_r = (x, 1 - x)\) with \(0<x<1\) is a best response to \(\sigma_c\) if and only if \(\sigma_c = (1/4, 3/4)\).

We will now apply the General condition for a best response again but to the column player:

If \(\sigma_c\) is a best response to \(\sigma_r\) then:

\[(\sigma_rB)_j = \text{max}_{k\in\{1, 2\}} (\sigma_rB)_k \text{ for all }j \in \{1, 2\}\]

which gives:

\[\begin{split}2x + 0(1-x) &= \text{max}_{k \in\{1, 2\}} (\sigma_rB)_k\\ 1x + 3(1-x) &= \text{max}_{k \in\{1, 2\}} (\sigma_rB)_k\end{split}\]

which in turn corresponds to:

\[\begin{split}2x & = x + 3(1-x)\\ x & = 3 / 4\end{split}\]

Thus \(\sigma_c = (y, 1 - y)\) with \(0<y<1\) is a best response to \(\sigma_r\) if and only if \(\sigma_r = (3/4, 1/4)\).

There are 3 pairs of strategies that are best responses to each other:

  • \(\sigma_r=(1,0)\) and \(\sigma_c=(1,0)\).

  • \(\sigma_r=(0,1)\) and \(\sigma_c=(0,1)\).

  • \(\sigma_r=(3/4,1/4)\) and \(\sigma_c=(1/4,3/4)\).

The support enumeration algorithm

The approach used in Motivating example: Coordination Game is in fact an application of a formalised algorithm called support enumeration.

The algorithm is as follows:

For a non Degenerate 2 player game \((A, B)\in{\mathbb{R}^{m\times n}}^2\) the following algorithm returns all pairs of best responses:

  1. For all \(1\leq k_1\leq m\) and \(1\leq k_2\leq n\);

  2. For all pairs of support \((I, J)\) with \(|I|=k_1\) and \(|J|=k_2\).

  3. Solve the following equations (this ensures we have best responses):

    \[ \begin{align}\begin{aligned} \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\end{aligned}\end{align} \]
  4. Solve

    • \(\sum_{i=1}^{m}{\sigma_{r}}_i=1\) and \({\sigma_{r}}_i\geq 0\) for all \(i\)

    • \(\sum_{j=1}^{n}{\sigma_{c}}_i=1\) and \({\sigma_{c}}_j\geq 0\) for all \(j\)

  5. Check the best response condition.

Repeat steps 3,4 and 5 for all potential support pairs.

Question

Use support enumeration to find all Nash equilibria for the game given by \(A=\begin{pmatrix} 1 & 1 & -1 \\ 2 & -1 & 0 \end{pmatrix}\) and \(B=\begin{pmatrix} 1/2 & -1 & -1/2 \\-1 & 3 & 2 \end{pmatrix}\).

Using Nashpy

See Solve with support enumeration for guidance of how to use Nashpy to use support enumeration.