<p>Suppose all players play unconditioned Nash equilibria, except player $i$ who diverts and plays another strategy. The other strategy of player $i$ may depend on history. We have to show that player $i$'s payoff in the repeated game does not increase.</p>

<p>For every time-period t, define the following random variables:</p>

<ul>
<li>$X^{t}$ - the utility of player $i$ in time t when all players, including player $i$, play the basic Nash equilibrium.</li>
<li>$Y_{h}^{t}$ (where $h$ is a history vector of length $t-1$) - the utility of player $i$ in time $t$ when player $i$ diverts and plays the alternative strategy while all other players continue to play the basic Nash equilibrium.</li>
<li>$Y^{t}$ - the utility of player $i$  in time $t$ when player $i$  diverts while all other players continue to play the basic Nash equilibrium:
$$Y^{t}=\sum_{h}Prob[h]\cdot Y_{h}^{t}$$</li>
</ul>

<p>By definition of a Nash equilibrium, for every time $t$
and for every history $h$:</p>

<p>$$E[Y_{h}^{t}]\leq E[X^{t}]$$</p>

<p>Hence also:</p>

<p>$$E[Y^{t}]\,=\,\sum_{h}Pr[h]\cdot E[Y_{h}^{t}]\,\leq\,\sum_{h}Pr[h]\cdot E[X^{t}]\,\leq\,E[X^{t}]\cdot\sum_{h}Pr[h]\,\leq\,E[X^{t}]$$</p>

<p>Summing over the entire series, and using the fact that the expectation of a sum is the sum of expectations:</p>

<p>$$E[\sum_{t=1}^{T}Y^{t}]\leq E[\sum_{t=1}^{T}X^{t}]$$</p>

<p>So the player cannot gain by deviating.</p>

<hr>

<p>Thanks to @denesp for verifying this proof!</p>

CC BY-SA 3.0
2015-08-26T14:10:24.387Z
2015-08-26T14:10:24.387Z
Erel Segal-Halevi
<p>What is a formal proof to this known fact about repeated games?</p>

<blockquote>
  <p>The situation in which, in every time step, the players play a Nash equilibrium in the basic game unconditioned on history, is a Nash equilibrium in the repeated game.</p>
</blockquote>

CC BY-SA 3.0
2015-08-26T13:58:48.083Z
Perhaps you ought to reformat this as a question and post your proof as an answer.
Giskard
CC BY-SA 3.0
2015-08-26T14:00:59.167Z
Your proof is essentially correct. It is difficult to say if it is sufficiently formal. Sufficient for who? The logic was easy to understand (this is subjective), but $X^t, Y^t$ could probably be defined as functions of strategies.
Giskard
<game-theory><repeated-games>
Repeatedly playing an equilibrium in a repeated game
Erel Segal-Halevi
# Repeatedly playing an equilibrium in a repeated game

(Asked by: username_0 on 2015-08-24)

What is a formal proof to this known fact about repeated games?

> The situation in which, in every time step, the players play a Nash equilibrium in the basic game unconditioned on history, is a Nash equilibrium in the repeated game.

**Tags:** game-theory, repeated-games
> **Comments:**
> **username_1**: Perhaps you ought to reformat this as a question and post your proof as an answer.  
> **username_1**: Your proof is essentially correct. It is difficult to say if it is sufficiently formal. Sufficient for who? The logic was easy to understand (this is subjective), but $X^t, Y^t$ could probably be defined as functions of strategies.  

---

## 1 answers

### Answer by username_0 on 2015-08-26. Score: 1 | Accepted answer

Suppose all players play unconditioned Nash equilibria, except player $i$ who diverts and plays another strategy. The other strategy of player $i$ may depend on history. We have to show that player $i$'s payoff in the repeated game does not increase.

For every time-period t, define the following random variables:

* $X^{t}$ - the utility of player $i$ in time t when all players, including player $i$, play the basic Nash equilibrium.
* $Y\_{h}^{t}$ (where $h$ is a history vector of length $t-1$) - the utility of player $i$ in time $t$ when player $i$ diverts and plays the alternative strategy while all other players continue to play the basic Nash equilibrium.
* $Y^{t}$ - the utility of player $i$ in time $t$ when player $i$ diverts while all other players continue to play the basic Nash equilibrium:
  $$Y^{t}=\sum\_{h}Prob[h]\cdot Y\_{h}^{t}$$

By definition of a Nash equilibrium, for every time $t$
and for every history $h$:

$$E[Y\_{h}^{t}]\leq E[X^{t}]$$

Hence also:

$$E[Y^{t}]\,=\,\sum\_{h}Pr[h]\cdot E[Y\_{h}^{t}]\,\leq\,\sum\_{h}Pr[h]\cdot E[X^{t}]\,\leq\,E[X^{t}]\cdot\sum\_{h}Pr[h]\,\leq\,E[X^{t}]$$

Summing over the entire series, and using the fact that the expectation of a sum is the sum of expectations:

$$E[\sum\_{t=1}^{T}Y^{t}]\leq E[\sum\_{t=1}^{T}X^{t}]$$

So the player cannot gain by deviating.

---

Thanks to @denesp for verifying this proof!


---

