# 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:

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

and:

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:

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

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

which gives:

which in turn corresponds to:

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:

which gives:

which in turn corresponds to:

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:

For all \(1\leq k\leq \min(m, n)\):

For all pairs of support \((I, J)\) with \(|I|=|J|=k\).

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} \]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\)

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}\).

Answer

It is immediate to note that there are no pairs of pure best responses.

All possible support pairs are:

\(I=\{1, 2\}\) and \(J=\{1,2\}\)

\(I=\{1, 2\}\) and \(J=\{1,3\}\)

\(I=\{1, 2\}\) and \(J=\{2,3\}\)

Let us solve the corresponding linear equations:

\(I=\{1, 2\}\) and \(J=\{1, 2\}\):

\[1/2{\sigma_{r}}_1-{\sigma_{r}}_2=-{\sigma_{r}}_1+3{\sigma_{r}}_2\]\[{\sigma_{r}}_1=8/3{\sigma_{r}}_2\]\[{\sigma_{c}}_1+{\sigma_{c}}_2=2{\sigma_{c}}_1-{\sigma_{c}}_2\]\[{\sigma_{c}}_1=2{\sigma_{c}}_2\]\(I=\{1, 2\}\) and \(J=\{1,3\}\):

\[1/2{\sigma_{r}}_1-{\sigma_{r}}_2=-1/2{\sigma_{r}}_1+2{\sigma_{r}}_2\]\[{\sigma_{r}}_1=3{\sigma_{r}}_2\]\[{\sigma_{c}}_1-{\sigma_{c}}_3=2{\sigma_{c}}_1+0{\sigma_{c}}_3\]\[{\sigma_{c}}_1=-{\sigma_{c}}_3\]\(I=\{1, 2\}\) and \(J=\{2,3\}\):

\[-{\sigma_{r}}_1+3{\sigma_{r}}_2=-1/2{\sigma_{r}}_1+2{\sigma_{r}}_2\]\[{\sigma_{r}}_1=2{\sigma_{r}}_2\]\[{\sigma_{c}}_2-{\sigma_{c}}_3=-{\sigma_{c}}_2+0{\sigma_{c}}_3\]\[2{\sigma_{c}}_2={\sigma_{c}}_3\]

We check which supports give valid strategies:

\(I=\{1, 2\}\) and \(J=\{1, 2\}\):

\[\sigma_r=(8/11, 3/11)\]\[\sigma_c=(2/3, 1/3, 0)\]\(I=\{1, 2\}\) and \(J=\{1, 3\}\):

\[\sigma_r=(3/4, 1/4)\]\[\sigma_c=(k, 0, -k)\]**which is not a valid strategy.**\(I=\{1, 2\}\) and \(J=\{2, 3\}\):

\[\sigma_r=(2/3, 1/3)\]\[\sigma_c=(0, 1/3, 2/3)\]

Let us verify the best response condition:

\(I=\{1, 2\}\) and \(J=\{1, 2\}\):

\[\sigma_c=(2/3, 1/3, 0)\]\[\begin{split}A\sigma_c^T= \begin{pmatrix} 1\\ 1 \end{pmatrix}\end{split}\]Thus \(\sigma_r\) is a best response to \(\sigma_c\)

\[\sigma_r=(8/11, 3/11)\]\[\sigma_r B=(1/11, 1/11, 2/11)\]Thus \(\sigma_c\) is not a best response to \(\sigma_r\) (because there is a better response outside of the support of \(\sigma_c\)).

\(I=\{1, 2\}\) and \(J=\{2, 3\}\):

\[\sigma_c=(0, 1/3, 2/3)\]\[\begin{split}A\sigma_c^T= \begin{pmatrix} -1/3\\ -1/3 \end{pmatrix}\end{split}\]Thus \(\sigma_r\) is a best response to \(\sigma_c\)

\[\sigma_r=(2/3, 1/3)\]\[\sigma_r B=(0, 1/3, 1/3)\]Thus \(\sigma_c\) is a best response to \(\sigma_r\).

Thus the (unique) Nash equilibrium for this game is:

\[((2/3, 1/3), (0, 1/3, 2/3))\]

## Exercises¶

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

## Using Nashpy¶

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