03 Best responses and Nash equilibrium¶

Corresponding chapters¶

Duration: 100 minutes

Objectives¶

• Define best responses
• Identify best responses in pure strategies
• Identify best responses against mixed strategies
• Theorem: best response condition
• Definition of Nash equilibria

Notes¶

Discuss best response in pure strategies.

Best response against mixed strategies¶

Use best responses against mixed strategies have students play against a mixed strategy:

>>> import random
>>> random.seed(0)  # Don't seed in class
>>> ["D", "C"][random.random() < 0.3]  # 30 chance of Cooperating
'D'


Discuss the definition of a best response. Identify best responses for the game considered:

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

Consider the best responses against a mixed strategy:

• Assume $$\sigma_r=(x, 1-x)$$
• Assume $$\sigma_c=(y, 1-y)$$

We have:

$\begin{split}A\sigma_c^T = \begin{pmatrix} 4y-2\\ 1-2y \end{pmatrix}\qquad \sigma_rB = \begin{pmatrix} 1-3x & 3x-1 \end{pmatrix}\end{split}$

Here is the code to do this calculation with sympy:

>>> import sympy as sym
>>> import numpy as np
>>> x, y = sym.symbols('x, y')
>>> A = sym.Matrix([[2, -2], [-1, 1]])
>>> B = - A
>>> sigma_r = sym.Matrix([[x, 1-x]])
>>> sigma_c = sym.Matrix([y, 1-y])
>>> A * sigma_c, sigma_r * B
(Matrix([
[ 4*y - 2],
[-2*y + 1]]), Matrix([[-3*x + 1, 3*x - 1]]))


Plot these two things:

>>> import matplotlib.pyplot as plt
>>> ys = [0, 1]
>>> row_us = [[(A * sigma_c)[i].subs({y: val}) for val in ys] for i in range(2)]
>>> plt.plot(ys, row_us[0], label="$(A\sigma_c^T)_1$")
[<matplotlib...>]
>>> plt.plot(ys, row_us[1], label="$(A\sigma_c^T)_2$")
[<matplotlib...>]
>>> plt.xlabel("$\sigma_c=(y, 1-y)$")
>>> plt.title("Utility to player 1")
>>> plt.legend();

>>> xs = [0, 1]
>>> row_us = [[(sigma_r * B)[j].subs({x: val}) for val in xs] for j in range(2)]
>>> plt.plot(ys, row_us[0], label="$(\sigma_rB)_1$")
[<matplotlib...>]
>>> plt.plot(ys, row_us[1], label="$(\sigma_rB)_2$")
[<matplotlib...>]
>>> plt.xlabel("$\sigma_r=(x, 1-x)$")
>>> plt.title("Utility to column player")
>>> plt.legend();


Conclude:

$\begin{split}\sigma_r^* = \begin{cases} (1, 0),&\text{ if } y > 1/2\\ (0, 1),&\text{ if } y < 1/2\\ \text{indifferent},&\text{ if } y = 1/2 \end{cases} \qquad \sigma_c^* = \begin{cases} (0, 1),&\text{ if } x > 1/3\\ (1, 0),&\text{ if } x < 1/3\\ \text{indifferent},&\text{ if } x = 1/3 \end{cases}\end{split}$

Some examples:

• If $$\sigma_r=(2/3, 1/3)$$ then $$\sigma_c^*=(0, 1)$$.
• If $$\sigma_r=(1/3, 2/3)$$ then any strategy is a best response.

Discuss best response condition theorem and proof.

This gives a finite condition that needs to be checked. To find the best response against $$\sigma_c$$ we potentially would need to check all infinite possibilities alternatives to $$\sigma_r^*$$. Now we simply need to check the values of the pure strategies against $$\sigma_c$$:

• Either there will be a single pure best response;
• There will be multiple pure strategies for which the row player is indifferent.

Return to previous example:if $$\sigma_r=(1/3, 2/3)$$ then $$(\sigma_rB)=(0, 0)$$ thus $$(\sigma_rB)_j = 0$$ for all $$j$$.

$$(\sigma_r, \sigma_c) = ((1/3, 1/2), (1/2, 1/2))$$ is a pair of best responses.

Discuss definition of Nash equilibria.

Explain how the best response condition theorem can be used to find NE.

• All possible supports (strategies that are played with positive probabilities) can be checked.
• All pure strategies must have maximum and equal payoff.