Repeated game

Last updated

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game (called a stage 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.

Contents

Finitely vs infinitely repeated games

Repeated games may be broadly divided into two classes, finite and infinite, depending on how long the game is being played for.

Even if the game being played in each round is identical, repeating that game a finite or an infinite number of times can, in general, lead to very different outcomes (equilibria), as well as very different optimal strategies.

Infinitely repeated games

The most widely studied repeated games are games that are repeated an infinite number of times. In iterated prisoner's dilemma games, it is found that the preferred strategy is not to play a Nash strategy of the stage game, but to cooperate and play a socially optimum strategy. An essential part of strategies in infinitely repeated game is punishing players who deviate from this cooperative strategy. The punishment may be playing a strategy which leads to reduced payoff to both players for the rest of the game (called a trigger strategy). A player may normally choose to act selfishly to increase their own reward rather than play the socially optimum strategy. However, if it is known that the other player is following a trigger strategy, then the player expects to receive reduced payoffs in the future if they deviate at this stage. An effective trigger strategy ensures that cooperating has more utility to the player than acting selfishly now and facing the other player's punishment in the future.

There are many results in theorems which deal with how to achieve and maintain a socially optimal equilibrium in repeated games. These results are collectively called "Folk Theorems". An important feature of a repeated game is the way in which a player's preferences may be modeled. There are many different ways in which a preference relation may be modeled in an infinitely repeated game, but two key ones are :

For sufficiently patient players (e.g. those with high enough values of ), it can be proved that every strategy that has a payoff greater than the minmax payoff can be a Nash equilibrium - a very large set of strategies.

Finitely repeated games

Repeated games allow for the study of the interaction between immediate gains and long-term incentives. A finitely repeated game is a game in which the same one-shot stage game is played repeatedly over a number of discrete time periods, or rounds. Each time period is indexed by 0 < t ≤ T where T is the total number of periods. A player's final payoff is the sum of their payoffs from each round. [1]

In each period of a finite game, players execute a certain amount of action. These actions lead to a stage-game payoff for the players. The stage game can be denoted by {A, u} where A = A1 * A2 *...* An is the set of profiles and ui(a) is player i's stage-game payoff when profile a is played. The stage game is played in each period. Additionally, we assume that in each period t, the players have observed the history of play, or the sequence of action profiles, from the first period through period t-1. The payoff of the entire game is the sum of the stage-game payoffs in periods 1 through T. Sometimes, one should assume that all players discount the future, in which case we include a discount factor in the payoff specification. [2]

For those repeated games with a fixed and known number of time periods, if the stage game has a unique Nash equilibrium, then the repeated game has a unique subgame perfect Nash equilibrium strategy profile of playing the stage game equilibrium in each round. This can be deduced through backward induction. The unique stage game Nash equilibrium must be played in the last round regardless of what happened in earlier rounds. Knowing this, players have no incentive to deviate from the unique stage game Nash equilibrium in the second-to-last round, and so on this logic is applied back to the first round of the game. [3] This ‘unraveling’ of a game from its endpoint can be observed in the Chainstore paradox.

If the stage game has more than one Nash equilibrium, the repeated game may have multiple subgame perfect Nash equilibria. While a Nash equilibrium must be played in the last round, the presence of multiple equilibria introduces the possibility of reward and punishment strategies that can be used to support deviation from stage game Nash equilibria in earlier rounds. [3]

Finitely repeated games with an unknown or indeterminate number of time periods, on the other hand, are regarded as if they were an infinitely repeated game. It is not possible to apply backward induction to these games.

Examples of cooperation in finitely repeated games

XYZ
A5 , 41, 12 , 5
B1, 13 , 21, 1

Example 1: Two-Stage Repeated Game with Multiple Nash Equilibria

Example 1 shows a two-stage repeated game with multiple pure strategy Nash equilibria. Because these equilibria differ markedly in terms of payoffs for Player 2, Player 1 can propose a strategy over multiple stages of the game that incorporates the possibility for punishment or reward for Player 2. For example, Player 1 might propose that they play (A, X) in the first round. If Player 2 complies in round one, Player 1 will reward them by playing the equilibrium (A, Z) in round two, yielding a total payoff over two rounds of (7, 9).

If Player 2 deviates to (A, Z) in round one instead of playing the agreed-upon (A, X), Player 1 can threaten to punish them by playing the (B, Y) equilibrium in round two. This latter situation yields payoff (5, 7), leaving both players worse off.

In this way, the threat of punishment in a future round incentivizes a collaborative, non-equilibrium strategy in the first round. Because the final round of any finitely repeated game, by its very nature, removes the threat of future punishment, the optimal strategy in the last round will always be one of the game's equilibria. It is the payoff differential between equilibria in the game represented in Example 1 that makes a punishment/reward strategy viable (for more on the influence of punishment and reward on game strategy, see 'Public Goods Game with Punishment and for Reward').

MNO
C5 , 41, 10, 5
D1, 13 , 21, 1

Example 2: Two-Stage Repeated Game with Unique Nash Equilibrium

Example 2 shows a two-stage repeated game with a unique Nash equilibrium. Because there is only one equilibrium here, there is no mechanism for either player to threaten punishment or promise reward in the game's second round. As such, the only strategy that can be supported as a subgame perfect Nash equilibrium is that of playing the game's unique Nash equilibrium strategy (D, N) every round. In this case, that means playing (D, N) each stage for two stages (n=2), but it would be true for any finite number of stages n. [4] To interpret: this result means that the very presence of a known, finite time horizon sabotages cooperation in every single round of the game. Cooperation in iterated games is only possible when the number of rounds is infinite or unknown.

Solving repeated games

In general, repeated games are easily solved using strategies provided by folk theorems. Complex repeated games can be solved using various techniques most of which rely heavily on linear algebra and the concepts expressed in fictitious play. It may be deducted that you can determine the characterization of equilibrium payoffs in infinitely repeated games. Through alternation between two payoffs, say a and f, the average payoff profile may be a weighted average between a and f.

Incomplete information

Repeated games can include incomplete information. Repeated games with incomplete information were pioneered by Aumann and Maschler. [5] While it is easier to treat a situation where one player is informed and the other not, and when information received by each player is independent, it is possible to deal with zero-sum games with incomplete information on both sides and signals that are not independent. [6]

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

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:

Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backwards until one has determined the best action for every possible situation at every point in time. It was first used by Zermelo in 1913, to prove that chess has pure optimal strategies.

In game theory, folk theorems are a class of theorems describing an abundance of Nash equilibrium payoff profiles in repeated games. 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.

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 at any point in the game, the players' behavior from that point onward should represent a Nash equilibrium of the continuation game, no matter what happened before. Every finite extensive game with perfect recall has a subgame perfect equilibrium.

Quantal response equilibrium (QRE) is a solution concept in game theory. First introduced by Richard McKelvey and Thomas Palfrey, it provides an equilibrium notion with bounded rationality. QRE is not an equilibrium refinement, and it can give significantly different results from Nash equilibrium. QRE is only defined for games with discrete strategies, although there are continuous-strategy analogues.

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.

In game theory, a stochastic game, introduced by Lloyd Shapley in the early 1950s, is a dynamic game with probabilistic transitions played by one or more players. The game is played in a sequence of stages. At the beginning of each stage the game is in some state. The players select actions and each player receives a payoff that depends on the current state and the chosen actions. The game then moves to a new random state whose distribution depends on the previous state and the actions chosen by the players. The procedure is repeated at the new state and play continues for a finite or infinite number of stages. The total payoff to a player is often taken to be the discounted sum of the stage payoffs or the limit inferior of the averages of the stage payoffs.

A Markov perfect equilibrium is an equilibrium concept in game theory. It has been used in analyses of industrial organization, macroeconomics, and political economy. It is a refinement of the concept of subgame perfect equilibrium to extensive form games for which a pay-off relevant state space can be identified. The term appeared in publications starting about 1988 in the work of economists Jean Tirole and Eric Maskin.

Jean-François Mertens

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

Mertens stability is a solution concept used to predict the outcome of a non-cooperative game. A tentative definition of stability was proposed by Elon Kohlberg and Jean-François Mertens for games with finite numbers of players and strategies. Later, Mertens proposed a stronger definition that was elaborated further by Srihari Govindan and Mertens. This solution concept is now called Mertens stability, or just stability.

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

  1. Knight, Vince. "Finitely Repeated Games". Game Theory. Retrieved 12/6/17.Check date values in: |access-date= (help)
  2. Waston, Joel (2013). Strategy: An Introduction to Game Theory. New York, London: W.W Norton and Company. p. 292. ISBN   978-0-393-91838-0.
  3. 1 2 Benoit, J.P. & Krishna, V. (1985). "Finitely Repeated Games". Econometrica: 905–922.CS1 maint: multiple names: authors list (link)
  4. Levin, Jonathan (May 2006). ""Repeated Games I: Perfect Monitoring"" (PDF). www.stanford.edu. Retrieved December 12, 2017.
  5. Aumann, R. J.; Maschler, M. (1995). Repeated Games with Incomplete Information. Cambridge London: MIT Press.
  6. Mertens, J.-F. (1987). "Repeated Games". Proceedings of the International Congress of Mathematicians, Berkeley 1986. Providence: American Mathematical Society. pp. 1528–1577. ISBN   0-8218-0110-4.