Repeated game

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

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

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 $x_{t}$ and player i has the basic-game utility function $u_{i}$ , player i's utility is:

U_{i}=\lim _{T\to \infty }\inf {\frac {1}{T}}\sum _{t=0}^{T}u_{i}(x_{t})

Discounting - If player i's valuation of the game diminishes with time depending on a discount factor $\delta <1$ , then player i's utility is:

U_{i}=\sum _{t\geq 0}\delta ^{t}u_{i}(x_{t})

For sufficiently patient players (e.g. those with high enough values of $\delta$ ) , 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

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

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

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

↑ Aumann, R. J.; Maschler, M. (1995). Repeated Games with Incomplete Information. Cambridge London: MIT Press.
↑ 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

Topics in game theory
Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference
Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium
Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy
Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global game Strictly determined game Potential game
Games	Prisoner's dilemma Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock–paper–scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and Monster game Rendezvous problem
Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem
Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith Antoine Augustin Cournot John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey
See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.