# Repeated games - solutions¶

1. Define a repeated game.

2. Define a strategy for a repeated game.

3. Write the full potential history $\bigcup_{t=0}^{T-1}H(t)$ for repeated games with $T$ periods in the following cases:

1. $S_1=S_2=\{0, 1\}$ and $T=2$

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

2. $S_1=\{r_1, r_2\}\;S_2=\{c_1, c_2\}$ and $T=3$

$$\{(\emptyset, \emptyset), (r_1, c_1), (r_1, c_2), (r_2, c_1), (r_2, c_2),\\ (r_1r_1, c_1c_1), (r_1r_1, c_1c_2), (r_1r_2, c_1c_1), (r_1r_2, c_1c_2),\\(r_1r_1, c_2c_1), (r_1r_1, c_2c_2), (r_1r_2, c_2c_1), (r_1r_2, c_2c_2),\\(r_2r_1, c_1c_1), (r_2r_1, c_1c_2), (r_2r_2, c_1c_1), (r_2r_2, c_1c_2),\\(r_2r_1, c_2c_1), (r_2r_1, c_2c_2), (r_2r_2, c_2c_1), (r_2r_2, c_2c_2)\}$$

4. Obtain a formula for $\left|\bigcup_{t=0}^{T-1}H(t)\right|$ in terms of $S_1, S_2$ and $T$.

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=\sum_{t=0}^{T - 1}(|S_1||S_2|)^t=\frac{1 - (|S_1||S_2|)^T}{1 - |S_1||S_2|}$$

Let us check for the two examples above: $|S_1||S_2|=4$. Indeed for $T=2$ we have:

$$\frac{1 - (|S_1||S_2|)^T}{1 - |S_1||S_2|}=\frac{15}{3}=5$$

For $T=3$ we have:

$$\frac{1 - (|S_1||S_2|)^T}{1 - |S_1||S_2|}=\frac{63}{3}=21$$

5. State and prove the theorem of sequence of stage Nash equilibria.

6. Obtain all sequence of pure stage Nash equilibria as well as another Nash equilibrium for the following repeated games: 1. $A = \begin{pmatrix} 3 & -1\\ 2 & 4\\ 3 & 1 \end{pmatrix} \qquad B = \begin{pmatrix} 13 & -1\\ 6 & 2\\ 3 & 1 \end{pmatrix} \qquad T=2$

Identifying the best responses:

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

Thus the pure Nash equilibria for the stage game are:

$$\{(r_1, c_1), (r_3, c_1)\}$$

So the following are Nash equilibria for the repeated games:

$$\{(r_1r_1, c_1c_1), (r_1r_3, c_1c_1), (r_3r_1, c_1c_1), (r_3r_3, c_1c_1)\}$$

Consider the following strategy pair:

For the row player:

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

For the column player:

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

This strategy corresponds to the following scenario:

Play $(r_2,c_2)$ in first stage and $(r_3,c_1)$ in second stage unless the column player does not cooperate in which case play $(r_1, c_1)$.

If both players play these strategies their utilities are: $(7, 15)$ which is better for both players then the utilities at any Nash equilibria. But is this a Nash equilibrium? To find out we investigate if either player has an incentive to deviate.

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

Thus this is a Nash equilibria.

2. $A = \begin{pmatrix} 2 & -1 & 8\\ 4 & 2 & 9 \end{pmatrix} \qquad B = \begin{pmatrix} 13 & 14 & -1\\ 6 & 2 & 6 \end{pmatrix} \qquad T=2$

Identifying the best responses:

$A = \begin{pmatrix} 2 & -1 & 8\\ \underline{4} & \underline{2} & \underline{9} \end{pmatrix} \qquad B = \begin{pmatrix} 13 & \underline{14} & -1\\ \underline{6} & 2 & \underline{6} \end{pmatrix}$

The pure Nash equilibria are:

$$\{(r_2, c_1), (r_2, c_3)\}$$

So the following is a Nash equilibrium for the repeated game:

$$\{(r_2r_2, c_1c_1), (r_2r_2, c_3c_1), (r_2r_2, c_1c_3), (r_2r_2, c_3c_3)\}$$

Consider the following strategy pair:

For the row player:

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

For the column player:

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

This strategy corresponds to the following scenario:

Play $(r_1,c_2)$ in first stage and $(r_2,c_3)$ in second stage unless the row player does not cooperate in which case play $(r_2, c_1)$.

If both players play these strategies their utilities are: $(8, 20)$ which is better for both players then the utilities at any Nash equilibria. But is this a Nash equilibrium? To find out we investigate if either player has an incentive to deviate.

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

Thus this is a Nash equilibria.

Previous

Next

Source code: @drvinceknight Powered by: Python Mathjax Github pages Skeleton css