# Mock exam 2018 - solutions¶

## Question 1¶

### (a) definition of a Normal form game:¶

An $N$ player normal form game consists of:

• A finite set of $N$ players
• Strategy spaces for the players: $\{S_1,S_2,S_3,\dots,S_N\}$;
• Payoff functions for the players: $u_i:S_1\times S_2\dots\times S_N\to\mathbb{R}$



### (b) Identifying best responses¶

We have:

• $u_r((1, 0), (y, 1-y))= y - 2 (1 - y)=3y-2$ and $u_r((0, 1), (y, 1-y))= -2y + (1 - y)=1-3y$
• $u_c((x, 1 - x), (1, 0))=-2x+(1-x)=1-3x$ and $u_c((x, 1- x), (0, 1))=x-2(1-x)=3x-2$
In :
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline
plt.figure()
ys = [0, 1]
plt.plot(ys, [3 * y - 2 for y in ys], label="$u_r((1, 0), (y, 1-y))$")
plt.plot(ys, [1 - 3 * y for y in ys], label="$u_r((0, 1), (y, 1-y))$")
plt.legend()
plt.xlabel("$y$")
plt.title("Utility to row player"); In :
plt.figure()
xs = [0, 1]
plt.plot(xs, [1 - x * 3 for x in xs], label="$u_c((x, 1 - x), (1, 0))$")
plt.plot(xs, [3 * x - 2 for x in xs], label="$u_c((x, 1 - x), (0, 1))$")
plt.legend()
plt.xlabel("$x$")
plt.title("Utility to column player"); The best responses are then given by:

$$\sigma_r^* = \begin{cases} (0,1)&\text{ if }y< 1/2\\ (1,0)&\text{ if }y> 1/2\\ \text{indifferent}&\text{ otherwise} \end{cases}$$$$\sigma_c^* = \begin{cases} (1,0)&\text{ if }x< 1/2\\ (0,1)&\text{ if }x> 1/2\\ \text{indifferent}&\text{ otherwise} \end{cases}$$



### (c) Proof of best response condition¶

$(A\sigma_c^T)_i$ is the utility of the row player when they play their $i$th strategy. Thus:

$$\sigma_rA\sigma_c^T=\sum_{i=1}^{m}{\sigma_r}_i(A\sigma_c^T)_i$$



Let $u=\max_{k}(A\sigma_c^T)_k$. Thus:

\begin{aligned} \sigma_rA\sigma_c^T&=\sum_{i=1}^{m}{\sigma_r}_i(u - u + (A\sigma_c^T)_i)\\ &=\sum_{i=1}^{m}{\sigma_r}_iu - \sum_{i=1}^{m}{\sigma_r}_i(u - (A\sigma_c^T)_i)\\ &=u - \sum_{i=1}^{m}{\sigma_r}_i(u - (A\sigma_c^T)_i) \end{aligned}



We know that $u - (A\sigma_c^T)_i\geq 0$, thus the largest $\sigma_rA\sigma_c^T$ can be is $u$ which occurs iff ${\sigma_r}_i > 0 \Rightarrow (A\sigma_c^T)_i = u$ as required.



### (d) Finding the Nash equilibrium¶

There are no pairs of pure strategies that are best response to each other (visibile from the payoff matrices). We consider mixed strategies $\sigma_r=(x, 1- x)$ and $\sigma_c=(y, 1-y)$ 

For $\sigma_r$ to be a best response to $\sigma_c$, from the theorem we have:

$$u_r((1, 0), \sigma_c)=u_r((1, 0), \sigma_c)\Rightarrow 3y-2=1-3y\Rightarrow y=1/2$$$$u_c(\sigma_r, (1, 0))=u_c(\sigma_r, (0, 1))\Rightarrow 1-3x=3x-2\Rightarrow x=1/2$$



The Nash equilibrium is $((1/2, 1/2), (1/2, 1/2))$.

This is confirmed by the best response findings of question (b): these two strategies are best responses to each other. 

### (e) Discussing the Knight et al. 2017 paper¶

• (i): This paper builds a Markov queueing model based on strategic interactions between two hospitals . It measures the Price of Anarchy to see the effect on patients of rational behaviour . It does all this by comparing the Nash equilibrium to the optimal behaviour .
• (ii): The main theoretic result is concerning the behaviour of the best response functions.  The paper proves that they are increasing functions which ensures there is a single point of intersection. 
• (iii): Various possibilities each worth :
• A stationary queueing model whilst in practice a time dependent model would be more appropriate.
• Only considering interaction between two hospitals.
• Just a single cutoff strategy.
• (iv): Depending on the choice of limiting factor :
• Use a non stationary queueing model, potentially simulating the queueing process in a time dependent way.
• Consider a multi player game although this becomes harder to generalise the theoretic result.
• Use multiple cutoff strategies (this would be the simplest approach).

## Question 2¶

### (a) Definition of repeated game¶

Given a two player game $(A,B)\in{\mathbb{R}^{m\times n}}^2$, referred to as a stage game, a $T$-stage repeated game is a game in which players play that stage game for $T > 0$ periods. Players make decisions based on the full history of play over all the periods.



### (b) Definition of a strategy in a repeated game¶

Given a two player stage game $(A,B)\in{\mathbb{R}^{m\times n}}^2$, repeated to give a $T$-stage repeated game. A strategy is a mapping from the entire history of play to an action of the stage game:

$$\bigcup_{t=0}^{T-1}H(t)\to a$$

where:

• $H(t)$ is the history of player of both players up until stage $t$ ($H(0)=(\emptyset, \emptyset)$)
• $a$ is an action (for either player) of the stage game



### (c) Size of history space¶

For a given integer value of $0\leq t< T$ there are $|S_1|^t$ possible histories for player 1 and $|S_2|^t$ possible histories for player 2. Thus the total number of histories is: 

$$\sum_{t=0}^{T - 1}|S_1|^t|S_2|^t$$



which gives:

$$\sum_{t=0}^{T - 1}|S_1|^t|S_2|^t=\sum_{t=0}^{T - 1}(|S_1||S_2|)^t=\frac{1 - (|S_1||S_2|)^T}{1 - |S_1||S_2|}$$



### (d) Listing strategy spaces¶

$S_1\{r_1, r_2\}$, $S_2=\{c_1, c_2, c_3\}$ and $T=2$

$$\{(\emptyset, \emptyset), (r_1, c_1), (r_1, c_2), (r_1, c_3), (r_2, c_1), (r_2, c_2), (r_2, c_3)\}$$



### (e) Sequence of stage Nash theorem¶

Consider the following strategy:

The row/column player should play action $a_{r/c}$ regardless of the play of any previous strategy profiles. 

where $(a_{r}, a_{c})$ is a given stage Nash equilibrium.

Using backwards induction, this is a Nash equilibrium for the last stage game. Thus, at the last stage, no player has a reason to deviate. Similarly at the $T-1$th stage. The proof follows.



### (f) Pure Nash equilibria¶

The pure Nash equilibria:

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

Thus, for our example we have the four Nash equilibria:

• $(r_1r_1, c_2c_2)$ with utility: (12, 14). 
• $(r_1r_1, c_2c_3)$ with utility: (7, 14). 
• $(r_1r_1, c_3c_2)$ with utility: (7, 14). 
• $(r_1r_1, c_3c_3)$ with utility: (2, 14). 

### (g) Note state Nash, equilibria¶

Consider the following two strategies:

1. For the row player:

$$(\emptyset, \emptyset) \to r_2$$ $$(r_2, c_1) \to r_1$$ $$(r_2, c_2) \to r_1$$ $$(r_2, c_3) \to r_1$$



2. For the column player:

$$(\emptyset, \emptyset) \to c_1$$ $$(r_1, c_1) \to c_3$$ $$(r_2, c_1) \to c_2$$



This is a Nash equilibria because:

1. If the row player deviates, they would only be rational to do so in the first stage, if they did they would gain 2 in that stage but lose 5 in the second stage. Thus they have no incentive to deviate.
2. If the column player deviates, they would only do so in the first stage and gain no utility.



## Question 3¶

### (a) Defining the row/col best response polytopes¶

For a two player game $(A, B)\in{\mathbb{R}^{m\times n}_{>0}}^2$ the row/column player best response polytope $\mathcal{P}$/$\mathcal{Q}$ is defined by:



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



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



### (b) Degeneracy of the game¶

The column player has two best responses to the first row thus the game is degenerate. 

### (c) Obtain half space definitions:¶

Directly apply the definition: 

Note that any modifications of $A, B$ are accepted (so as to make them $>0$).

For $\mathcal{P}$ :

\begin{aligned} x_1 &\geq 0\\ x_2 &\geq 0\\ 20x_2 & \leq 1\\ 7 x_1 + x_2 & \leq 1\\ 7 x_1& \leq 1\\ \end{aligned}



For $\mathcal{Q}$ :

\begin{aligned} 3y_1 +6y_2 + y_3 & \leq 1\\ y_1 +2y_2 & \leq 1\\ y_1 &\geq 0\\ y_2 &\geq 0\\ y_3 &\geq 0\\ \end{aligned}



### (d) Confirming labelling:¶

There are an infinite number of possible vertices (based on potential modifications of $A, B$). Thus it makes sense to consider the strategies that correspond to the normalised vertices given (recall the question is not asking to find the vertices):

For $\mathcal{P}$:

• $x=(0, 0)\text{ with labels: }\{0, 1\}$: $x_1=0$ and $x_2=0$
• $x=(1/7, 0)\rightarrow \sigma_r=(1, 0)\text{ with labels: }\{1, 3, 4\}$. Label $1$ because $x_2=0$. Labels $\{3, 4\}$ because the 2nd and 3rd columns are best responses.
• $x=(0, 1/20)\rightarrow \sigma_r=(0, 1)\text{ with labels: }\{0, 2\}$: Label $0$ because $x_1=0$. Label $2$ because the first column is a best response.
• $x=(19/140, 1/20)\rightarrow \sigma_r=(19/26, 7/26)\text{ with labels: }\{2, 3\}$: we have $\sigma_r B = (70/13, 70/13, 133/26)$ thus columns 1 and 2 are best responses.



For $\mathcal{Q}$:

• $y=(0, 0, 0)\text{ with labels: }\{2, 3, 4\}$: $y_1=0$, $y_2=0$ and $y_3=0$
• $y=(0, 0, 1)\rightarrow \sigma_c=(0, 0, 1)\text{ with labels: }\{0, 2, 3\}$: 2, 3 is immediate, 0 because best response to 3rd column is first row.
• $y=(0, 1/6, 0)\rightarrow \sigma_c=(0, 1, 0)\text{ with labels: }\{0, 2, 4\}$: 2, 4 is immediate, 0 because best response to 2nd column is first row.
• $y=(1/3, 0, 0)\rightarrow \sigma_c=(1, 0, 0)\text{ with labels: }\{0, 3, 4\}$: 3, 4 is immediate, 0 because best response to 1st column is first row.



In :
import nashpy as nash

A = np.array([[3, 6, 1],
[1, 2, 0]])
B = np.array([[0, 7, 7],
[20, 1, 0]])

row_halfspaces = nash.polytope.build_halfspaces(B.transpose())
for vertex, labels in nash.polytope.non_trivial_vertices(row_halfspaces):
print(np.round(vertex / sum(vertex), 4))

[1. 0.]
[0. 1.]
[0.7308 0.2692]

In :
col_halfspaces = nash.polytope.build_halfspaces(A)
for vertex, labels in nash.polytope.non_trivial_vertices(col_halfspaces):
print(np.round(vertex / sum(vertex), 4))

[0. 0. 1.]
[0. 1. 0.]
[1. 0. 0.]


### (e) The vertex enumeration algorithm¶

For a nondegenerate 2 player game $(A, B)\in{\mathbb{R}^{m\times n}_{>0}}^2$ the following algorithm returns all nash equilibria:

1. For all pairs of vertices of the best response polytopes
2. Check if the vertices have full labels
3. Return the normalised probabilities



### (f) Use the vertex enumeration algorithm¶

The only vertex pairs with a full set of labels:

• $x=(1/7, 0)\text{ with labels: }\{1, 3, 4\}$ and $y=(0, 0, 1)\text{ with labels: }\{0, 2, 3\}$ 
• $x=(1/7, 0)\text{ with labels: }\{1, 3, 4\}$ and $y=(0, 1/6, 0)\text{ with labels: }\{0, 2, 4\}$ 

This corresponds to:

$$\{((1, 0), (0, 0, 1)), ((1, 0), (0, 1, 0))\}$$



In :
game = nash.Game(A, B)
for eq in game.vertex_enumeration():
print([np.round(s, 2) for s in eq])

[array([1., 0.]), array([0., 0., 1.])]
[array([1., 0.]), array([0., 1., 0.])]


### (g) The L-H Algorithm¶

For a nondegenerate 2 player game $(A, B)\in{\mathbb{R}^{m\times n}_{>0}}^2$ the following algorithm returns a nash equilibria:

1. Start at the artificial equilibrium: $(0, 0)$
2. Choose a label to drop.
3. Remove this label from the corresponding vertex by traversing an edge of the corresponding polytope to another vertex.
4. The new vertex will now have a duplicate label in the other polytope. Remove this label from the vertex of the other polytope and traverse an edge of that polytope to another vertex.
5. Repeat step 4 until the pair of vertices is fully labelled.

### (h) Using the L-H Algorithm¶

Note that the game is degenerate but that we can still attempt to use the algorithm:

• $((0, 0), (0, 0, 0))$ have labels: $\{0, 1\}, \{2, 3, 4\}$. Drop 0 (arbitrary decision) in $\mathcal{P}$. 
• $\to ((1/7, 0), (0, 0, 0))$ have labels: $\{1, 3, 4\}, \{2, 3, 4\}$. In $\mathcal{Q}$ drop 3 (arbitrary decision, could have dropped 4). 
• $\to ((1/7, 0), (0, 1/6, 0))$ have labels: $\{1, 3, 4\}, \{0, 2, 4\}$. 

We have a fully labelled vertex pair (and one of the same equilibria as before).

There are numerous possible implimentations of this algorithm, here is another:

• $((0, 0), (0, 0, 0))$ have labels: $\{0, 1\}, \{2, 3, 4\}$. Drop 2 (arbitrary decision) in $\mathcal{Q}$.
• $\to ((0, 0), (1/3, 0, 0))$ have labels: $\{0, 1\}, \{0, 3, 4\}$. In $\mathcal{P}$ drop 0.
• $\to ((1/7, 0), (1/3, 0, 0))$ have labels: $\{1, 3, 4\}, \{0, 3, 4\}$. In $\mathcal{Q}$ drop 4 (arbitrary decision, could have dropped 3).
• $\to ((1/7, 0), (0, 0, 1))$ have labels $\{1, 3, 4\}, \{0, 2, 3\}$

We have a fully labelled vertex pair (and one of the same equilibria as before).

## Question 4¶

### (a) Definition of a Moran process on a game¶

Consider a matrix $A\in\mathbb{R}^{m\times n}$ representing a game with two strategies.

$$A= \begin{pmatrix} a & b\\ c & d \end{pmatrix}$$

The Moran process is as follows:

• At a given time step: all individuals play all other individuals.
• Obtain their fitness as given by the game.
• Randomly select an individual proportional to their fitness as an individual to be reproduced
• Uniformly select an individual to be replaced
• Proceed to the next time step.
• The process terminates when there is only one type of individual in the population.



### (b) Theorem¶

Given a birth death process, the fixation probability $x_i$ is given by:

$$x_i=\frac{1+\sum_{j=1}^{i-1}\prod_{k=1}^j\gamma_k}{1+\sum_{j=1}^{N-1}\prod_{k=1}^j\gamma_k}$$

where:

$$\gamma_k = \frac{p_{k,k-1}}{p_{k,k+1}}$$



The Moran process is a birth death process where the transition probabilities are then given by:

$$p_{i,i+1}=\frac{if_{1i}}{if_{1i} + (N-i)f_{2i}}\frac{N-i}{N}$$$$p_{i,i-1}=\frac{(N-i)f_{2i}}{if_{1i} + (N-i)f_{2i}}\frac{i}{N}$$



which gives:

$$\gamma_i=\frac{f_{2i}}{f_{1i}}$$



thus (using the general birth death process result):

$$x_i=\frac{1+\sum_{j=1}^{i-1}\prod_{k=1}^j\frac{f_{2k}}{f_{1k}}}{1+\sum_{j=1}^{N-1}\prod_{k=1}^j\frac{f_{2k}}{f_{1k}}}$$



### (c) Moran process for the game¶

Assuming $i$ individuals of the first type, for this game we have $N=3$ and $(a, b, c, d)=(0, 2, r, 0)$ the fitness of both types is given respectively by:

$$f_{1i}=\frac{a(i-1)+b(N-i)}{N-1}=\frac{6-2i}{2}=3-i$$$$f_{2i}=\frac{c(i)+d(N-i-1)}{N-1}=\frac{ri}{2}=\frac{ri}{2}$$

which gives:

$$\gamma_i=\frac{f_{2i}}{f_{1i}}=\frac{ri}{6-2i}$$

thus:

$$x_1=\frac{1}{1+\sum_{j=1}^{2}\prod_{k=1}^j\frac{rk}{6-2k}}=\frac{1}{1 + \frac{r}{4} + \frac{r}{4}\frac{2r}{2}}=\frac{1}{\frac{r^{2}}{4} + \frac{r}{4} + 1}$$

for $r=2$ we get:

$$x_1 = 2 / 5$$

Some code to verify the result:

In :
def theoretic_fixation(N, game, i=1):
"""
Calculate x_i as given by the above formula
"""
f_ones = np.array([(game[0, 0] * (i - 1) + game[0, 1] * (N - i)) / (N - 1) for i in range(1, N)])
f_twos = np.array([(game[1, 0] * i + game[1, 1] * (N - i - 1)) / (N - 1) for i in range(1, N)])
gammas = f_twos / f_ones
return (1 + np.sum(np.cumprod(gammas[:i-1]))) / (1 + np.sum(np.cumprod(gammas)))

In :
import sympy as sym
import numpy as np
r = sym.symbols("r")
game = np.array([[sym.S(0), sym.S(2)], [sym.S(r), sym.S(0)]])
x_1 = theoretic_fixation(N=3, game=game)
x_1, x_1.subs({r: 2})

Out:
(1/(r**2/4 + r/4 + 1), 2/5)

### (d) Finding an $r$¶

Finding $r$ such that $x_1>.9$ corresponds to:

$$\frac{1}{\frac{r^{2}}{4} + \frac{r}{4} + 1}>9/10$$

which corresponds to:

\begin{aligned} \left(\frac{r^{2}}{4} + \frac{r}{4} + 1\right)9/10 & < 1 &&\text{}\\ \left(\frac{r^{2}}{4} + \frac{r}{4} + 1\right) & < 10/9 && \text{}\\ \frac{r^{2}}{4} + \frac{r}{4} - \frac{1}{9}& < 0 && \text{} \\ r ^ 2 + r - \frac{4}{9}& < 0 && \text{} \\ \end{aligned}

The roots of this polynomial are $-4/3, 1/3$ , thus: $r<1/3$ ensures $x_1>9/10$. 

To ensure a high probability of fixation we need the fitness of an individual of the second type encountering an individual of the first type to be at most $1/3$. 

In :
sym.solveset(r ** 2 + r  - sym.S(4) / 9, r)

Out:
{-4/3, 1/3}
Previous

Next