One-shot deviation principle

The one-shot deviation principle (also known as one-deviation property[1]) is the principle of optimality of dynamic programming applied to game theory.[2] 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.[1][3] 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.

Furthermore, the one-shot deviation principle is very important for infinite horizon games, in which the principle typically does not hold,[4] since it is not plausible to consider an infinite number of strategies and payoffs in order to solve. In an infinite horizon game where the discount factor is less than 1, a strategy profile is a subgame perfect equilibrium if and only if it satisfies the one-shot deviation principle.[5]

Definitions

The following is the paraphrased definition from Watson (2013)[1]

To check whether strategy s is a subgame perfect Nash equilibrium, we have to ask every player i and every subgame, if considering s, there is a strategy s’ that yields a strictly higher payoff for player i than does s in the subgame. This analysis is equivalent to looking at single deviations from s, meaning s’ differs from s at only one information set. Note that the choices associated with s and s’ are the same at all nodes that are successors of nodes in the information set where s and s’ prescribe different actions.

Example

Consider a symmetric game with two players in which each player makes binary choice decisions, A or B, in three sequences. Note, that each player only first sees the opposing sequence once three characters has been selected. There are 8 (23) total number of pure strategies for each player: {AAA, AAB, ABA, ABB, BBB, BBA, BAB, BAA}. In this example, consider that a player chooses strategy (AAA). To check whether this strategy is a SPE, the one-shot deviation principle states that the player needs to check the payoffs of only three other strategies which differ from the original strategy by a single deviation, instead of all seven others. These three strategies are: (BAA), (ABA), and (AAB). If none of these three strategies yields a higher payoff than (AAA), then the player can conclude that (AAA) is an SPE.

References
  1. Watson, Joel (2013). Strategy: An Introduction to Game Theory. New York: W. W. Norton & Company. p. 194. ISBN 978-0393123876.
  2. Blackwell, David (1965). "Discounting Dynamic Programming". Annals of Mathematical Statistics. 36: 226–235. doi:10.1214/aoms/1177700285.
  3. Tirole, Jean; Fudenberg, Drew (1991). Game theory (6. printing. ed.). Cambridge, Mass. [u.a.]: MIT Press. ISBN 978-0-262-06141-4.
  4. Obara, I. (2012). Subgame Perfect Equilibrium [PDF document]. Slide 13. Retrieved from http://www.econ.ucla.edu/iobara/SPE201B.pdf
  5. Ozdaglar, A. (2010). Repeated Games [PDF document]. Slide 13. Retrieved from https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-254-game-theory-with-engineering-applications-spring-2010/lecture-notes/MIT6_254S10_lec15.pdf
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.