# 05 Best response polytopes¶

## Corresponding chapters¶

Duration: 100 minutes

## Objectives¶

• Define the best response polytopes (using both definitions: convex hull and halfspaces).
• Labelling of vertices
• Equivalence between equilibrium and fully labeled pair
• Vertex enumeration

## Notes¶

### Defining best response polytopes¶

Discuss what an average is. Place this in the context of the line between two points. Weighted averages of two points are just a line. So an average is just a probability distribution. Expand this notion to the average over two points. How would you take the weighted average between three points $$x, y, z$$:

$\lambda_1 x + \lambda_2 y + \lambda_3 z$

This corresponds to something like:

Explain how another definition for that space would be to draw inequalities on our variables. Give definition of best response polytopes for a game. Illustrate this with the battle of the sexes game (scaled):

$\begin{split}A = \begin{pmatrix} 3 & 1\\ 0 & 2\\ \end{pmatrix} \qquad B = \begin{pmatrix} 2 & 1\\ 0 & 3\\ \end{pmatrix}\end{split}$

Go over the definition of the best response polytopes.

The row best response polytope is given by:

$\mathcal{P} = \left\{x\in\mathbb{R}^{m}\;|\;x\geq 0; xB\leq 1\right\}$

This corresponds to the following inequalities:

• $$x_1\geq 0$$
• $$x_2\geq 0$$
• $$2x_1\leq 1$$
• $$x_1+3x_2\leq 1$$

From this we can identify the vertices:

• $$(x_1, x_2)=(0,0)$$
• $$(x_1, x_2)=(1/2,0)$$
• $$(x_1, x_2)=(0,1/3)$$
• $$(x_1, x_2)=(1/2,1/6)$$

This can be confirmed using nashpy:

>>> import numpy as np
>>> import nashpy as nash
>>> B = np.array([[2, 1], [0, 3]])
>>> halfspaces = nash.polytope.build_halfspaces(B.transpose())
>>> for v, l in nash.polytope.non_trivial_vertices(halfspaces):
...     print(v)
[0.5 0. ]
[0.         0.333...]
[0.5        0.166...]


The column best response polytope is given by:

$\mathcal{Q} = \left\{y\in\mathbb{R}^{m}\;|\;Ay\leq 1; y\geq 0\right\}$

This corresponds to the following inequalities:

• $$3y_1+y_2\leq 1$$
• $$2y_2\leq 1$$
• $$y_1\geq 0$$
• $$y_2\geq 0$$

From this we can identify the vertices:

• $$(y_1, y_2)=(0,0)$$
• $$(y_1, y_2)=(1/3,0)$$
• $$(y_1, y_2)=(0,1/2)$$
• $$(y_1, y_2)=(1/6,1/2)$$

Confirmed:

>>> import numpy as np
>>> A = np.array([[3, 1], [0, 2]])
>>> halfspaces = nash.polytope.build_halfspaces(A)
>>> for v, l in nash.polytope.non_trivial_vertices(halfspaces):
...     print(v)
[0.333... 0.        ]
[0.  0.5]
[0.1666... 0.5       ]


### Pair activity¶

Ask everyone to draw these two polytopes.

Now describe how we label the vertices: using the same ordering as the inequalities (starting at 0), a vertex has the label corresponding to that inequality if it is a strict equality.

$$\mathcal{P}$$:

$$\mathcal{Q}$$:

Explain that what these polytopes represent is the scaled strategies when players maximum utilities are 1. So given, the action of an opponent, if the players’ utility is 1 they are playing a best response.

Ask each person in a pair to be the row or the column player.

Have the row player pick a vertex, then identify the strategy and it’s best response and then pick the corresponding vertex.

For example:

Row player picks $$(0, 1/3)$$ which has labels $$(0, 3)$$ and corresponds to the strategy $$(0, 1)$$. The best response to the second row is the first column which corresponds to vertex $$(0, 1/2)$$ which has labels $$(1, 2)$$.

Remind ourselves why these are the labels? (Refer to the defining properties of the polytopes).

Repeat with other vertices.

Aim to identify strategies that are best responses to each other:

• $$\sigma_r=(0, 1)$$ and $$\sigma_r=(0,1)$$
• $$\sigma_r=(3/4, 1/4)$$ and $$\sigma_r=(1/4,3/4)$$
• $$\sigma_r=(1, 0)$$ and $$\sigma_r=(1, 0)$$

Discuss how this relates to the labels again.

Finally show how this is implemented in nashpy:

>>> A = np.array([[1, -1], [-1, 1]])
>>> matching_pennies = nash.Game(A)
>>> for eq in matching_pennies.vertex_enumeration():
...     print(eq)
(array([0.5, 0.5]), array([0.5, 0.5]))


If there is time use support enumeration to compare.