# AA- Revisiting Polytopes¶

## Corresponding chapters¶

Duration: 50 minutes

## Objectives¶

• Re visit best response polytopes using a game with a dominated strategy.

## Notes¶

Consider the $$(A,B)\in{\mathbb{R}^{2\times 2}}^2$$ game:

$\begin{split}A = \begin{pmatrix} 1 & 4 \\ -3 & 2 \end{pmatrix} \qquad B = \begin{pmatrix} 5 & 2 \\ -1 & 9 \end{pmatrix}\end{split}$

Ask students in pairs to construct the column player best response polytope

First we add $$4$$ to all elements to ensure they are positive:

$\begin{split}A = \begin{pmatrix} 5 & 8 \\ 1 & 6 \end{pmatrix} \qquad B = \begin{pmatrix} 9 & 6 \\ 3 & 13 \end{pmatrix}\end{split}$

By definition (https://vknight.org/gt/chapters/06/#Definition-of-best-response-polytopes), the column player best response polytope $$\mathcal{Q}$$ is given by:

$\mathcal{Q} = \{y\in\mathbb{R}^{n}\;|\;Ay\leq 1\;y\geq0\}$

So the inequalities are:

\begin{split}\begin{align*} 5y_1+8y_2&\leq 1&&\text{ label: }0\\ y_1 + 6y_2&\leq 1&&\text{ label: }1\\ y_1&\geq 0&&\text{ label: }2\\ y_2&\geq 0&&\text{ label: }3 \end{align*}\end{split}

The first two inequalities come from $$Ay\leq 1$$, however, $$Ay$$ corresponds to the row players utility against vertex $$y$$.

Note that everything is scaled so that the best response of the row player is $$1$$ (the scaling takes place in the strategies/vertices).

Thus if a vertex has label $$0$$ or $$1$$ that implies that the first/second row player strategy is a best response to $$y$$.

We will return to this idea but first let us plot our $$Q$$. We start by rearranging our inequalities:

\begin{split}\begin{align*} y_2 &\leq 1/8 - 5/8y_1&&\text{ label: }0\\ y_2 &\leq 1/6 - y_1/6&&\text{ label: }1\\ y_1&\geq 0&&\text{ label: }2\\ y_2&\geq 0&&\text{ label: }3 \end{align*}\end{split}

Now let us sketch these:

import matplotlib.pyplot as plt
%matplotlib inline
y1s = [0, 1]
first_line = [1 / 8 - 5 / 8 * y for y in y1s]
second_line = [1 / 6 - y / 6 for y in y1s]
plt.figure()
plt.plot(first_line, label="$1/8-5/8y_1$ (label: 0)")
plt.plot(second_line, label="$1/6-y_1/6$ (label: 1)")
plt.legend();


This gives:

We can see that our polytope is a straightforward triangle and that no vertex will ever have label $$1$$.

Discuss if this is OK?

Returning to the game:

$\begin{split}A = \begin{pmatrix} \underline{5} & \underline{8} \\ 1 & 6 \end{pmatrix}\end{split}$

We see that the first strategy dominates the second: so the second strategy is never a best response.

Our vertices with labels are:

\begin{split}\begin{align*} (0, 0)&\text{ labels }\{2, 3\}\\ (0, 1/8)&\text{ labels }\{0, 2\}\\ (1/5, 0)&\text{ labels }\{0, 3\}\\ \end{align*}\end{split}

Exercise:

Obtain the best response polytope for the row player:

By definition (https://vknight.org/gt/chapters/06/#Definition-of-best-response-polytopes), the row player best response polytope $$\mathcal{P}$$ is given by:

$\mathcal{Q} = \{x\in\mathbb{R}^{m}\;|\;x\geq0\;xB\leq 1\}$

So the inequalities are:

\begin{split}\begin{align*} x_1&\geq 0&&\text{ label: }0\\ x_2&\geq 0&&\text{ label: }1\\ 9x_1+3x_2&\leq 1&&\text{ label: }2\\ 2x_1 + 9x_2&\leq 1&&\text{ label: }3 \end{align*}\end{split}

Rearranging:

\begin{split}\begin{align*} x_1&\geq 0&&\text{ label: }0\\ x_2&\geq 0&&\text{ label: }1\\ x_2&\leq 1/3 - 3 x_1&&\text{ label: }2\\ x_2&\leq 1/9 - 2/9x_1&&\text{ label: }3 \end{align*}\end{split}

Now let us sketch these:

x1s = [0, 1]
first_line = [1 / 3 - 3 * x for x in x1s]
second_line = [1 / 9 - 2 / 9 * x for x in x1s]
plt.figure()
plt.plot(first_line, label="$1/3-3x_1$ (label: 2)")
plt.plot(second_line, label="$1/9-2/9x_1/6$ (label: 3)")
plt.legend();


This gives:

We see that there our polytope has 4 vertices:

\begin{split}\begin{align*} (0, 0)&\text{ labels }\{0, 1\}\\ (0, 1/9)&\text{ labels }\{0, 3\}\\ (1/9, 0)&\text{ labels }\{1, 2\}\\ (2/25, 7/75)&\text{ labels }\{2, 3\}\\ \end{align*}\end{split}

Here is some sympy code to verify the intersection of both boundaries:

>>> import sympy as sym
>>> x = sym.Symbol("x")
>>> sym.solveset(sym.S(1) / 3-3 * x - sym.S(1) / 9 + sym.S(2) / 9 * x, x)
{2/25}


We can now identify a fully labelled vertex pair (we already know that label $$code$$ must come from a vertex in $$\mathcal{P}$$):

$((1/9, 0), (1/5, 0))$

Which once normalised gives: $$((1, 0),(0, 1))$$ which is in fact readily readable using pure best responses:

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

Checking using nashpy:

>>> import nashpy as nash
>>> A = [[1, 4], [-3, 2]]
>>> B = [[5, 2], [-1, 9]]
>>> game = nash.Game(A, B)
>>> list(game.vertex_enumeration())
[(array([1., 0.]), array([1., 0.]))]