In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games (Friedman 1971).
[1] The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game.
This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it.
Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept: subgame-perfect Nash equilibria rather than Nash equilibria.
[2] The Folk Theorem suggests that if the players are patient enough and far-sighted (i.e. if the discount factor
), then repeated interaction can result in virtually any average payoff in an SPE equilibrium.
We then consider a repetition of this stage game, finitely or infinitely many times.
Any Nash equilibrium payoff profile of a repeated game must satisfy two properties: Folk theorems are partially converse claims: they say that, under certain conditions (which are different in each folk theorem), every payoff profile that is both individually rational and feasible can be realized as a Nash equilibrium payoff profile of the repeated game.
The folk theorem in this case is very simple and contains no pre-conditions: every individually rational and feasible payoff profile in the basic game is a Nash equilibrium payoff profile in the repeated game.
All players start by playing the prescribed action and continue to do so until someone deviates.
The one-stage gain from deviation contributes 0 to the total utility of player i.
A subgame perfect equilibrium requires a slightly more complicated strategy.
[5][7]: 146–149 The punishment should not last forever; it should last only a finite time which is sufficient to wipe out the gains from deviation.
The limit-of-means criterion ensures that any finite-time punishment has no effect on the final outcome.
Only outcomes that are strictly individually rational, can be attained in Nash equilibrium.
One can define a Nash equilibrium of the game with u as resulting payoff profile as follows: If player i gets ε more than his minmax payoff each stage by following 1, then the potential loss from punishment is If δ is close to 1, this outweighs any finite one-stage gain, making the strategy a Nash equilibrium.
Then, the folk theorem guarantees that it is possible to approach u in equilibrium to any desired precision (for every ε there exists a Nash equilibrium where the payoff profile is a distance ε away from u).
In the last step, the only stable outcome is a Nash-equilibrium in the basic game.
Suppose a player i gains nothing from the Nash equilibrium (since it gives him only his minmax payoff).
If the game is sufficiently long, the effect of the last phase is negligible, so the equilibrium payoff approaches the desired profile.
Folk theorems can be applied to a diverse number of fields.
For example: On the other hand, MIT economist Franklin Fisher has noted that the folk theorem is not a positive theory.
[13] In 2007, Borgs et al. proved that, despite the folk theorem, in the general case computing the Nash equilibria for repeated games is not easier than computing the Nash equilibria for one-shot finite games, a problem which lies in the PPAD complexity class.
[14] The practical consequence of this is that no efficient (polynomial-time) algorithm is known that computes the strategies required by folk theorems in the general case.
The following table compares various folk theorems in several aspects: In allusion to the folk theorems for repeated games, some authors have used the term "folk theorem" to refer to results on the set of possible equilibria or equilibrium payoffs in other settings, especially if the results are similar in what equilibrium payoffs they allow.
For instance, Tennenholtz proves a "folk theorem" for program equilibrium.