Repeatedly playing an equilibrium in a repeated game 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.
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!