<p>The intuition is that, following any history <span class="math-container">$h^t$</span>, the continuation strategy should be a subgame perfect equilibrium <span class="math-container">$\sigma|h^t$</span>, which allows you to <em>predict the value</em> of continuation play (<span class="math-container">$V(\sigma|h^t)$</span>) with certainty. Therefore, when choosing the current-stage strategy, a player know her action <span class="math-container">$a$</span> counts toward <span class="math-container">$h^t$</span>, which in turn, leads to <span class="math-container">$\sigma|h^{t-1}\cup\{a\}$</span>, generating a certain continuation payoff <span class="math-container">$v_i(\sigma|h^{t-1}\cup\{a\})$</span>. And because other things are already determined, you can simply write <span class="math-container">$v_i(a)$</span>. This is precisely why the continuation payoff is in fact history-strategy dependent.</p>
<p>The normal form says the players are choosing today's strategy <span class="math-container">$a$</span> by trading off today's payoff <span class="math-container">$u_i(a)$</span> and (discounted) future valuation <span class="math-container">$v_i(a)$</span>. You can use the normal form because everything can be summarised into a current-stage variable <span class="math-container">$a$</span>.</p>
<p><strong>Edits:</strong>
Question (1): you are right, there're infinitely many strategies for each player. However, to deal with this repeated game, we conjecture that there is some SPE <span class="math-container">$\sigma$</span> being played following action <span class="math-container">$a$</span>. One-shot deviation principle makes it clear you never deviate from <span class="math-container">$\sigma$</span>. Think it as some black-box algorithm that automatically choose the best action for you forever, after your play for the current period. In this sense, any future strategies are summarized by the current action <span class="math-container">$a$</span>, and <span class="math-container">$U_i(\sigma|(h_{t-1}, a)$</span> is function of only <span class="math-container">$a$</span> but not anything else, so you can relabel it as <span class="math-container">$v_i(a)$</span>.</p>
<p>Question (2): Then the SPE of the repeated game contains <span class="math-container">$(0,0)$</span> as the first period strategy, e.g., Round 1: play <span class="math-container">$0$</span>; Round 2: if <span class="math-container">$(0,0)$</span> was played in round 1, play <span class="math-container">$a_{(0,0)}$</span>, otherwise...</p>
<p>Since it's an infinitely repeated game, you should have one SPE where <span class="math-container">$(0,0)$</span> is played every period. E.g., infinitely repeated prisoner's dilemma, you have (confess,confess) to be played ``no matter what'' as an SPE, but you can also have grim trigger -- (deny, deny) is a Nash equilibrium in your normal form, and for next period, if (deny, deny) is played, then continue (deny, deny); otherwise, (confess, confess) forever.</p>
<p>Question (3): Yes. From the logic above, you should see there can be infinitely many SPE.</p>

CC BY-SA 4.0
2024-07-10T20:34:00.330Z
Thanks DiZ. First, you made me realise that I forgot to add $a$ in the continuation strategy, I've edited my question. Still, I do not understand how we go from $U_i(\sigma| (h_t, a))$ to $\nu_i(a)$. Where do $\sigma$ and $h_t$ go? Are they implicit?
Star
CC BY-SA 4.0
2024-07-10T21:23:25.377Z
I have split my questions into 3 subquestions. If you could answer those, in particular (3), it would be very helpful.
Star
CC BY-SA 4.0
2024-07-11T02:14:25.480Z
Hi Star, thanks for clarifying. Just edited my original answer.
DiZ
CC BY-SA 4.0
2024-07-11T17:14:52.103Z
Thanks, but your answers do not seem to match my questions
Star
CC BY-SA 4.0
2024-07-11T18:11:13.767Z
Sorry for the confusion, I have edited my answers to those questions.
DiZ
CC BY-SA 4.0
2024-07-10T19:20:59.990Z
2024-07-11T18:10:46.220Z
2024-07-11T18:10:46.220Z
DiZ
<p>Consider an infinitely-repeated game with perfect monitoring and pure strategies. The one-shot deviation principle tells us that a strategy profile <span class="math-container">$\sigma$</span> is a subgame perfect Nash equilibrium if and only if there are no profitable one-shot deviations.</p>
<p>More precisely, let <span class="math-container">$h^t$</span> denote the history available to players up to the beginning of period <span class="math-container">$t$</span>.</p>
<p>For each history <span class="math-container">$h^t$</span>, let <span class="math-container">$a^*=\sigma(h^t)$</span>. It must be that<br />
<span class="math-container">$$
(1-\delta) u_i(a^*)+\delta U_i(\sigma|_{(h^t,a^*)})\geq (1-\delta) u_i(a_i, a^*_{-i})+\delta U_i(\sigma|_{(h^t,a_i, a^*_{-i})})\quad \forall a_i, \forall i
$$</span>
where</p>
<ul>
<li><p><span class="math-container">$\delta$</span> is the discount factor</p>
</li>
<li><p><span class="math-container">$u_i$</span> is the stage game payoff</p>
</li>
<li><p><span class="math-container">$\sigma|_{(h^t,a)}$</span> is player <span class="math-container">$i$</span>'s continuation strategy induced by history <span class="math-container">$h^t$</span> and action <span class="math-container">$a$</span>.</p>
</li>
<li><p><span class="math-container">$U_i$</span> is the continuation payoff</p>
</li>
</ul>
<p><strong>Question:</strong> My lecture notes say that in this setting <span class="math-container">$U_i(\sigma|_{h^t,a})$</span> just depends on <span class="math-container">$a$</span> and so can be denoted by <span class="math-container">$v_i(a)$</span>. Hence, the normal form of this game with 2 players and 2 actions <span class="math-container">$\{0,1\}$</span> is</p>
<pre><code>|      (1-delta)u_1(1,1)+delta*v_1(1,1)  | (1-delta)u_1(1,0)+delta*v_1(1,0)
|      (1-delta)u_2(1,1)+delta*v_2(1,1)  | (1-delta)u_2(1,0)+delta*v_2(1,0)
|----------------------------------------|----------------------------------------
|      (1-delta)u_1(0,1)+delta*v_1(0,1)  | (1-delta)u_1(0,0)+delta*v_1(0,0)
|      (1-delta)u_2(0,1)+delta*v_2(0,1)  | (1-delta)u_2(0,0)+delta*v_2(0,0)
</code></pre>
<p>I don't understand this step at all. In particular:</p>
<p>(1) The fact that I can write the normal form of a repeated game as above is a consequence of the one-shot deviation principle?</p>
<p>(2) Suppose in the above normal-form game, <span class="math-container">$(0,0)$</span> is a Nash Equilibrium for given values of <span class="math-container">$v_1, v_2$</span>. What is the relation between such Nash equilibrium and a subgame perfect Nash equilibrium of the repeated game?</p>
<p>(3) Suppose in the above normal-form game, <span class="math-container">$(0,0)$</span> and <span class="math-container">$(0,1)$</span>  are Nash Equilibria for given values of <span class="math-container">$v_1, v_2$</span>. Does this imply that there are multiple subgame perfect Nash equilibria in the repeated game as well?</p>

<game-theory><repeated-games>
About the normal form of a repeated game
Star
# About the normal form of a repeated game

(Asked by: username_0 on 2024-07-10)

Consider an infinitely-repeated game with perfect monitoring and pure strategies. The one-shot deviation principle tells us that a strategy profile $\sigma$ is a subgame perfect Nash equilibrium if and only if there are no profitable one-shot deviations.
More precisely, let $h^t$ denote the history available to players up to the beginning of period $t$.
For each history $h^t$, let $a^*=\sigma(h^t)$. It must be that
$$
(1-\delta) u_i(a^*)+\delta U_i(\sigma|_{(h^t,a^*)})\geq (1-\delta) u_i(a_i, a^*_{-i})+\delta U_i(\sigma|_{(h^t,a_i, a^*_{-i})})\quad \forall a_i, \forall i
$$
where

$\delta$ is the discount factor

$u_i$ is the stage game payoff

$\sigma|_{(h^t,a)}$ is player $i$'s continuation strategy induced by history $h^t$ and action $a$.

$U_i$ is the continuation payoff


Question: My lecture notes say that in this setting $U_i(\sigma|_{h^t,a})$ just depends on $a$ and so can be denoted by $v_i(a)$. Hence, the normal form of this game with 2 players and 2 actions $\{0,1\}$ is
|      (1-delta)u_1(1,1)+delta*v_1(1,1)  | (1-delta)u_1(1,0)+delta*v_1(1,0)
|      (1-delta)u_2(1,1)+delta*v_2(1,1)  | (1-delta)u_2(1,0)+delta*v_2(1,0)
|----------------------------------------|----------------------------------------
|      (1-delta)u_1(0,1)+delta*v_1(0,1)  | (1-delta)u_1(0,0)+delta*v_1(0,0)
|      (1-delta)u_2(0,1)+delta*v_2(0,1)  | (1-delta)u_2(0,0)+delta*v_2(0,0)

I don't understand this step at all. In particular:
(1) The fact that I can write the normal form of a repeated game as above is a consequence of the one-shot deviation principle?
(2) Suppose in the above normal-form game, $(0,0)$ is a Nash Equilibrium for given values of $v_1, v_2$. What is the relation between such Nash equilibrium and a subgame perfect Nash equilibrium of the repeated game?
(3) Suppose in the above normal-form game, $(0,0)$ and $(0,1)$  are Nash Equilibria for given values of $v_1, v_2$. Does this imply that there are multiple subgame perfect Nash equilibria in the repeated game as well?

**Tags:** game-theory, repeated-games

---

## 1 answers

### Answer by username_1 on 2024-07-10. Score: 0

The intuition is that, following any history $h^t$, the continuation strategy should be a subgame perfect equilibrium $\sigma|h^t$, which allows you to *predict the value* of continuation play ($V(\sigma|h^t)$) with certainty. Therefore, when choosing the current-stage strategy, a player know her action $a$ counts toward $h^t$, which in turn, leads to $\sigma|h^{t-1}\cup\{a\}$, generating a certain continuation payoff $v\_i(\sigma|h^{t-1}\cup\{a\})$. And because other things are already determined, you can simply write $v\_i(a)$. This is precisely why the continuation payoff is in fact history-strategy dependent.

The normal form says the players are choosing today's strategy $a$ by trading off today's payoff $u\_i(a)$ and (discounted) future valuation $v\_i(a)$. You can use the normal form because everything can be summarised into a current-stage variable $a$.

**Edits:**
Question (1): you are right, there're infinitely many strategies for each player. However, to deal with this repeated game, we conjecture that there is some SPE $\sigma$ being played following action $a$. One-shot deviation principle makes it clear you never deviate from $\sigma$. Think it as some black-box algorithm that automatically choose the best action for you forever, after your play for the current period. In this sense, any future strategies are summarized by the current action $a$, and $U\_i(\sigma|(h\_{t-1}, a)$ is function of only $a$ but not anything else, so you can relabel it as $v\_i(a)$.

Question (2): Then the SPE of the repeated game contains $(0,0)$ as the first period strategy, e.g., Round 1: play $0$; Round 2: if $(0,0)$ was played in round 1, play $a\_{(0,0)}$, otherwise...

Since it's an infinitely repeated game, you should have one SPE where $(0,0)$ is played every period. E.g., infinitely repeated prisoner's dilemma, you have (confess,confess) to be played ``no matter what'' as an SPE, but you can also have grim trigger -- (deny, deny) is a Nash equilibrium in your normal form, and for next period, if (deny, deny) is played, then continue (deny, deny); otherwise, (confess, confess) forever.

Question (3): Yes. From the logic above, you should see there can be infinitely many SPE.

> **Comments:**
> **username_0**: Thanks DiZ. First, you made me realise that I forgot to add $a$ in the continuation strategy, I've edited my question. Still, I do not understand how we go from $U_i(\sigma| (h_t, a))$ to $\nu_i(a)$. Where do $\sigma$ and $h_t$ go? Are they implicit?  
> **username_0**: I have split my questions into 3 subquestions. If you could answer those, in particular (3), it would be very helpful.  
> **username_1**: Hi Star, thanks for clarifying. Just edited my original answer.  
> **username_0**: Thanks, but your answers do not seem to match my questions  
> **username_1**: Sorry for the confusion, I have edited my answers to those questions.  

---

