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:

../_images/AA-dominated-strategy-polytope.png

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:

../_images/AA-row-player-strategy-polytope.png

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.]))]