Folk theorem (game theory): Difference between revisions
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 115: | Line 115: | ||
| Aumann&Shapley<ref name=AumannShapley94>{{Cite journal|doi=10.1007/978-1-4612-2648-2_1|chapter=Long-Term Competition—A Game-Theoretic Analysis|title=Essays in Game Theory|pages=1|year=1994|last1=Aumann|first1=Robert J.|last2=Shapley|first2=Lloyd S.|isbn=978-1-4612-7621-0}}</ref> || Infinite || Limit of means || None || None || Nash equilibrium with payoff exactly <math>x</math>. || "Grim" punishment: punishment from point of defection to infinity. |
| Aumann&Shapley<ref name=AumannShapley94>{{Cite journal|doi=10.1007/978-1-4612-2648-2_1|chapter=Long-Term Competition—A Game-Theoretic Analysis|title=Essays in Game Theory|pages=1|year=1994|last1=Aumann|first1=Robert J.|last2=Shapley|first2=Lloyd S.|isbn=978-1-4612-7621-0}}</ref> || Infinite || Limit of means || None || None || Nash equilibrium with payoff exactly <math>x</math>. || "Grim" punishment: punishment from point of defection to infinity. |
||
|- |
|- |
||
| Aumann&Shapley<ref name=AumannShapley94/> || Infinite || Limit of means || None || None || Subgame-perfect Nash equilibrium with payoff exactly <math>x</math>. || Intricate punishment scheme; including punishing the non-punishers. |
| Aumann&Shapley<ref name=AumannShapley94/> and Rubinstein<ref name=Rubinstein>{{cite journal|doi= 10.1007/978-1-4612-2648-2_2|chapter= Equilibrium in Supergames|title= Essays in Game Theory|pages= 17|year= 1994|last1= Rubinstein|first1= Ariel|isbn= 978-1-4612-7621-0}}</ref> || Infinite || Limit of means || None || None || Subgame-perfect Nash equilibrium with payoff exactly <math>x</math>. || Intricate punishment scheme; including punishing the non-punishers. |
||
|} |
|} |
||
Revision as of 20:12, 14 November 2015
Folk theorem | |
---|---|
Solution concept in game theory | |
Relationship | |
Subset of | Minimax, Nash Equilibrium |
Significance | |
Proposed by | various, notably Ariel Rubinstein |
Used for | repeated games |
Example | Repeated prisoner's dilemma |
In game theory, folk theorems are a class of theorems about possible Nash equilibrium payoff profiles in repeated games (Friedman 1971).[1] Folk theorems are motivated by a puzzling fact: in many cases, game theory predicts that rational people will act selfishly, since selfishness is the only Nash equilibrium in the game. However, in reality, people act cooperatively. The explanation provided by folk theorems is that, in repeated games, there are many Nash equilibria which are substantially different than in the one-shot game. The fact that the game is repeated allows the players to agree on certain sequences of actions, and punish the players that deviate from that sequence.
For example, in the one-shot Prisoner's Dilemma, both players cooperating is not a Nash equilibrium (if at least one of them is rational). The only Nash equilibrium (if both are rational) is given by both players defecting, 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.
Preliminaries
Any Nash equilibrium payoff in a repeated game must satisfy two properties:
1. Individual rationality (IR): the payoff must weakly dominate the minmax payoff profile of the constituent stage game. I.e, 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 (are different in each folk theorem), every payoff that is both IR and feasible can be realized as a Nash equilibrium payoff profile in the repeated game.
There are various folk theorems, some relate to finitely-repeated games while others relate to infinitely-repeated games. [2]
Infinitely-repeated games with no discount
When players are patient, their utility in the infinitely-repeated game is modeled by the limit of the means, in case it exists. If a strategy profile results in the path of histories {ht}, player i's payoff is
where ui is player i's utility in the basic game.
The folk theorem in this case is very simple and contains no pre-conditions: every IR feasible payoff profile in the basic game is an equilibrium payoff profile in the repeated game.
The proof employs what is called a grim trigger strategy (Rubinstein 1979). All players start by playing the prescribed action and continue to do so until someone deviates. If player i deviates, all players switch to the strategy which minmaxes player i forever after. The one-stage gain from deviation contributes 0 to the total utility of the player. The utility of a deviating player cannot be higher than his minmax payoff. Hence all players stay on the intended path.
Infinitely-repeated games with discount
Assume that the payoff of a player in an infinitely repeated game is given by the average discounted criterion with discount factor 0<δ<1:
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 pure strategy profile with payoff profile x which strictly dominates the minmax payoff profile. One can define a Nash equilibrium with x 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
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[2] allows the equilibrium payoff profile x to be any IR feasible payoff profile; it only requires there exists an IR feasible payoff profile x, which strictly dominates the minmax payoff profile. Then, the folk theorem guarantees that it is possible to approach x in equilibirum to any desired precision (for every ε there exists a Nash equilibrium where the payoff profile is a distance ε away from x).
Infinitely-repeated games with discount - Subgame perfection
The above Nash equilibrium need not be subgame perfect. The threat of punishment may not be credible. Under the additional assumption that the set of feasible payoff profiles is full dimensional and the minmax profile lies in its interior, the argument can be strengthened to achieve subgame perfection 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 for N periods. (Choose N and δ large enough so that no player has incentive to deviate from phase 1.)
- 3. If no players deviated from phase 2, all player j ≠ i gets rewarded ε above j's minmax forever after, while player i continues receiving his minmax. (Full-dimensionality and the interior assumption is needed here.)
- 4. If player j deviated from phase 2, all players restart phase 2 with j as target.
- 5. Ignore multilateral deviations.
Player j ≠ i now has no incentive to deviate from the punishment phase 2. This proves the subgame perfect folk theorem.
Finitely-repeated games without discount
Assume that the payoff of a player in an finitely repeated game is given by a simple arithmetic mean:
A folk theorem for this case has the following additional requirement: [2]
- In the basic game, for every player i, there is a Nash-equilibrium 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:
- In the first phase, the players alternate strategies in the required frequencies to approximate the desired payoff profile.
- 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). As specific historic example, consider the relations between North Vietnam and the USA during the Vietnam war.[3]
On the other hand, MIT economist Franklin Fisher has noted that the folk theorem is not a positive theory.[4] 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.[4]
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.[5] 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 the different folk theorems in several aspects:
- Horizon - whether game is repeated Finitely or Infinitely many times.
- Utilities - whether the utility of a player in the repeated game is assumed to be an arithmetic mean or a discounted sum.
- Conditions on G (the basic 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) - whether the theorem works for any IR and feasible payoff vector, or only on a subset of these vectors.
- Equilibrium guarantee - if all conditions are met, what kind of Nash equilibrium is guaranteed by the theorem?
Published by | Horizon | Utilities | Conditions on G | Conditions on x | Equilibrium guarantee | Comments |
---|---|---|---|---|---|---|
Benoit&Krishna[6] | Finite () | Arithmetic mean | For every player there is an equilibrium payoff strictly better than minimax. | None | For all there is such that, if , for every there is an equilibrium with payoff -close to . | |
Aumann&Shapley[3] | Infinite | Limit of means | None | None | Nash equilibrium with payoff exactly . | "Grim" punishment: punishment from point of defection to infinity. |
Aumann&Shapley[3] and Rubinstein[7] | Infinite | Limit of means | None | None | Subgame-perfect Nash equilibrium with payoff exactly . | Intricate punishment scheme; including punishing the non-punishers. |
Notes
- ^ In mathematics, the term folk theorem refers generally to any theorem that is believed and discussed, but has not been published. In order that the name of the theorem be more descriptive, Roger Myerson has recommended the phrase general feasibility theorem in the place of folk theorem for describing theorems which are of this class. See Myerson, Roger B. Game Theory, Analysis of conflict, Cambridge, Harvard University Press (1991)
- ^ a b c Game Theory. Cambridge University Press. 2013. pp. 176–180. ISBN 9781107005488.
{{cite book}}
: Unknown parameter|authors=
ignored (help) - ^ a b c Aumann, Robert J.; Shapley, Lloyd S. (1994). "Essays in Game Theory": 1. doi:10.1007/978-1-4612-2648-2_1. ISBN 978-1-4612-7621-0.
{{cite journal}}
:|chapter=
ignored (help); Cite journal requires|journal=
(help) - ^ a b Fisher, Franklin M. Games Economists Play: A Noncooperative View The RAND Journal of Economics, Vol. 20, No. 1. (Spring, 1989), pp. 113–124, this particular discussion is on page 118
- ^ Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, and Christos Papadimitriou (2007). "The Myth of the Folk Theorem" (PDF).
{{cite web}}
: CS1 maint: multiple names: authors list (link) - ^ Benoit, Jean-Pierre; Krishna, Vijay (1985). "Finitely Repeated Games". Econometrica. 53 (4): 905. doi:10.2307/1912660. JSTOR 1912660.
- ^ Rubinstein, Ariel (1994). "Essays in Game Theory": 17. doi:10.1007/978-1-4612-2648-2_2. ISBN 978-1-4612-7621-0.
{{cite journal}}
:|chapter=
ignored (help); Cite journal requires|journal=
(help)
References
- Friedman, J. (1971), "A non-cooperative equilibrium for supergames", Review of Economic Studies, 38 (1): 1–12, doi:10.2307/2296617, JSTOR 2296617.
- Rubinstein, Ariel (1979), "Equilibrium in Supergames with the Overtaking Criterion", Journal of Economic Theory, 21: 1–9, doi:10.1016/0022-0531(79)90002-4
- Mas-Colell, A., Whinston, M and Green, J. (1995) Microeconomic Theory, Oxford University Press, New York (readable; suitable for advanced undergraduates.)
- Tirole, J. (1988) The Theory of Industrial Organization, MIT Press, Cambridge MA (An organized introduction to industrial organization)
- Ratliff, J. (1996). A Folk Theorem Sampler. A set of introductory notes to the Folk Theorem.