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:

../_images/triangular_convex_hull.png

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

../_images/matching_pennies_row_best_response_polytope.png

\(\mathcal{Q}\):

../_images/matching_pennies_col_best_response_polytope.png

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.