Best response polytopes - solutions

Define a polytope as a convex hull

Bookwork: https://vknight.org/gt/chapters/06/#Definition-of-a-Polytope-as-a-convex-hull
Define a polytope as an intersection of halfspaces

Bookwork: https://vknight.org/gt/chapters/06/#Definition-of-a-Polytope-as-an-intersection-of-halfspaces
For the following set of vertices draw the corresponding polytope and obtain their definition as an intersection of halfspaces:

A. V = $\{(0, 0), (0, 1), (1, 0), (1, 1)\}$



In [1]:

    
%matplotlib inline

import matplotlib.pyplot as plt
import numpy as np
import scipy.spatial

V = [np.array([0, 0]), np.array([0, 1]), np.array([1, 0]), np.array([1, 1])]
P = scipy.spatial.ConvexHull(V)
scipy.spatial.convex_hull_plot_2d(P);

The definition as an intersection of halfspaces:

$$ \begin{align} - x_1 & \leq 0\\ -x_2 & \leq 0\\ x_1 & \leq 1\\ x_2 & \leq 1 \end{align} $$

B. V = $\{(0, 0), (0, 1/4), (1, 2/3), (2, 1/5)\}$



In [2]:

    
V = [np.array([0, 0]), np.array([0, 1 / 4]), np.array([1, 2  / 3]), np.array([2, 1 / 5])]
P = scipy.spatial.ConvexHull(V)
scipy.spatial.convex_hull_plot_2d(P);

Let us first find the equations for each boundary:

Between $(0, 0)$ and $(0, 1/4)$: $x_1=0$
Between $(0, 1/4)$ and $(1, 2/3)$: $x_2=(5/12)x_1+1/4$
Between $(1, 2/3)$ and $(2, 1/5)$: $x_2=(-7/15)x_1+17/15$
Between $(2, 1/5)$ and $(0, 0)$: $x_2=(1/10)x_1$

The definition as an intersection of halfspaces (obtained by identifying the lines corresponding to each boundary of the polytope):

$$ \begin{align} -x_1 & \leq 0\\ 12x_2 - 5x_1 & \leq 3\\ 15x_2 + 7x_1 & \leq 17\\ x_1 -10x_2 & \leq 0 \end{align} $$

C. V = $\{(0, 0), (0, 1/4), (1, 2/3), (2, 1/5), (1, 0)\}$



In [3]:

    
V = [np.array([0, 0]), np.array([0, 1 / 4]), np.array([1, 2  / 3]), np.array([2, 1 / 5]), np.array([1, 0])]
P = scipy.spatial.ConvexHull(V)
scipy.spatial.convex_hull_plot_2d(P);

Let us first find the equations for each boundary:

Between $(0, 0)$ and $(0, 1/4)$: $x_1=0$
Between $(0, 1/4)$ and $(1, 2/3)$: $x_2=(5/12)x_1+1/4$
Between $(1, 2/3)$ and $(2, 1/5)$: $x_2=(-7/15)x_1+17/15$
Between $(2, 1/5)$ and $(1, 0)$: $x_2=(1/5)x_1-1/5$
Between $(1, 0)$ and $(0, 0)$: $x_2=0$

The definition as an intersection of halfspaces (obtained by identifying the lines corresponding to each boundary of the polytope):

$$ \begin{align} -x_1 & \leq 0\\ 12x_2 - 5x_1 & \leq 3\\ 15x_2 + 7x_1 & \leq 17\\ x_1 - 5 x_2 & \leq 1\\ -x_2 & \leq 0 \end{align} $$

4. Define the best response polytopes.

Bookwork: https://vknight.org/gt/chapters/06/#Definition-of-best-response-polytopes

5. For the following games, obtain the best response polytopes, label the vertices and identify all Nash equilibria:

$ A = \begin{pmatrix} 3 & -1\\ 2 & 7\end{pmatrix} \qquad B = \begin{pmatrix} -3 & 1\\ 1 & -6\end{pmatrix} $

First we need nonegative valued matrices:

$$ A \to A + 2 = \begin{pmatrix} 5 & 1\\ 4 & 9\end{pmatrix} \qquad B \to B + 7 = \begin{pmatrix} 4 & 8\\ 8 & 1\end{pmatrix} $$

The inequalities of $\mathcal{P}$ are then given by:

$$ \begin{align} -x_1 & \leq 0\\ -x_2 & \leq 0\\ 4x_1 + 8x_2 & \leq 1\\ 8x_1 + 1x_2 & \leq 1\ \end{align} $$

which corresponds to:

$$ \begin{align} x_1 & \geq 0\\ x_2 & \geq 0\\ x_2 & \leq 1/8 - (1/2)x_1\\ x_2 & \leq 1 - 8x_1 \end{align} $$

The vertices are given by:

$$V=\{(0, 0), (0, 1/8), (1/8, 0), (7/60, 1/15)\}$$

The labels of our vertices (using the ordering of the inequalities):

$(0, 0)$: $\{0, 1\}$
$(0, 1/8)$: $\{0, 2\}$
$(1/8, 0)$: $\{1, 3\}$
$(7/60, 1/15)$: $\{2, 3\}$

The inequalities of $\mathcal{Q}$ are given by:

$$ \begin{align} 5x_1 + x_2 & \leq 1\\ 4x_1 + 9x_2 & \leq 1\\ -x_1 & \leq 0\\ -x_2 & \leq 0 \end{align} $$

which corresponds to:

$$ \begin{align} x_2 & \leq 1 - 5x_1\\ x_2 & \leq 1/9 - (4/9)x_1\\ x_1 & \geq 0\\ x_2 & \geq 0 \end{align} $$

The vertices are given by:

$$V=\{(0, 0), (0, 1/9), (1/5, 0), (8/41, 1/41)\}$$

The labels of our vertices (using the ordering of the inequalities):
- $(0, 0)$: $\{2, 3\}$
- $(0, 1/9)$: $\{1, 2\}$
- $(1/5, 0)$: $\{0, 3\}$
- $(8/41, 1/41)$: $\{0, 1\}$
The only fully labeled vertex pair is given by:

$$((7/60, 1/15), (8/41, 1/41))$$

which gives the normalised Nash equilibrium:

$$((7/11, 4/11), (8/9, 1/9))$$

Here is some code to verify this numerically:



In [4]:

    
import nashpy as nash
# Obtaining the row player best response polytope vertices
B = np.array([[4, 8], [8, 1]])
halfspaces = nash.polytope.build_halfspaces(B.transpose())
for v, l in nash.polytope.non_trivial_vertices(halfspaces):
    print(v)









    



[0.125 0.   ]
[0.    0.125]
[0.11666667 0.06666667]



In [5]:

    
# Obtaining the column player best response polytope vertices
A = np.array([[5, 1], [4, 9]])
halfspaces = nash.polytope.build_halfspaces(A)
for v, l in nash.polytope.non_trivial_vertices(halfspaces):
    print(v)









    



[6.93889390e-18 1.11111111e-01]
[0.19512195 0.02439024]
[ 2.0000000e-01 -6.9388939e-18]



In [6]:

    
# Verifying the Nash equilibria:
A = A - 2  # Scaling back down (note this makes no difference)
B = B - 7 
game = nash.Game(A, B)
list(game.vertex_enumeration()), (7/11, 4/11), (8/9, 1/9)









    Out[6]:





([(array([0.63636364, 0.36363636]), array([0.88888889, 0.11111111]))],
 (0.6363636363636364, 0.36363636363636365),
 (0.8888888888888888, 0.1111111111111111))

2. $ A = \begin{pmatrix} 2 & -1\\ 1 & 3\end{pmatrix} \qquad B = \begin{pmatrix} -2 & 2\\ 1 & -2\end{pmatrix} $

First we need nonegative valued matrices:

$$ A \to A + 2 = \begin{pmatrix} 4 & 1\\ 3 & 5\end{pmatrix} \qquad B \to B + 3 = \begin{pmatrix} 1 & 5\\ 4 & 1\end{pmatrix} $$

The inequalities of $\mathcal{P}$ are then given by:

$$ \begin{align} -x_1 & \leq 0\\ -x_2 & \leq 0\\ x_1 + 4x_2 & \leq 1\\ 5x_1 + x_2 & \leq 1\ \end{align} $$

which corresponds to:

$$ \begin{align} x_1 & \geq 0\\ x_2 & \geq 0\\ x_2 & \leq 1/4 - (1/4)x_1\\ x_2 & \leq 1 - 5x_1 \end{align} $$

The vertices are given by:

$$V=\{(0, 0), (0, 1/4), (1/5, 0), (3/19, 4/19)\}$$

The labels of our vertices (using the ordering of the inequalities):

$(0, 0)$: $\{0, 1\}$
$(0, 1/4)$: $\{0, 2\}$
$(1/5, 0)$: $\{1, 3\}$
$(3/19, 4/19)$: $\{2, 3\}$

The inequalities of $\mathcal{Q}$ are given by:

$$ \begin{align} 4x_1 + x_2 & \leq 1\\ 3x_1 + 5x_2 & \leq 1\\ -x_1 & \leq 0\\ -x_2 & \leq 0 \end{align} $$

which corresponds to:

$$ \begin{align} x_2 & \leq 1 - 4x_1\\ x_2 & \leq 1/5 - (3/5)x_1\\ x_1 & \geq 0\\ x_2 & \geq 0 \end{align} $$

The vertices are given by:

$$V=\{(0, 0), (0, 1/5), (1/4, 0), (4/17, 1/17)\}$$

The labels of our vertices (using the ordering of the inequalities):

$(0, 0)$: $\{2, 3\}$
$(0, 1/5)$: $\{1, 2\}$
$(1/4, 0)$: $\{0, 3\}$
$(4/17, 1/17)$: $\{0, 1\}$

The only fully labeled vertex pair is given by:

$$((3/19, 4/19), (4/17, 1/17))$$

which gives the normalised Nash equilibrium:

$$((3/7, 4/7), (4/5, 1/5))$$

Here is some code to verify this numerically:



In [7]:

    
# Obtaining the row player best response polytope vertices
B = np.array([[1, 5], [4, 1]])
halfspaces = nash.polytope.build_halfspaces(B.transpose())
for v, l in nash.polytope.non_trivial_vertices(halfspaces):
    print(v)









    



[0.2 0. ]
[0.   0.25]
[0.15789474 0.21052632]



In [8]:

    
# Obtaining the column player best response polytope vertices
A = np.array([[4, 1], [3, 5]])
halfspaces = nash.polytope.build_halfspaces(A)
for v, l in nash.polytope.non_trivial_vertices(halfspaces):
    print(v)









    



[0.  0.2]
[0.23529412 0.05882353]
[2.50000000e-01 1.38777878e-17]



In [9]:

    
# Verifying the Nash equilibria:
A = A - 2  # Scaling back down (note this makes no difference)
B = B - 3 
game = nash.Game(A, B)
list(game.vertex_enumeration()), (3 / 7, 4 / 7), (4 / 5, 1 / 5)









    Out[9]:





([(array([0.42857143, 0.57142857]), array([0.8, 0.2]))],
 (0.42857142857142855, 0.5714285714285714),
 (0.8, 0.2))