# Repeated Games¶

## Motivating example: Repeated Coordination Game¶

Consider the 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:

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

## Definition of a repeated games¶

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\) 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:

- \[\begin{split}A = \begin{pmatrix}1 & 2 \\ 2 & 3\end{pmatrix} \qquad B = \begin{pmatrix}2 & 3 \\ 1 & -1\end{pmatrix} \qquad T = 2\end{split}\]
- \[\begin{split}A = \begin{pmatrix}0 & 1 \\ -1 & 3\end{pmatrix} \qquad B = -A \qquad T = 2\end{split}\]
- \[\begin{split}A = \begin{pmatrix}0 & 1 \\ -1 & 3\end{pmatrix} \qquad B = -A \qquad T = 3\end{split}\]
- \[\begin{split}A = \begin{pmatrix}0 & 1 & 4\\1 &-1 & 3\end{pmatrix} \qquad B = -A \qquad T = 2\end{split}\]

Answer

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.

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.

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.

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 which of the following are valid strategies, and in the case of valid strategies what is the outcome.

For the row player:

\[\begin{split}\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{split}\]For the column player:

\[\begin{split}\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{split}\]For the row player:

\[\begin{split}\begin{align*} (\emptyset, \emptyset) &\to C\\ (S, S) &\to C\\ (C, S) &\to S\\ (C, C) &\to S\\ \end{align*}\end{split}\]For the column player:

\[\begin{split}\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{split}\]For the row player:

\[\begin{split}\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{split}\]For the column player:

\[\begin{split}\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{split}\]For the row player:

\[\begin{split}\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{split}\]For the column player:

\[\begin{split}\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{split}\]

Answer

This is a valid strategy pair: all possible histories are mapped to correct actions. The outcome would be: \((3,2)\) (corresponding to \(O_9\) of the extensive form representation).

This is not a valid strategy pair: the row player strategy does not have a mapping from \((S, C)\).

This is not a valid strategy pair: the column player strategy maps from \((C, S)\) to an action (\(\alpha\)) that is not in the action space of the stage game.

This is a valid strategy pair: all possible histories are mapped to correct actions. The outcome would be: \((5,5)\) (corresponding to \(O_4\) 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\):

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

For the row player:

For the column player:

This pair of strategies correspond to the following scenario:

The row player plays \(r_1\) and the column player plays \(c_2\) in the first state. The row player plays \(r_2\) and the column player plays \(c_3\) in the second stage.

Note that if the row player deviates and plays \(r_2\) in the first stage then the column player will play \(c_1\).

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.

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.

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.

## Exercises¶

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

\(\mathcal{A}_1=\mathcal{A}_2=\{0, 1\}\) and \(T=2\)

\(\mathcal{A}_1=\{r_1, r_2\}\;\mathcal{A}_2=\{c_1, c_2\}\) and \(T=3\)

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

Prove that a sequence of stage Nash equilibria is a Nash equilibria for the repeated game.

Obtain all sequence of stage Nash equilibria as well as another Nash equilibrium for the following repeated games:

\[\begin{split}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\end{split}\]\[\begin{split}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\end{split}\]

## Using Nashpy¶

Repeated games are a particularly compact way of representing a given subset of Extensive Form Games. Thus, it is possible to study them as an equivalent normal form game. See Obtain a repeated game for guidance of how to use Nashpy to generate a normal form game by repeating a stage game.