Lecture 13: Sequential Games of Perfect Information

and Backward Induction

Vera Sharunova

1 Sequential vs. Simultaneous Games

So far in our course, we have been focusing exclusively on simultaneous-move games1 , in
which players choose their actions simultaneously and after that observe the outcome of
the game. However, there are games that entail a defined order of play, e.g. the games of
chess, checkers, and go, and therefore cannot be adequately modeled by simultaneous-
move games and represented in normal form. Such games are called sequential or
dynamic. Players take turns making their moves, and typically, they know what moves
the players who moved before them made and they know that the players who move after
them observe all previous choices. The change from simultaneous to sequential moves
introduces additional strategic implications, as now each player needs to consider how
their current actions will influence future actions, both for their rivals and for themselves.

Definition 1. Sequential games are strategic situations with a defined order of play.

Normal vs. Extensive-Form Representation

As mentioned before, normal form representation that we have been using so far can-
not describe the order in which players make their moves. For this reason, we need to
develop a new tool for representing and analyzing sequential games. We refer to such
representation of games as the extensive form or the game tree. Consider an example
of a game in its extensive form in Figure 1 below.

This game has four players – Ann, Bob, Chris, and Deb – that make their moves in
turns. Ann is the first to move, so she starts the game by choosing her move at the
initial node of the game tree. Nodes of a game tree in which some player has to make
a move are called decision nodes. Ann has two choices available to her at the initial
node: Stop and Go. These choices are illustrated by two branches emerging from the
initial node and labeled “Stop” and “Go”. Ann’s choices at this point will determine
how the game will be played.
1
Simultaneous-move games are also applicable to situations in which players are not literally choosing
their actions simultaneously, but rather cannot communicate with each other.

1
ECON3308.01: Game Theory in Economics Summer 2021

• If Ann chooses Stop, then the game reaches Bob’s decision node. Bob can choose
between three moves – 1, 2, and 3. If Bob chooses 1, Ann gets to move again. If Bob
chooses 2, Deb gets to move. Finally, if Bob chooses 3, the game is terminated with
the payoff profile (10, 7, 1, 1) realizing for all four players (listed in alphabetical
order). The last nodes in a game tree are called terminal nodes and, whenever the
game play reaches a terminal node, the game is over and the payoffs are realized2 .

• If Ann chooses Go, Chris gets to choose between Risky and Safe. If he chooses
Safe, the game play reaches a terminal node and the payoff profile (3, 5, 3, 1) is
realized. If Chris chooses a Risky strategy, a fair coin is flipped and the outcome
of the game is determined by whether that coin comes up “heads” or “tails”. This
is an example of an external uncertainty featuring in the game. For notational
convenience, we introduce a fictitious player Nature that “decides” whether the
coin will come up “heads” or “tails” each with 50% probability.

Starting from the initial node, you can trace a number of different paths through the
game tree by following successive branches that terminate at a particular terminal node.
We call these paths game paths and they describe a particular possibility of how the
game can play out, or a game play.

Actions vs. Strategies

In simultaneous-move games, each player chooses a single action, e.g. Swerve or Straight
in the chicken game, that constitutes their strategy for the entire game. In sequential
games, a strategy consists of a complete plan of actions for the game, i.e. moves that
each player is going to make when the game play reaches their decision nodes. There-
fore, strategies and actions are equivalent in simultaneous-move games, but strategies
consist of multiple actions in sequential games. It is easier to understand this distinction
through an example in Figure 1 and I will formally define what a strategy is after that.

Consider again Figure 1. A single move taken by a player at a decision node is called an
action. But sometimes players have more than one decision node – in this case, Ann.
She has to make plans for her choices at each decision node even though this decision
node may never be reached. Let us explicitly state what the strategies are for each of
the players:

• Ann: {Stop-Up, Stop-Down, Go-Up, Go-Down}.

• Bob: {1, 2, 3}.

• Chris: {Risky, Safe}.

• Deb: {High, Low}.

2
This is economics jargon for “the game is over and players observe their payoffs”.

2
ECON3308.01: Game Theory in Economics Summer 2021

Figure 1: An example of a game tree.

Even though if Ann chooses Go she never gets to move again, we still write down
her strategies as if she would get to move in her second decision node. This pedantic
specification of strategies matters for more advanced game theory topics, such as analysis
of stability of equilibria. People are known to make mistakes when playing games;
similarly, Ann could make a mistake and choose Stop even if she intended to choose Go.
If such a small mistake happens, it is important to follow up how Ann would act in case
Bob chooses 1 and she gets to move again. So we are now ready to formally define what
a strategy is in a sequential game.

Definition 2. A strategy is a complete plan of actions for the game that describes
actions at each of the player’s decision nodes, contingent on all possible combinations

3
ECON3308.01: Game Theory in Economics Summer 2021

made by players who acted at earlier nodes.

There is a useful way of thinking about strategies: If you were to delegate your choice
to a computer program, this program should execute completely without returning an
error message. Say, one of the players later in the game makes a mistake that puts you
in a decision node which you have not planned for. The program will return an error
message, so the game will not be able to terminate. Therefore, you must specify your
actions at all decision nodes given all possible combinations of choices made by other
players.

Finally, we will start our analysis of sequential games by considering a special type
of sequential games – games of perfect information. A game is said to have perfect
information if at each decision node a player observes all moves made by other players
earlier in the game. In other words, every player knows the history of the game when it
is their turn to move.

Definition 3. Perfect information is a situation in which all players know the history
of the game at each decision node and face no external uncertainty.

2 Rollback and Backward Induction

We will now discuss how one solves sequential games of perfect information. The idea is
rather simple and intuitive: start solving the game at the latest decision nodes and roll
back to the initial node, or in plain English, look ahead and reason back. This method is
referred to as rollback in our textbook, but it is more commonly known as backward
induction. These are two different names of the same technique. In order to illustrate
how this method works, consider a simpler game tree in Figure 3.

The Smoking Game

In this example we consider Carmen’s decision of whether to take up smoking or not.
Carmen may choose to never start smoking (Not) or she may choose to try smoking
and later decide whether to Continue or Not. The payoff from never starting smoking
is normalized to zero, the payoff from trying and quitting is normalized to 1, the payoff
of trying and continuing is normalized to -1. At first, we may think that it is not even
a game at all since it involves only one player – Carmen. However, once Carmen tries
smoking she is likely to get addicted and not have the same preferences as she has today.
Because of the addiction, we consider this situation as a game between Today’s Carmen
and Future Carmen.

Let us employ rollback or backward induction to solve this game. Start by looking at
Future Carmen’s decision node. She can choose whether to continue smoking and get a

4
ECON3308.01: Game Theory in Economics Summer 2021

Figure 2: The Smoking Decision.

Figure 3: The Smoking Game.

payoff of 1 or not to continue smoking and get a payoff of -1. Future Carmen maximizes
her payoff by choosing to continue smoking. Today’s Carmen should anticipate this
and make her choice accordingly. If she chooses to Try, then Future Carmen chooses to
Continue and Today’s Carmen gets a payoff of -1. If she chooses not to try smoking, her
payoff will be zero. Therefore, Today’s Carmen maximizes her payoff by choosing not
to try smoking (Not). Therefore, the equilibrium path of play is Not and the rollback
equilibrium is (Not, Continue).

Another Example of Rollback Reasoning

Consider the following game between Scarecrow and Tinman.

(a) How many pure strategies are available to each player? List all of them.

5
ECON3308.01: Game Theory in Economics Summer 2021

• Scarecrow chooses between two actions at three decision nodes, so he has 2 · 2 · 2 =

23 = 8 pure strategies. The strategies are SSS, SSN , SN S, SN N , N SS, N SN ,
N N S, N N N .

• Tinman chooses between two actions at three decision nodes, so he has 2 · 2 · 2 =

23 = 8 pure strategies. The strategies are sss, ssn, sns, snn, nss, nsn, nns, nnn.

(b) Identify the rollback equilibrium outcome and the complete equilibrium strategies
of each player.

Use backward induction to identify that the equilibrium play is S-n-S-n-N and that the
rollback equilibrium is (SSN , nns) yielding the equilibrium payoff of (4, 5).

At decision node 6, Tinman chooses s since 2 > 0. At decision node 5, Scarecrow,

knowing that Tinman will choose s if he chooses S, decides to choose N since the payoff
in that case is greater 4 > 2. At decision node 4, Tinman chooses n, knowing that
Scarecrow will choose N at node 5 since the payoff for him is greater in that case 5 > 2.
At decision node 3, Scarecrow, knowing the future path of play, chooses S since 4 > 2.
At decision node 2, Tinman, knowing the future path of play, chooses n since 5 > 4.
Finally, at decision node 1, Scarecrow, knowing the future path of play, chooses S since
4 > 0.