Skip to content

Latest commit

 

History

History
314 lines (233 loc) · 8.83 KB

repeated-games.rst

File metadata and controls

314 lines (233 loc) · 8.83 KB

Repeated Games

Motivating example: Repeated Coordination Game

Consider the Coordination game <motivating-example-coordination-game> but in this instance Alice and Bob repeat their play of this game. In other words, they aim to meet (both making their decision at the same time) and after this first meeting they repeat the process, with full knowledge of the outcome of the first play.

This can be represented pictorially as follows:

image

To show this as an equivalent extensive form game <extensive-form-games-discussion>, the tree is the same but we take care to label the vertices correctly:

image

Definition of a repeated games

Given a two player game (A, B) ∈ ℝm × n2, referred to as a stage game, a T-stage repeated game is a game in which players play that stage game for T > 0 repetitions. Players make decisions based on the full history of play over all the repetitions.

Question

For the following values of T and the following stage games, how many leaves would the extensive form representation of the repeated game have:

1.

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

2.

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

3.

$$\begin{aligned} A = \begin{pmatrix}0 & 1 \\ -1 & 3\end{pmatrix} \qquad B = -A \qquad T = 3 \end{aligned}$$

4.

$$\begin{aligned} A = \begin{pmatrix}0 & 1 & 4\\1 &-1 & 3\end{pmatrix} \qquad B = -A \qquad T = 2 \end{aligned}$$

Answer

  1. The initial play of the game will have 4 leaves (corresponding to the 2 choices by each player), each leave will in turn have 4 leaves. Thus, the total number of leaves will be 16.
  2. The initial play of the game will have 4 leaves (corresponding to the 2 choices by each player), each leave will in turn have 4 leaves. Thus, the total number of leaves will be 16.
  3. The initial play of the game will have 4 leaves (corresponding to the 2 choices by each player), each leave will in turn have 4 leaves in the second repetition. In the final repetition each of those leaves will have 4 leaves. Thus, the total number of leaves will be 64.
  4. The initial play of the game will have 6 leaves (corresponding to the 2 choices by the row player and 3 by the column player), each leave will in turn have 6 leaves in the second repetition. Thus, the total number of leaves will be 36.

Strategies in a repeated game

A strategy for a player in a repeated game is a mapping from all possible histories of play to a probability distribution over the action set of the stage game.

Question

For the repeated coordination game <motivating-example-repeated-game> which of the following are valid strategies, and in the case of valid strategies what is the outcome.

  1. For the row player:


    $$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to C\\ (S, S) &\to C\\ (S, C) &\to C\\ (C, S) &\to S\\ (C, C) &\to S\\ \end{align} \end{aligned}$$

    For the column player:


    $$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to S\\ (S, S) &\to C\\ (S, C) &\to C\\ (C, S) &\to S\\ (C, C) &\to S\\ \end{align} \end{aligned}$$

  2. For the row player:


    $$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to C\\ (S, S) &\to C\\ (C, S) &\to S\\ (C, C) &\to S\\ \end{align} \end{aligned}$$

    For the column player:


    $$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to S\\ (S, S) &\to C\\ (S, C) &\to C\\ (C, S) &\to S\\ (C, C) &\to S\\ \end{align} \end{aligned}$$

  3. For the row player:


    $$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to C\\ (S, S) &\to C\\ (C, S) &\to S\\ (S, C) &\to S\\ (C, C) &\to S\\ \end{align} \end{aligned}$$

    For the column player:


    $$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to S\\ (S, S) &\to C\\ (S, C) &\to C\\ (C, S) &\to \alpha\\ (C, C) &\to S\\ \end{align} \end{aligned}$$

  4. For the row player:


    $$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to S\\ (S, S) &\to C\\ (C, S) &\to S\\ (S, C) &\to C\\ (C, C) &\to S\\ \end{align} \end{aligned}$$

    For the column player:


    $$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to S\\ (S, S) &\to C\\ (S, C) &\to C\\ (C, S) &\to S\\ (C, C) &\to S\\ \end{align} \end{aligned}$$

Answer

  1. This is a valid strategy pair: all possible histories are mapped to correct actions. The outcome would be: (3, 2) (corresponding to O9 of the extensive form representation).
  2. This is not a valid strategy pair: the row player strategy does not have a mapping from (S, C).
  3. This is not a valid strategy pair: the column player strategy maps from (C, S) to an action (α) that is not in the action space of the stage game.
  4. This is a valid strategy pair: all possible histories are mapped to correct actions. The outcome would be: (5, 5) (corresponding to O4 of the extensive form representation).

Equilibria in repeated games

In a repeated game it is possible for players to encode reputation and trust in their strategies.

Consider as an example the following stage game with T = 2:

$$\begin{aligned} A = \begin{pmatrix} 0 & 6 & 1\\\ 1 & 7 & 5 \end{pmatrix} \qquad B = \begin{pmatrix} 0 & 3 & 1\\\ 1 & 0 & 1 \end{pmatrix} \end{aligned}$$

Through inspection it is possible to verify that the following strategy pair is a Nash equilibrium:

For the row player:

$$\begin{aligned} \begin{align} (\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\\\ (r_2, c_1) &\to r_2\\\ (r_2, c_2) &\to r_2\\\ (r_2, c_3) &\to r_2\\\ \end{align} \end{aligned}$$

For the column player:

$$\begin{aligned} \begin{align} (\emptyset, \emptyset) &\to c_2\\\ (r_1, c_1) &\to c_3\\\ (r_2, c_1) &\to c_1\\\ (r_1, c_2) &\to c_3\\\ (r_2, c_2) &\to c_1\\\ (r_1, c_3) &\to c_3\\\ (r_2, c_3) &\to c_1\\\ \end{align} \end{aligned}$$

This pair of strategies correspond to the following scenario:

The row player plays r1 and the column player plays c2 in the first state. The row player plays r2 and the column player plays c3 in the second stage.

Note that if the row player deviates and plays r2 in the first stage then the column player will play c1.

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

  1. If the row player deviates, they would only be rational to do so in the first stage, if they did they would gain 1 in that stage but lose 4 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.

Thus this strategy pair is a Nash equilibrium and evidences how a reputation can be built and cooperation can emerge from complex dynamics.

Using Nashpy

Repeated games are a particularly compact way of representing a given subset of extensive-form-games-discussion. Thus, it is possible to study them as an equivalent normal form game <equivalence-of-extensive-and-normal-form-games>. See how-to-obtain-a-repeated-game for guidance of how to use Nashpy to generate a normal form game by repeating a stage game.