Repeated game

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Finitely vs infinitely repeated games[edit]

Repeated games may be broadly divided into two classes, depending on the horizon. The horizon is the player's belief about the number of repetitions of the stage game, and may be finite or infinite. The horizon is infinite in infinitely repeated games, so players in this type of game can expect to play indefinitely. By contrast, the horizon is finite in finitely repeated games, so players expect the game to terminate after playing the stage game some number of times. Note that for a game with an infinite horizon, the stage game will not necessarily be repeated an infinite number of times. A game repeated a finite number of times may be regarded as having an infinite horizon if the players in the game do not know how many times the game will be repeated. The results in these two cases are very dissimilar. The difference in strategies for finite versus infinite horizon games is a hotly debated topic, and many game theorists have differing views regarding it.

Infinitely repeated games[edit]

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 :

  • Limit of means - If the game results in a path of outcomes and player i has the basic-game utility function , player i's utility is:
  • Discounting - If player i's valuation of the game diminishes with time depending on a discount factor , then player i's utility is:

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[edit]

As explained earlier, finite games can be divided into two broad classes. In the first class of finitely repeated games where the time period is fixed and known, it is optimal to play the Nash strategy of the stage game in all periods. When the Nash equilibrium payoff is equal to the minmax payoff, then the player has no reason to stick to a socially optimum strategy and is free to play a selfish strategy throughout, since the punishment cannot affect him (being equal to the minmax payoff). This deviation to a selfish Nash equilibrium strategy is explained by the Chainstore paradox. In the second class of finitely repeated games, the time period is not fixed and known. Because the time period is indeterminate, backward induction is not possible, so these games are treated as if they were infinitely repeated. Finitely repeated games can have (repeated game) subgame perfect Nash equilibrium when the stage game has more than one Nash equilibrium.

Solving repeated games[edit]

In general, repeated game 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.

Incomplete information[edit]

Repeated games can include incomplete information. Repeated games with incomplete information were pioneered by Aumann and Maschler.[1] 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.[2]

References[edit]

  1. ^ Aumann, R. J.; Maschler, M. (1995). Repeated Games with Incomplete Information. Cambridge London: MIT Press. 
  2. ^ 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. 
  • Fudenberg, Drew; Tirole, Jean (1991). Game Theory. Cambridge: MIT Press. ISBN 0-262-06141-4. 
  • Mailath, G. & Samuelson, L. (2006). Repeated games and reputations: long-run relationships. New York: Oxford University Press. ISBN 0-19-530079-3. 
  • Osborne, Martin J.; Rubinstein, Ariel (1994). A Course in Game Theory. Cambridge: MIT Press. ISBN 0-262-15041-7. 
  • Sorin, Sylvain (2002). A First Course on Zero-Sum Repeated Games. Berlin: Springer. ISBN 3-540-43028-8. 

External links[edit]