Folk Theorem -game Theory

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 ${\displaystyle \delta \to 1}$), then repeated interaction can result in virtually any average payoff in an SPE equilibrium.^[3] "Virtually any" is here technically defined as "feasible" and "individually rational".

For example, in the one-shot Prisoner's Dilemma, both players cooperating is not a Nash equilibrium. The only Nash equilibrium is that both players defect, which is also a mutual minmax profile. One folk theorem says that, in the infinitely repeated version of the game, provided players are sufficiently patient, there is a Nash equilibrium such that both players cooperate on the equilibrium path. But if the game is only repeated a known finite number of times, it can be determined by using backward induction that both players will play the one-shot Nash equilibrium in each period, i.e. they will defect each time.

Setup and definitions

We start with a basic game, also known as the stage game, which is a n-player game. In this game, each player has finitely many actions to choose from, and they make their choices simultaneously and without knowledge of the other player's choices. The collective choices of the players leads to a payoff profile, i.e. to a payoff for each of the players. The mapping from collective choices to payoff profiles is known to the players, and each player aims to maximize their payoff. If the collective choice is denoted by x, the payoff that player i receives, also known as player i's utility, will be denoted by ${\displaystyle u_{i}(x)}$.

We then consider a repetition of this stage game, finitely or infinitely many times. In each repetition, each player chooses one of their stage game options, and when making that choice, they may take into account the choices of the other players in the prior iterations. In this repeated game, a strategy for one of the players is a deterministic rule that specifies the player's choice in each iteration of the stage game, based on all other player's choices in the prior iterations. A choice of strategy for each of the players is a strategy profile, and it leads to a payout profile for the repeated game. There are a number of different ways such a strategy profile can be translated into a payout profile, outlined below.

Any Nash equilibrium payoff profile of a repeated game must satisfy two properties:

1. Individual rationality: the payoff must weakly dominate the minmax payoff profile of the constituent stage game. That is, the equilibrium payoff of each player must be at least as large as the minmax payoff of that player. This is because a player achieving less than his minmax payoff always has incentive to deviate by simply playing his minmax strategy at every history.

2. Feasibility: the payoff must be a convex combination of possible payoff profiles of the stage game. This is because the payoff in a repeated game is just a weighted average of payoffs in the basic games.

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.

There are various folk theorems; some relate to finitely-repeated games while others relate to infinitely-repeated games.^[4]

Infinitely-repeated games without discounting

In the undiscounted model, the players are patient. They don't differentiate between utilities in different time periods. Hence, their utility in the repeated game is represented by the sum of utilities in the basic games.

When the game is infinite, a common model for the utility in the infinitely-repeated game is the limit inferior of mean utility: If the game results in a path of outcomes ${\displaystyle x_{t}}$, where ${\displaystyle x_{t}}$ denotes the collective choices of the players at iteration t (t=0,1,2,...), player i's utility is defined as

${\displaystyle U_{i}=\liminf _{T\to \infty }{\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t}),}$

where ${\displaystyle u_{i}}$ is the basic-game utility function of player i.

An infinitely-repeated game without discounting is often called a "supergame".

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.

The proof employs what is called a grim^[5] or grim trigger^[6] strategy. All players start by playing the prescribed action and continue to do so until someone deviates. If player i deviates, all other players switch to picking the action which minmaxes player i forever after. The one-stage gain from deviation contributes 0 to the total utility of player i. The utility of a deviating player cannot be higher than his minmax payoff. Hence all players stay on the intended path and this is indeed a Nash equilibrium.

Infinitely-repeated games with discounting

Assume that the payoff of a player in an infinitely repeated game is given by the average discounted criterion with discount factor 0 < δ < 1:

${\displaystyle U_{i}=(1-\delta )\sum _{t\geq 0}\delta ^{t}u_{i}(x_{t}),}$

The discount factor indicates how patient the players are.

The folk theorem in this case requires that the payoff profile in the repeated game strictly dominates the minmax payoff profile (i.e., each player receives strictly more than the minmax payoff).

Let a be a strategy profile of the stage game with payoff profile u which strictly dominates the minmax payoff profile. One can define a Nash equilibrium of the game with u as resulting payoff profile as follows:

1. All players start by playing a and continue to play a if no deviation occurs.

2. If any one player, say player i, deviated, play the strategy profile m which minmaxes i forever after.

3. Ignore multilateral deviations.

If player i gets ε more than his minmax payoff each stage by following 1, then the potential loss from punishment is

${\displaystyle {\frac {1}{1-\delta }}\varepsilon .}$

If δ is close to 1, this outweighs any finite one-stage gain, making the strategy a Nash equilibrium.

An alternative statement of this folk theorem^[4] allows the equilibrium payoff profile u to be any individually rational feasible payoff profile; it only requires there exist an individually rational feasible payoff profile that strictly dominates the minmax payoff profile. 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).

Finitely-repeated games without discount

Assume that the payoff of player i in a game that is repeated T times is given by a simple arithmetic mean:

${\displaystyle U_{i}={\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t})}$

A folk theorem for this case has the following additional requirement:^[4]

In the basic game, for every player i, there is a Nash-equilibrium ${\displaystyle E_{i}}$ that is strictly better, for i, then his minmax payoff.

This requirement is stronger than the requirement for discounted infinite games, which is in turn stronger than the requirement for undiscounted infinite games.

This requirement is needed because of the last step. 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). Then, there is no way to punish that player.

On the other hand, if for every player there is a basic equilibrium which is strictly better than minmax, a repeated-game equilibrium can be constructed in two phases:

1. In the first phase, the players alternate strategies in the required frequencies to approximate the desired payoff profile.
2. In the last phase, the players play the preferred equilibrium of each of the players in turn.

In the last phase, no player deviates since the actions are already a basic-game equilibrium. If an agent deviates in the first phase, he can be punished by minmaxing him in the last phase. If the game is sufficiently long, the effect of the last phase is negligible, so the equilibrium payoff approaches the desired profile.

Applications

Folk theorems can be applied to a diverse number of fields. For example:

• Anthropology: in a community where all behavior is well known, and where members of the community know that they will continue to have to deal with each other, then any pattern of behavior (traditions, taboos, etc.) may be sustained by social norms so long as the individuals of the community are better off remaining in the community than they would be leaving the community (the minimax condition).
• International politics: agreements between countries cannot be effectively enforced. They are kept, however, because relations between countries are long-term and countries can use "minimax strategies" against each other. This possibility often depends on the discount factor of the relevant countries. If a country is very impatient (pays little attention to future outcomes), then it may be difficult to punish it (or punish it in a credible way).^[5]

On the other hand, MIT economist Franklin Fisher has noted that the folk theorem is not a positive theory.^[13] In considering, for instance, oligopoly behavior, the folk theorem does not tell the economist what firms will do, but rather that cost and demand functions are not sufficient for a general theory of oligopoly, and the economists must include the context within which oligopolies operate in their 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.

Summary of folk theorems

The following table compares various folk theorems in several aspects:

• Horizon – whether the stage game is repeated finitely or infinitely many times.
• Utilities – how the utility of a player in the repeated game is determined from the player's utilities in the stage game iterations.
• Conditions on G (the stage game) – whether there are any technical conditions that should hold in the one-shot game in order for the theorem to work.
• Conditions on x (the target payoff vector of the repeated game) – whether the theorem works for any individually rational and feasible payoff vector, or only on a subset of these vectors.
• Equilibrium type – if all conditions are met, what kind of equilibrium is guaranteed by the theorem – Nash or Subgame-perfect?
• Punishment type – what kind of punishment strategy is used to deter players from deviating?

Published by	Horizon	Utilities	Conditions on G	Conditions on x	Guarantee	Equilibrium type	Punishment type
Benoit& Krishna[15]	Finite (${\displaystyle T}$)	Arithmetic mean	For every player there is an equilibrium payoff strictly better than minimax.	None	For all ${\displaystyle \varepsilon >0}$ there is ${\displaystyle T_{0}\in \mathbb {N} }$ such that, if ${\displaystyle T\geq T_{0}}$, for every ${\displaystyle x}$ there is equilibrium with payoff ${\displaystyle \varepsilon }$-close to ${\displaystyle x}$.	Nash
Aumann& Shapley[5]	Infinite	Limit of means	None	None	Payoff exactly ${\displaystyle x}$.	Nash	Grim
Aumann& Shapley[5] and Rubinstein[8][16]	Infinite	Limit of means	None	None	Payoff exactly ${\displaystyle x}$.	Subgame-perfect	Limited-time punishment.[7]:146–149
Rubinstein[6]	Infinite	Overtaking	None	Strictly above minimax.	Single outcome or a periodic sequence.	Subgame-perfect	Punishing non-punishers.[7]:149–150
Rubinstein[8]	Infinite	Limit of means	None	Pareto-efficient and weakly-coalition-individually-rational[10]	None	Coalition-subgame-perfect
Rubinstein[8]	Infinite	Overtaking	None	Pareto-efficient and strongly-coalition-individually-rational[12]	None	Coalition-Nash
Fudenberg& Maskin[17]	Infinite	Sum with discount ${\displaystyle \delta }$	Correlated mixed strategies are allowed.	Strictly above minimax.	When ${\displaystyle \delta }$ is sufficiently near 1, there is an equilibrium with payoff exactly ${\displaystyle x}$.	Nash	Grim
Fudenberg& Maskin[17]	Infinite	Sum with discount ${\displaystyle \delta }$	Only pure strategies are allowed.	Strictly above minimax.	For all ${\displaystyle \varepsilon >0}$ there is ${\displaystyle \delta _{0}<1}$ such that, if ${\displaystyle \delta \geq \delta _{0}}$, for every ${\displaystyle x}$ there is an equilibrium with payoff ${\displaystyle \varepsilon }$-close to ${\displaystyle x}$.	Nash	Grim punishment.
Friedman (1971, 1977)	Infinite	Sum with discount ${\displaystyle \delta }$	Correlated mixed strategies are allowed.	Strictly above a Nash-equilibrium in G.	When ${\displaystyle \delta }$ is sufficiently near 1, there is equilibrium with payoff exactly ${\displaystyle x}$.	Subgame-perfect	Grim punishment using the Nash-equilibrium.
Fudenberg& Maskin[17]	Infinite	Sum with discount ${\displaystyle \delta }$	Two players	Strictly above minimax.	For all ${\displaystyle x}$ there is ${\displaystyle \delta _{0}<1}$ such that, if ${\displaystyle \delta \geq \delta _{0}}$, there is equilibrium with payoff exactly ${\displaystyle x}$.	Subgame-perfect	Limited-time punishment.
Fudenberg& Maskin[17]	Infinite	Sum with discount ${\displaystyle \delta }$	The IR feasible space is full-dimensional.[18]	Strictly above minimax.	For all ${\displaystyle x}$ there is ${\displaystyle \delta _{0}<1}$ such that, if ${\displaystyle \delta \geq \delta _{0}}$, there is equilibrium with payoff exactly ${\displaystyle x}$.	Subgame-perfect	Rewarding the punishers.[7]:150–153

Notes

References

• Friedman, J. (1971). "A non-cooperative equilibrium for supergames". Review of Economic Studies. 38 (1): 1–12. doi:10.2307/2296617. JSTOR 2296617.
• Ichiishi, Tatsuro (1997). Microeconomic Theory. Oxford: Blackwell. pp. 263–269. ISBN 1-57718-037-2.
• Mas-Colell, A.; Whinston, M.; Green, J. (1995). Microeconomic Theory. New York: Oxford University Press. ISBN 0-19-507340-1.
• Ratliff, J. (1996). "A Folk Theorem Sampler" (PDF). A set of introductory notes to the Folk Theorem.