Nash Folk Theorem

EC487_Advanced_Microeconomics

Consider a finite stage game $(N,A,u)$, where:

• $N=\{1,2,\dots n\}$ the set of players
• $A=A_1\times A_2\times \cdots \times A_n$ the action sets.
• $u=\{u_1\dots u_n\}$ the stage games payoffs.

The game is repeated infinitely with discount factor $\delta \in (0,1)$, and the player payoffs are:

$$U^j(a_0,a_1,\dots )=(1-\delta )\sum _{t=1}^{\infty }{\delta }^t{u}^j(a_t)$$

We recall the Min-Max = Max-Min strategy here, we define the lowest payoff other players can force upon player $j$ in any stage game:

$$V_{\min \max }^j=\underset{a^{-j}\in A^{-j}}{\min }\underset{a^j\in A^j}{\max }{u}^j(a^j,a^{-j})$$

The minmax admits a straightforward interpretation as an extensive-form game: other players move first to punish player $j$; $j$ subsequently Best Response.

We could then define that, a payoff profile $W=(W^j{)}_{j=1}^N$ is individually rational if $W^j\ge V_{\min \max }^j$ for all $j$.

Proposition

Thus we are able to make the proposition of Nash Folk Theorem

Let $W$ a feasible and strictly individually rational payoff profile of the stage game $(N,A,u)$. Then for all $ϵ>0$ such that $W^j-ϵ>V_{\min \max }^j$ uniformly for all players $j$, there exists $\underline{\delta }>0$ such that any infinitely repeated game where $\delta \ge \underline{\delta }$ there exists a Nash Equilibrium whose equilibrium payoff profile is $ϵ$ close to $W$.

---

Some hints to prove Nash Folk Theorem with a unique action profile.

We construct the game $N=\{1,\dots ,n\}$ where for all players, we define their Strategy $s^j$ as:

• Cooperate State (initial state):
  • at $t=0$, play $a^j$.
  • Then at history $h=\{a,a,a,\dots ,\}$ always play $a^j$
• Punishment State:
  • Once at $t$, if observe a player $i$ doesn’t play $a^i$, then from the start of $t+1$, every player $j\ne i$ plays $a_{\min \max }^{-i}$ where $a_{\min \max }^{-i}=\arg {\min }_{a^{-}i}{u}_i(a^{-i},a^i)$

We want to show that if $\underline{\delta }$ is big enough, no player wants to play off-path

Suppose on path:

$$U_{\text{Cooperate}}^j=(1-\delta )\sum _{t=0}{\delta }^t{u}^j(a)$$

Since we normalize with $(1-\delta )$, thus $U_{\text{Cooperate}}^j=u^j(a)$.

If off-path:

If player $j$ decides to off-path at $t=0$, then he would get a deviation utility $\tilde{u}$, then he gets $V_{\min \max }^j$ forever.

Thus,

$$U_{Deviate}^j=(1-\delta )\underset{a^{{}^{\prime }j}}{\max }{u}^j(a^{{}^{\prime }j},a^{-j})+\delta V_{\min \max }^j$$

Only when $U_{Coo}^j\ge U_{Dev}^j$, $j$ won’t have incentive to deviate, thus

$$u^j(a)\ge (1-\delta )\underset{a^{{}^{\prime }j}}{\max }{u}^j(a^{{}^{\prime }j},a^{-j})+\delta V_{\min \max }^j$$

We could get

$$\underline{\delta }\ge 1-\frac{u^j(a)-V_{\min \max }^j}{{\max }_{a^{{}^{\prime }j}}{u}^j(a^{{}^{\prime }j},a^{-j})-V_{\min \max }^j}$$

Since $u^j(a)>V_{\min \max }^j$ (because people are rational), we have $\underline{\delta }<1$.

Thus we pick the highest $\underline{\delta }$ among all $j$, where $\delta ={\max }_{j\in 1,\dots ,n}{\underline{\delta }}_j$

The conclusion is, if we let $\delta \ge {\max }_{j\in 1,\dots ,n}{\underline{\delta }}_j$, then nobody wants to play off-path, everyone would play $a$.