Extensive form games with multiple stages have lots of potential deviations from what could be equilibrium strategies. Take a game with 16 binary decision nodes. Then there are 216 total possible combinations of strategies, which is equal 65,536. Thus, there appear to be 65,535 deviations that one would have to check to verify that something is an equilibrium. The problem seems to become completely intractable for an infinite horizon game, as there are an infinite number of possible deviations to select from.
This lecture introduces the one-shot deviation principle, which makes a relatively difficult problem somewhat simple to tackle.
- In finite games or infinitely repeated games with discounting, a set of strategies is a subgame perfect equilibrium if and only if no player can profitably deviate from his strategy at a single stage and maintain his strategy everywhere else.
- This is called the one-shot deviation principle because it allows us to check single deviations to find equilibria.
- It is straightforward to understand that if something is a subgame perfect equilibrium, no profitable one shot deviation exists. SPE must be optimal. If a player could make a single change somewhere and do better, than clearly the set of strategies in question is not an equilibrium.
- The more surprising thing is that if no profitable one-shot deviation exists, then the set of strategies is a subgame perfect equilibrium. The proof for this is complicated, and we do not cover it here. However, the basic idea is that if a more complicated deviation is profitable, then a simpler deviation will be as well.
- Equivalently (by contraposition), if a set of strategies is not a subgame perfect equilibrium, then a profitable one-shot deviation exists.
- Thus, a game with 16 binary decisions only requires you to check 16 deviations to verify that something is an equilibrium, rather than 65,535 deviations.