{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Repeated games\n",
"\n",
"---\n",
"\n",
"## Definition of a repeated game\n",
"\n",
"[Video](https://youtu.be/K4LKeO2rdgM?list=PLnC5h3PY-znxMsG0TRYGOyrnEO-QhVwLb)\n",
"\n",
"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$ periods. Players make decisions based on the full history of play over all the periods.\n",
"\n",
"---\n",
"\n",
"For example consider the game:\n",
"\n",
"$$\n",
"A = \n",
"\\begin{pmatrix}\n",
"0 & 6 & 1\\\\\n",
"1 & 7 & 5\n",
"\\end{pmatrix}\n",
"\\qquad\n",
"B = \n",
"\\begin{pmatrix}\n",
"0 & 3 & 1\\\\\n",
"1 & 0 & 1\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"by identifying the best responses:\n",
"\n",
"$$\n",
"A = \n",
"\\begin{pmatrix}\n",
"0 & 6 & 1\\\\\n",
"\\underline{1} & \\underline{7} & \\underline{5}\n",
"\\end{pmatrix}\n",
"\\qquad\n",
"B = \n",
"\\begin{pmatrix}\n",
"0 & \\underline{3} & 1\\\\\n",
"\\underline{1} & 0 & \\underline{1}\n",
"\\end{pmatrix}\n",
"$$\n",
"\n",
"it is immediate to find two Nash equilibria:\n",
"\n",
"$$((0,1), (1,0,0))\\qquad((0,1), (0,0,1))$$"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(array([0., 1.]), array([1., 0., 0.])),\n",
" (array([0., 1.]), array([0., 0., 1.]))]"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"import nashpy as nash\n",
"import numpy as np\n",
"\n",
"A = np.array([[0, 6, 1],\n",
" [1, 7, 5]])\n",
"B = np.array([[0, 3, 1],\n",
" [1, 0, 1]])\n",
"game = nash.Game(A, B)\n",
"list(game.support_enumeration())"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If we were to repeat this game twice ($T=2$) we obtain a new game. However to be able to think of this we need to define what a strategy in a repeated game is.\n",
"\n",
"---\n",
"\n",
"## Definition of a strategy in a repeated game\n",
"\n",
"Given a two player stage game $(A,B)\\in{\\mathbb{R}^{m\\times n}}^2$, repeated to give a $T$-stage repeated game. A strategy is a mapping from the entire history of play to an action of the stage game:\n",
"\n",
"$$\n",
"\\bigcup_{t=0}^{T-1}H(t)\\to a\n",
"$$\n",
"\n",
"where:\n",
"\n",
"- $H(t)$ is the history of play of **both** players up until stage $t$ ($H(0)=(\\emptyset, \\emptyset)$)\n",
"- $a$ is an action (for either player) of the **stage** game\n",
"\n",
"---\n",
"\n",
"To help avoid confusion, whilst we have referred to pure strategies as choices made in stage games, here we will call those **actions**.\n",
"\n",
"The actions for our example:\n",
"\n",
"- for the row player: $\\{r_1, r_2\\}$ (corresponding to the rows)\n",
"- for the column player: $\\{c_1, c_2, c_3\\}$ (corresponding to the columns)\n",
"\n",
"A strategy for the row/column player thus needs to map an element of the following set to an element of $\\{r_1, r_2\\}$/$\\{c_1, c_2, c_3\\}$:\n",
"\n",
"$$\\bigcup_{t=0}^{1}H(t)=\\{(\\emptyset, \\emptyset), (r_1, c_1), (r_1, c_2), (r_1, c_3), (r_2, c_1), (r_2, c_2), (r_3, c_3)\\}$$\n",
"\n",
"In other words, in our example, a strategy answers both of the following questions:\n",
"\n",
"- What should the player do in the first period?\n",
"- What should the player do in the second period **given** knowledge of what both players did in the first period?\n",
"\n",
"The following theorem allows us to find **a** Nash equilibrium:\n",
"\n",
"\n",
"---\n",
"\n",
"## Theorem of sequence of stage Nash equilibria\n",
"\n",
"[Video](https://www.youtube.com/watch?v=wtl69v7Qz_s&list=PLnC5h3PY-znxMsG0TRYGOyrnEO-QhVwLb&index=30)\n",
"\n",
"For any repeated game, any sequence of stage Nash profiles gives a Nash equilibrium.\n",
"\n",
"### Proof \n",
"\n",
"\n",
"Consider the following strategy:\n",
"\n",
"> The row/column player should play action $a_{r/c}$ regardless of the play of any previous strategy profiles.\n",
"\n",
"where $(a_{r}, a_{c})$ is a given stage Nash equilibrium.\n",
"\n",
"Using backwards induction, this is a Nash equilibrium for the last stage game. Thus, at the last stage, no player has a reason to deviate. Similarly at the $T-1$th stage. The proof follows.\n",
"\n",
"---\n",
"\n",
"Thus, for our example we have the four Nash equilibria:\n",
"\n",
"- $(r_2r_2, c_1c_1)$ with utility: (2, 2).\n",
"- $(r_2r_2, c_1c_3)$ with utility: (6, 2).\n",
"- $(r_2r_2, c_3c_1)$ with utility: (6, 2).\n",
"- $(r_2r_2, c_3c_3)$ with utility: (10, 2).\n",
"\n",
"Note however that it is not the only equilibria for our repeated game.\n",
"\n",
"## Reputation\n",
"\n",
"[Video](https://youtu.be/VMYpSJMYQU0?list=PLnC5h3PY-znxMsG0TRYGOyrnEO-QhVwLb)\n",
"\n",
"In a repeated game it is possible for players to encode reputation and trust in their strategies.\n",
"\n",
"Consider the following two strategies:\n",
"\n",
"1. For the row player:\n",
"\n",
" $$(\\emptyset, \\emptyset) \\to r_1$$\n",
" $$(r_1, c_1) \\to r_2$$\n",
" $$(r_1, c_2) \\to r_2$$\n",
" $$(r_1, c_3) \\to r_2$$\n",
" \n",
"2. For the column player:\n",
"\n",
" $$(\\emptyset, \\emptyset) \\to c_2$$\n",
" $$(r_1, c_2) \\to c_3$$\n",
" $$(r_2, c_2) \\to c_1$$\n",
"\n",
"\n",
"Note that here we omit some of the histories which are not possible based on the first play by each player.\n",
"\n",
"This strategy corresponds to the following scenario:\n",
"\n",
"> 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)$.\n",
"\n",
"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.\n",
"\n",
"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.\n",
"2. If the column player deviates, they would only do so in the first stage and gain no utility.\n",
"\n",
"Thus this strategy pair **is a Nash equilibrium** and evidences how a reputation can be built and cooperation can emerge from complex dynamics."
]
}
],
"metadata": {
"anaconda-cloud": {},
"kernelspec": {
"display_name": "GT",
"language": "python",
"name": "gt"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.6.1"
}
},
"nbformat": 4,
"nbformat_minor": 2
}