# Best responses¶

## Motivating example: Best Responses in Matching Pennies¶

Considering the game Matching Pennies:

If the row player knows that the column player is playing the strategy \(\sigma_c=(0, 1)\) the utility of the row player is maximised by playing \(\sigma_r=(0, 1)\).

In this case \(\sigma_r\) is referred to as a **best response** to
\(\sigma_c\).

Alternatively, if the column player knows that the row player is playing the strategy \(\sigma_r=(0, 1)\) the column player’s best response is \(\sigma_c=(1, 0)\).

## Definition of a best response in a normal form game¶

In a two player game \((A,B)\in{\mathbb{R}^{m\times n}}^2\) a strategy \(\sigma_r^*\) of the row player is a best response to a column players’ strategy \(\sigma_c\) if and only if:

Where \(\mathcal{S}_1\) denotes the space of all strategies for the first player.

Similarly a mixed strategy \(\sigma_c^*\) of the column player is a best response to a row players’ strategy \(\sigma_r\) if and only if:

Question

For the Prisoners Dilemma:

What is the row player’s best response to either of the actions of the column player?

Answer

Recalling that \(A\) is given by:

Against the first action of the column player the best response is to choose the second action which gives a utility of 5. This can be expressed as:

Against the second action of the column player the best response is to choose the second action which gives a utility of 1. This can be expressed as:

The row player’s best response to either of the actions of the column player is \(\sigma_r^*=(1,0)\). This can be expressed as:

## Generic best responses in 2 by 2 games¶

In two player normal form games with \(|A_1|=|A_2|=2\): a 2 by 2 game, the utility of a row player playing \(\sigma_r=(x, 1 - x)\) against a strategy \(\sigma_c = (y, 1 - y)\) is linear in \(x\):

where:

This observation allows us to obtain the best response \(\sigma_r^*\) against any \(\sigma_c = (y, 1 - y)\).

For example, consider Matching Pennies. Below is a plot of \(u_r(\sigma_r, \sigma_c)\) as a function of \(y\) for \(\sigma_r \in \{(1, 0), (0, 1)\}\).

(Source code, png, hires.png, pdf)

Given that the utilities in both cases are linear, the best response to any value of \(y \ne 1/2\) is either \((1, 0)\) or \((0, 1\). The best response \(\sigma_r^*\) is given by:

Question

For the Matching Pennies game:

What is the column player’s best response as a function of \(x\) where \(\sigma_r=(x, 1 - x)\).

Answer

Recalling that \(B\) is given by:

This gives:

Here is a plot of the utilities:

(Source code, png, hires.png, pdf)

## General condition for a best response¶

In a two player game \((A,B)\in{\mathbb{R}^{m\times n}}^2\) a strategy \(\sigma_r^*\) of the row player is a best response to a column players’ strategy \(\sigma_c\) if and only if:

### Proof¶

\((A\sigma_c^T)_i\) is the utility of the row player when they play their \(i^{\text{th}}\) action. Thus:

Let \(u=\max_{k}(A\sigma_c^T)_k\) giving:

We know that \(u - (A\sigma_c^T)_i\geq 0\), thus the largest \(\sigma_rA\sigma_c^T\) can be is \(u\) which occurs if and only if \({\sigma_r}_i > 0 \Rightarrow (A\sigma_c^T)_i = u\) as required.

Question

For the Rock Paper Scissors game:

Which of the following pairs of strategies are best responses to each other:

\(\sigma_r=(0, 0, 1) \text{ and } \sigma_c=(0, 1/2, 1/2)\)

\(\sigma_r=(1/3, 1/3, 1/3) \text{ and } \sigma_c=(0, 1/2, 1/2)\)

\(\sigma_r=(1/3, 1/3, 1/3) \text{ and } \sigma_c=(1/3, 1/3, 1/3)\)

Answer

Recalling that \(A\) and \(B\) are given by:

We can apply the best response condition to each pairs of strategies:

\(A\sigma_c^T = \begin{pmatrix}0\\ -1/2\\ 1/2\\\end{pmatrix}\). \(\text{max}(A\sigma_c^T)=1/2\). The only \(i\) for which \({\sigma_r}_i > 0\) is \(i=3\) and \((A\sigma_c^T)_3=\text{max}(A\sigma_c^T)\) thus \(\sigma_r\)

**is a best response to**\(\sigma_c\). \(\sigma_rB = (1, -1, 0)\). \(\text{max}(\sigma_rB)=1\). The values of \(i\) for which \({\sigma_c}_i > 0\) are \(i=2\) and \(i=3\) but \((\sigma_r B)_2 \ne \text{max}(\sigma_r B)\) thus \(\sigma_c\)**is not a best response to**\(\sigma_r\).\(A\sigma_c^T = \begin{pmatrix}0\\ -1/2\\ 1/2\\\end{pmatrix}\). \(\text{max}(A\sigma_c^T)=1/2\). The values of \(i\) for which \({\sigma_r}_i > 0\) are \(i=1\), \(i=2\) and \(i=3\) however, \((A\sigma_c^T)_2 \ne \text{max}(A\sigma_c^T)\) thus \(\sigma_r\)

**is not a best response to**\(\sigma_c\). \(\sigma_rB = (0, 0, 0)\). \(\text{max}(\sigma_rB)=0\). The values of \(i\) for which \({\sigma_c}_i > 0\) are \(i=2\) and \(i=3\) and \((\sigma_r B)_2 = (\sigma_r B)_3= \text{max}(\sigma_r B)\) thus \(\sigma_c\)**is a best response to**\(\sigma_r\).\(A\sigma_c^T = \begin{pmatrix}0\\ 0\\ 0\\\end{pmatrix}\). \(\text{max}(A\sigma_c^T)=0\). The values of \(i\) for which \({\sigma_r}_i > 0\) are \(i=1\), \(i=2\) and \(i=3\) and \((A\sigma_c^T)_1=(A\sigma_c^T)_2 = (A\sigma_c^T)_3 =\text{max}(A\sigma_c^T)\) thus \(\sigma_r\)

**is a best response to**\(\sigma_c\). \(\sigma_rB = (0, 0, 0)\). \(\text{max}(\sigma_rB)=0\). The values of \(i\) for which \({\sigma_c}_i > 0\) are \(i=1\), \(i=2\) and \(i=3\) and \((\sigma_r B)_1 =(\sigma_r B)_2 = (\sigma_r B)_3= \text{max}(\sigma_r B)\) thus \(\sigma_c\)**is a best response to**\(\sigma_r\).

## Definition of Nash equilibrium¶

In a two player game \((A, B)\in {\mathbb{R}^{m \times n}} ^ 2\), \((\sigma_r, \sigma_c)\) is a Nash equilibria if \(\sigma_r\) is a best response to \(\sigma_c\) and \(\sigma_c\) is a best response to \(\sigma_r\).

## Using Nashpy¶

See Check if a strategy is a best response for guidance of how to use Nashpy to check if a strategy is a best response.