1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Perhaps you ought to reformat this as a question and post your proof as an answer. $\endgroup$
    – Giskard
    Aug 26 '15 at 13:58
  • $\begingroup$ 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. $\endgroup$
    – Giskard
    Aug 26 '15 at 14:00
1
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.