Folk theorem (game theory)

Last updated

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]

Contents

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. [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 .

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 , where denotes the collective choices of the players at iteration t (t=0,1,2,...), player i's utility is defined as

where 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.

Subgame perfection

The above Nash equilibrium is not always subgame perfect. If punishment is costly for the punishers, the threat of punishment is not credible.

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. After that, the other players should return to the equilibrium path.

The limit-of-means criterion ensures that any finite-time punishment has no effect on the final outcome. Hence, limited-time punishment is a subgame-perfect equilibrium.

Overtaking

Some authors claim that the limit-of-means criterion is unrealistic, because it implies that utilities in any finite time-span contribute 0 to the total utility. However, if the utilities in any finite time-span contribute a positive value, and the value is undiscounted, then it is impossible to attribute a finite numeric utility to an infinite outcome sequence. A possible solution to this problem is that, instead of defining a numeric utility for each infinite outcome sequence, we just define the preference relation between two infinite sequences. We say that agent (strictly) prefers the sequence of outcomes over the sequence , if: [6] [7] :139 [8]

For example, consider the sequences and . According to the limit-of-means criterion, they provide the same utility to player i, but according to the overtaking criterion, is better than for player i. See overtaking criterion for more information.

The folk theorems with the overtaking criterion are slightly weaker than with the limit-of-means criterion. Only outcomes that are strictly individually rational, can be attained in Nash equilibrium. This is because, if an agent deviates, he gains in the short run, and this gain can be wiped out only if the punishment gives the deviator strictly less utility than the agreement path. The following folk theorems are known for the overtaking criterion:

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:

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 preated 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

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).

Subgame perfection

Attaining a subgame perfect equilibrium in discounted games is more difficult than in undiscounted games. The cost of punishment does not vanish (as with the limit-of-means criterion). It is not always possible to punish the non-punishers endlessly (as with the overtaking criterion) since the discount factor makes punishments far away in the future irrelevant for the present. Hence, a different approach is needed: the punishers should be rewarded.

This requires an additional assumption, that the set of feasible payoff profiles is full dimensional and the min-max profile lies in its interior. The strategy is 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 ji gets rewarded ε above j's min-max forever after, while player i continues receiving his min-max. (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 ji 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 player i in a game that is repeated T times is given by a simple arithmetic mean:

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 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:

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:

Published byHorizonUtilitiesConditions on GConditions on xGuaranteeEquilibrium typePunishment type
Benoit& Krishna [15] Finite ()Arithmetic meanFor every player there is an equilibrium payoff strictly better than minimax.NoneFor all there is such that, if , for every there is equilibrium with payoff -close to .Nash
Aumann& Shapley [5] InfiniteLimit of meansNoneNonePayoff exactly .NashGrim
Aumann& Shapley [5] and Rubinstein [8] [16] InfiniteLimit of meansNoneNonePayoff exactly .Subgame-perfectLimited-time punishment. [7] :146–149
Rubinstein [6] Infinite Overtaking NoneStrictly above minimax.Single outcome or a periodic sequence.Subgame-perfectPunishing non-punishers. [7] :149–150
Rubinstein [8] InfiniteLimit of meansNonePareto-efficient and weakly-coalition-individually-rational [10] NoneCoalition-subgame-perfect
Rubinstein [8] InfiniteOvertakingNonePareto-efficient and strongly-coalition-individually-rational [12] NoneCoalition-Nash
Fudenberg& Maskin [17] InfiniteSum with discount Correlated mixed strategies are allowed.Strictly above minimax.When is sufficiently near 1, there is an equilibrium with payoff exactly .NashGrim
Fudenberg& Maskin [17] InfiniteSum with discount Only pure strategies are allowed.Strictly above minimax.For all there is such that, if , for every there is an equilibrium with payoff -close to .NashGrim punishment.
Friedman (1971, 1977)InfiniteSum with discount Correlated mixed strategies are allowed.Strictly above a Nash-equilibrium in G.When is sufficiently near 1, there is equilibrium with payoff exactly .Subgame-perfectGrim punishment using the Nash-equilibrium.
Fudenberg& Maskin [17] InfiniteSum with discount Two playersStrictly above minimax.For all there is such that, if , there is equilibrium with payoff exactly .Subgame-perfectLimited-time punishment.
Fudenberg& Maskin [17] InfiniteSum with discount The IR feasible space is full-dimensional. [18] Strictly above minimax.For all there is such that, if , there is equilibrium with payoff exactly .Subgame-perfectRewarding the punishers. [7] :150–153

Notes

  1. In mathematics, the term folk theorem refers generally to any theorem that is believed and discussed, but has not been published. Roger Myerson has recommended the more descriptive term "general feasibility theorem" for the game theory theorems discussed here. See Myerson, Roger B. Game Theory, Analysis of conflict, Cambridge, Harvard University Press (1991)
  2. R. Gibbons (1992). A Primer in Game Theory. Harvester Wheatsheaf. p. 89. ISBN   0-7450-1160-8.CS1 maint: uses authors parameter (link)
  3. Jonathan Levin (2002). "Bargaining and Repeated Games" (PDF).
  4. 1 2 3 Michael Maschler, Eilon Solan & Shmuel Zamir (2013). Game Theory. Cambridge University Press. pp. 176–180. ISBN   978-1-107-00548-8.CS1 maint: uses authors parameter (link)
  5. 1 2 3 4 5 Aumann, Robert J.; Shapley, Lloyd S. (1994). "Long-Term Competition—A Game-Theoretic Analysis". Essays in Game Theory. p. 1. doi:10.1007/978-1-4612-2648-2_1. ISBN   978-1-4612-7621-0.
  6. 1 2 3 4 5 6 Rubinstein, Ariel (1979). "Equilibrium in supergames with the overtaking criterion". Journal of Economic Theory. 21: 1. doi:10.1016/0022-0531(79)90002-4.
  7. 1 2 3 4 5 6 . ISBN   0-262-15041-7. LCCN   94008308. OL   1084491M.Missing or empty |title= (help)
  8. 1 2 3 4 5 6 Rubinstein, A. (1980). "Strong perfect equilibrium in supergames". International Journal of Game Theory. 9: 1. doi:10.1007/BF01784792.
  9. The paper uses the term "strong equilibrium". Here, to prevent ambiguity, the term "coalition equilibrium" is used instead.
  10. 1 2 For every nonempty coalition , there is a strategy of the other players () such that for any strategy played by , the payoff when plays is not [strictly better for all members of ].
  11. In the 1979 paper, Rubinstein claims that an outcome is attainable in strict-stationary-equilibrium if-and-only-if for every player, the outcome is EITHER strictly better than the player's minimax outcome OR the outcome is weakly better than any other outcome the player can unilaterally deviate to. It is not clear how the second option is attainable in a strict equilibrium. In the 1994 book, this claim does not appear.
  12. 1 2 for every nonempty coalition , there is a strategy of the other players () such that for any strategy played by , the payoff is strictly worse for at least one member of .
  13. 1 2 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
  14. Christian Borgs; Jennifer Chayes; Nicole Immorlica; Adam Tauman Kalai; Vahab Mirrokni; Christos Papadimitriou (2007). "The Myth of the Folk Theorem" (PDF).
  15. Benoit, Jean-Pierre; Krishna, Vijay (1985). "Finitely Repeated Games". Econometrica. 53 (4): 905. doi:10.2307/1912660. JSTOR   1912660.
  16. Rubinstein, Ariel (1994). "Equilibrium in Supergames". Essays in Game Theory. p. 17. doi:10.1007/978-1-4612-2648-2_2. ISBN   978-1-4612-7621-0.
  17. 1 2 3 4 Fudenberg, Drew; Maskin, Eric (1986). "The Folk Theorem in Repeated Games with Discounting or with Incomplete Information". Econometrica. 54 (3): 533. CiteSeerX   10.1.1.308.5775 . doi:10.2307/1911307. JSTOR   1911307.
  18. There is a collection of IR feasible outcomes , one per player, such that for every players , and .

Related Research Articles

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy.

In game theory, the centipede game, first introduced by Robert Rosenthal in 1981, is an extensive form game in which two players take turns choosing either to take a slightly larger share of an increasing pot, or to pass the pot to the other player. The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot on the next round, one receives slightly less than if one had taken the pot on this round. Although the traditional centipede game had a limit of 100 rounds, any game with this structure but a different number of rounds is called a centipede game.

Matching pennies is the name for a simple game used in game theory. It is played between two players, Even and Odd. Each player has a penny and must secretly turn the penny to heads or tails. The players then reveal their choices simultaneously. If the pennies match, then Even keeps both pennies, so wins one from Odd. If the pennies do not match Odd keeps both pennies, so receives one from Even.

In game theory, cheap talk is communication between players that does not directly affect the payoffs of the game. Providing and receiving information is free. This is in contrast to signaling in which sending certain messages may be costly for the sender depending on the state of the world.

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others. A player's strategy will determine the action which the player will take at any stage of the game.

Game theory is the branch of mathematics in which games are studied: that is, models describing human behaviour. This is a glossary of some terms of the subject.

In game theory, grim trigger is a trigger strategy for a repeated game.

Solution concept formal rule for predicting how a strategic game will be played

In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

An extensive-form game is a specification of a game in game theory, allowing for the explicit representation of a number of key aspects, like the sequencing of players' possible moves, their choices at every decision point, the information each player has about the other player's moves when they make a decision, and their payoffs for all possible game outcomes. Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature".

In game theory, a Perfect Bayesian Equilibrium (PBE) is an equilibrium concept relevant for dynamic games with incomplete information. It is a refinement of Bayesian Nash equilibrium (BNE). A PBE has two components - strategies and beliefs:

In game theory, strategic dominance occurs when one strategy is better than another strategy for one player, no matter how that player's opponents may play. Many simple games can be solved using dominance. The opposite, intransitivity, occurs in games where one strategy may be better or worse than another strategy for one player, depending on how the player's opponents may play.

In game theory, trembling hand perfect equilibrium is a refinement of Nash equilibrium due to Reinhard Selten. A trembling hand perfect equilibrium is an equilibrium that takes the possibility of off-the-equilibrium play into account by assuming that the players, through a "slip of the hand" or tremble, may choose unintended strategies, albeit with negligible probability.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of his or her current action on the future actions of other players; this impact is sometimes called his or her reputation. Single stage game or single shot game are names for non-repeated games.

In game theory, a correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. It was first discussed by mathematician Robert Aumann in 1974. The idea is that each player chooses their action according to their observation of the value of the same public signal. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from the recommended strategy, the distribution is called a correlated equilibrium.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that if the players played any smaller game that consisted of only one part of the larger game, their behavior would represent a Nash equilibrium of that smaller game. Every finite extensive game with perfect recall has a subgame perfect equilibrium.

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers.

The intuitive criterion (IC) is a technique for equilibrium refinement in signaling games. It aims to reduce possible outcome scenarios by first restricting the type group to types of agents who could obtain higher utility levels by deviating to off-the-equilibrium messages and second by considering in this sub-set of types the types for which the off-the-equilibrium message is not equilibrium dominated.

Jean-François Mertens Belgian game theorist

Jean-François Mertens was a Belgian game theorist and mathematical economist.

The one-shot deviation principle is the principle of optimality of dynamic programming applied to game theory. It says that a strategy profile of a finite extensive-form game is a subgame perfect equilibrium (SPE) if and only if there exist no profitable one-shot deviations for each subgame and every player. In simpler terms, if no player can increase their payoffs by deviating a single decision, or period, from their original strategy, then the strategy that they have chosen is a SPE. As a result, no player can profit from deviating from the strategy for one period and then reverting to the strategy.

The Berge equilibrium is a game theory solution concept named after the mathematician Claude Berge. It is similar to the standard Nash equilibrium, except that it aims to capture a type of altruism rather than purely non-cooperative play. Whereas a Nash equilibrium is a situation in which each player of a strategic game ensures that they personally will receive the highest payoff given other players' strategies, in a Berge equilibrium every player ensures that all other players will receive the highest payoff possible. Although Berge introduced the intuition for this equilibrium notion in 1957, it was only formally defined by Vladislav Iosifovich Zhukovskii in 1985, and it was not in widespread use until half a century after Berge originally developed it.

References