Define a repeated game.

Bookwork: https://vknight.org/gt/chapters/08/#Definition-of-a-repeated-game

Define a strategy for a repeated game.

Bookwork: https://vknight.org/gt/chapters/08/#Definition-of-a-repeated-game

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

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

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

$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)\}$$

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 $$

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

Bookwork: https://vknight.org/gt/chapters/08/#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.

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