Folk theorem (game theory)
Encyclopedia
In game theory
, folk theorems are a class of theorems which imply that in repeated game
s, any outcome is a feasible solution concept
, if under that outcome the players' minimax conditions are satisfied. The minimax
condition states that a player will minimize the maximum possible loss which he could face in the game. An outcome is said to be feasible if it satisfies this condition for each player of the game. A repeated game is one in which there is not necessarily a final move, but rather, there is a sequence of rounds, during which the player may gather information and choose moves. An early published example is .
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.
The method for proving folk theorems is actually quite simple. A grim trigger
strategy is a strategy
which punishes an opponent for any deviation from some certain behavior. So, all of the players of the game first must have a certain feasible outcome in mind. Then the players need only adhere to an almost grim trigger strategy under which any deviation from the strategy which will bring about the intended outcome is punished to a degree such that any gains made by the deviator on account of the deviation are exactly cancelled out. Thus, there is no advantage to any player for deviating from the course which will bring out the intended, and arbitrary, outcome, and the game will proceed in exactly the manner to bring about that outcome.
, for example, would be that 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 (tradition
s, taboo
s, 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).
On the other hand, MIT economist Franklin Fisher has noted that the folk theorem is not a positive theory. 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.
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.
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, folk theorems are a class of theorems which imply that in repeated game
Repeated game
In game theory, a repeated game is an extensive form game which consists in some number of repetitions of some base game . The stage game is usually one of the well-studied 2-person games...
s, any outcome is a feasible solution concept
Solution concept
In game theory, a solution concept is a formal rule for predicting how the game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players, therefore predicting the result of the game...
, if under that outcome the players' minimax conditions are satisfied. The minimax
Minimax
Minimax is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case scenario. Alternatively, it can be thought of as maximizing the minimum gain...
condition states that a player will minimize the maximum possible loss which he could face in the game. An outcome is said to be feasible if it satisfies this condition for each player of the game. A repeated game is one in which there is not necessarily a final move, but rather, there is a sequence of rounds, during which the player may gather information and choose moves. An early published example is .
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.
Sketch of proof
A commonly referenced proof of a folk theorem was published in .The method for proving folk theorems is actually quite simple. A grim trigger
Grim trigger
In game theory, grim trigger is a trigger strategy for a repeated game, such as an iterated prisoner's dilemma. Initially, a player using grim trigger will cooperate, but as soon as the opponent defects , the player using grim trigger will defect for the remainder of the iterated game...
strategy is a strategy
Strategy
Strategy, a word of military origin, refers to a plan of action designed to achieve a particular goal. In military usage strategy is distinct from tactics, which are concerned with the conduct of an engagement, while strategy is concerned with how different engagements are linked...
which punishes an opponent for any deviation from some certain behavior. So, all of the players of the game first must have a certain feasible outcome in mind. Then the players need only adhere to an almost grim trigger strategy under which any deviation from the strategy which will bring about the intended outcome is punished to a degree such that any gains made by the deviator on account of the deviation are exactly cancelled out. Thus, there is no advantage to any player for deviating from the course which will bring out the intended, and arbitrary, outcome, and the game will proceed in exactly the manner to bring about that outcome.
Applications
It is possible to apply this class of theorems to a diverse number of fields. An application in anthropologyAnthropology
Anthropology is the study of humanity. It has origins in the humanities, the natural sciences, and the social sciences. The term "anthropology" is from the Greek anthrōpos , "man", understood to mean mankind or humanity, and -logia , "discourse" or "study", and was first used in 1501 by German...
, for example, would be that 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 (tradition
Tradition
A tradition is a ritual, belief or object passed down within a society, still maintained in the present, with origins in the past. Common examples include holidays or impractical but socially meaningful clothes , but the idea has also been applied to social norms such as greetings...
s, taboo
Taboo
A taboo is a strong social prohibition relating to any area of human activity or social custom that is sacred and or forbidden based on moral judgment, religious beliefs and or scientific consensus. Breaking the taboo is usually considered objectionable or abhorrent by society...
s, 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).
On the other hand, MIT economist Franklin Fisher has noted that the folk theorem is not a positive theory. In considering, for instance, oligopoly
Oligopoly
An oligopoly is a market form in which a market or industry is dominated by a small number of sellers . The word is derived, by analogy with "monopoly", from the Greek ὀλίγοι "few" + πόλειν "to sell". Because there are few sellers, each oligopolist is likely to be aware of the actions of the others...
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.
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
PPAD (complexity)
PPAD is a complexity class introduced by Christos Papadimitriou in 1994. PPAD is a subclass of TFNP based on functions that can be shown to be total by a parity argument...
complexity class.