Abstract

In real-world games we look ahead and plan what we would do in various contingencies. However, our plan is not a commitment. As the situation progresses, we constantly reassess our play in response to new information. Even if there is no new information, and the situation is exactly what we forecast it to be, we can still reassess the wisdom of the plan we made earlier. If at some point what we had planned to do no longer seems optimal, we must deviate from our original plan. Because there are situations in which we cannot commit to a particular decision in the future, a rational player should also be sequentially rational: Her planned action in any situation and point in time must actually be optimal at that time and in that situation given her beliefs. We will see that this requirement of dynamic consistency is a stronger form of rationality assumption than we have made thus far.

In order to impose dynamic consistency upon our solution concepts, we learn how to decompose an extensive-form game into a subgame and its complement, viz., its difference game. Then we learn how to restrict extensive-form game strategies to the subgame and to the difference game, as well as the reverse: how to compose a new extensive-form game strategy from a subgame strategy and a difference-game strategy.

We define the solution concept of subgame-perfect equilibrium as a refinement of Nash equilibrium that imposes the desired dynamic consistency. A subgame-perfect equilibrium of an extensive-form game is a behavior-strategy profile whose restriction to each subgame is a Nash equilibrium of that subgame.

An extensive-form game need not have a pure-strategy Nash equilibrium. However, we then consider the special case of extensive-form games of perfect information, i.e., where every information set contains exactly one decision node. We use Zermelo’s backward-induction algorithm to prove that all such games of perfect information have a pure-strategy subgame-perfection equilibrium. This algorithm also provides a useful technique for finding the equilibria of actual games.