One-shot deviation principle: Difference between revisions
m Open access bot: doi added to citation with #oabot. |
m Normalize {{Multiple issues}}: Remove {{Multiple issues}} for only 1 maintenance template(s): Technical |
||
| Line 1: | Line 1: | ||
{{multiple issues| |
|||
{{Orphan|date=March 2014}} |
{{Orphan|date=March 2014}} |
||
{{technical|date=March 2014}} |
{{technical|date=March 2014}} |
||
}} |
|||
The '''one-shot deviation principle''' (also known as '''one-deviation property'''<ref name=":0">{{Cite book|title=Strategy: An Introduction to Game Theory|last=Watson|first=Joel|publisher=W. W. Norton & Company|year=2013|isbn=978-0393123876|location=New York|pages=194}}</ref>) is the principle of optimality of [[dynamic programming]] applied to [[game theory]]<ref>{{Cite journal|last=Blackwell|first=David|date=1965|title=Discounting Dynamic Programming|url=|journal=Annals of Mathematical Statistics|volume=36|pages=226–235|via=|doi=10.1214/aoms/1177700285|doi-access=free}}</ref>. 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.<ref name=":0" /><ref>{{cite book|last1=Tirole|first1=Jean|last2=Fudenberg|first2=Drew|title=Game theory|year=1991|publisher=MIT Press|location=Cambridge, Mass. [u.a.]|isbn=978-0-262-06141-4|edition=6. printing.}}</ref> 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 '''one-shot deviation principle''' (also known as '''one-deviation property'''<ref name=":0">{{Cite book|title=Strategy: An Introduction to Game Theory|last=Watson|first=Joel|publisher=W. W. Norton & Company|year=2013|isbn=978-0393123876|location=New York|pages=194}}</ref>) is the principle of optimality of [[dynamic programming]] applied to [[game theory]]<ref>{{Cite journal|last=Blackwell|first=David|date=1965|title=Discounting Dynamic Programming|url=|journal=Annals of Mathematical Statistics|volume=36|pages=226–235|via=|doi=10.1214/aoms/1177700285|doi-access=free}}</ref>. 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.<ref name=":0" /><ref>{{cite book|last1=Tirole|first1=Jean|last2=Fudenberg|first2=Drew|title=Game theory|year=1991|publisher=MIT Press|location=Cambridge, Mass. [u.a.]|isbn=978-0-262-06141-4|edition=6. printing.}}</ref> 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. |
||
Revision as of 17:18, 31 May 2020
 | This article may be too technical for most readers to understand. (March 2014) |
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
- ^ a b c Watson, Joel (2013). Strategy: An Introduction to Game Theory. New York: W. W. Norton & Company. p. 194. ISBN 978-0393123876.
- ^ Blackwell, David (1965). "Discounting Dynamic Programming". Annals of Mathematical Statistics. 36: 226–235. doi:10.1214/aoms/1177700285.
- ^ Tirole, Jean; Fudenberg, Drew (1991). Game theory (6. printing. ed.). Cambridge, Mass. [u.a.]: MIT Press. ISBN 978-0-262-06141-4.
- ^ Obara, I. (2012). Subgame Perfect Equilibrium [PDF document]. Slide 13. Retrieved from http://www.econ.ucla.edu/iobara/SPE201B.pdf
- ^ 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