Repeated games - solutions

  1. Define a repeated game.

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

  2. Define a strategy for a repeated game.

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

    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.

Previous

Next

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