978-0393919684 Chapter 3 Lecture Note

Unlock access to all the studying documents.

View Full Document

PART TWO—Concepts and Techniques

CHAPTER 3

Games with Sequential Moves

Teaching Suggestions

Most students find the idea of rollback very simple and natural, even without drawing

or understanding trees. Of course, they start by being able to do only one or two steps. A very

simple way to get them to think about carrying the process all the way back to the beginning is

to get pairs of students in class to play a game that requires rollback reasoning. Two such

games were described in Chapters 1 and 2 of this manual (Claim a Pile of Dimes [The

Centipede game] and Single-Offer Bargaining [The Ultimatum game]). Two others are Games 1

and 2 below (also Exercise U5 of this chapter). They are variants of the Nim-type 21 Flags

game in Chapters 1 and 2 of this manual and are described in more detail below. The discussion

that follows the play of the games can build up to the general notion of rollback. With this

understood, the class will be much more receptive to the formalism of trees as a systematic

way of practicing rollback.

Once you have succeeded in introducing the idea of rollback and in motivating the

usefulness of trees, it is also important to focus on specifics. It is nice to have a sample game

that you can use to illustrate a variety of concepts and that you can refer to continually during

the first part of the term. The sequential-move versions of the Prisoners’ Dilemma game, the

Chicken game, or the Tennis-Point game, introduced in the text in Section 2 of Chapter 6, are

about the right size for this. While these games most logically fit the description of a

simultaneous-move game (with no equilibrium or multiple equilibria in pure strategies), you

can motivate the sequential-move versions. For example, in the Tennis-Point game you can

argue that you want to analyze the case in which the player about to hit the ball makes a

particular move that indicates in which direction the ball will go; her opponent can read the

body language and respond accordingly. Then the game is sequential and amenable to rollback

analysis. You could also use a baseball example where the pitcher “tips” his pitch and the

batter can be ready for it.

When you first illustrate the tree for a specific game like the sequential-move version

of the Tennis-Point game, you will want to identify and label the various components of the

tree: initial node, decision nodes, terminal nodes, and branches. You will also want to introduce

the important components of analysis that are considered in any game: players, actions,

payoffs, strategies, outcomes, and equilibria. In your simple tree, you will easily be able to

identify players, actions, payoffs, and outcomes. Strategies, especially for sequential games,

and equilibria take more effort.

One of the hardest ideas for students to grasp is the game-theoretic concept of a

strategy as a complete plan of action. We have exhorted many classes of students to think of a

strategy as something you can write down on a piece of paper and give to your mother so that

she can play the game for you; then you have to write down instructions for mom in such a

way that she knows what you want her to do no matter what happens in the game before it is

your turn to move. And that means no matter what happens, that strategy has to cover every

possible contingency. Most students can relate to the need for explaining everything down to

the last detail to their mothers. In your sample sequential-move game, you can then show the

number of strategies available to the first mover and the larger number available to the second

mover; you will want to show how to construct the second mover’s contingent strategies and

how to describe them.

Once you have discussed the issues surrounding contingent strategies, you can derive

the rollback equilibrium and show which strategies are used in equilibrium. To help students

appreciate how quickly contingent strategies increase in complexity, you can go on to an

example of a three-or-more-player game. The text abbreviates the contingent strat egies in such

games. For example, in the Street Garden game of Section 3, Nina’s strategy “Don’t contribute

if Emily has contributed, and contribute if Emily has not” is abbreviated (DC). Students who

have difficulty with the idea of strategies as complete plans of action may be more comfortable

with the description of this strategy (and others) in the notation (if C, then D; if D, then C). If

you are looking for an example that is similar but not identical to ours, Peter Ordeshook

provides a comprehensive analysis of a three-person voting example involving a roll-call

(sequential) vote on a pay raise in Game Theory and Political Theory (London: Cambridge

University Press, 1986); the tree for his game is the same size and shape as that for our Street

Garden Game and the Mall-Location game in Exercise 8 of this chapter.

You may want to have some discussion with your students about the increase in

complexity that arises when the number of moves, in addition to the number of players, is

increased. Most students will have at least heard of the chess-playing computer, Deep Blue,

and may be interested in what game theory has to tell them about the ongoing chess-based saga

of human versus machine. Others may want to pursue the dis crepancies between the

predictions of rollback—like immediate pickup in Claim a Pile of Dimes (The Centipede game;

see Chapters 1 and 2)—and outcomes in actual play, particularly if they had the opportunity to

play a game of this type themselves. Our students have found it interesting to see the tree for

The Centipede game at this point, and you can use it to show how a full tree is sometimes not

necessary for the complete analysis of the game.

Game Playing in Class

GAME 1—Adding Numbers (Win at 100)

This game is described in Exercise U5 of this chapter, part a, and is a longer version of the 21

Flags game described in Chapters 1 and 2 of this manual. In this version, two players take turns

choosing a number between 1 and 10 (inclusive), and a cumulative total of their choices is kept.

The player to take the total exactly to 100 is the winner.

One way to play this game is to have pairs of students play in front of the class. The

first pair starts by choosing numbers more or less at random, until the total drifts into the 90s

and the player with the next turn clinches a win. The second (or maybe third) time you play it,

when the total gets somewhere in the 80s, one of that pair will realize that she wins if she takes

the total to 89. When she does that, the other will (probably) realize that she has lost, and as

she concedes, the rest of the class will realize it, too. The next pair will quickly settle into

subgame-perfect play. By the fifth or sixth pair, almost everyone will have figured out that

starting at 0 (being the first mover) guarantees a win: start with 1, and then say 11 minus what

the other says, thus taking the total successively to 12, 23, . . . , 78, 89, 100.

An alternative approach is to divide your students into pairs and to provide them with a

worksheet on which they can record their numbers and the running total. Each pair can work

together to determine a winning strategy for the game. This approach has the advantage of

letting every student struggle with the first few steps of the rollback process rather than

watching it unfold before them. After a few minutes, you can begin your discussion of the

game by asking what the first step in the solution process was for each pair; each will be able

to answer that the winner wants to take the total to 89. You can then lead them backward

through the game and discuss the full equilibrium strategy.

In both cases, you can hold a brief discussion and build the insight gained from

watching and playing into the general idea of backward induction. You can also point out how

the equilibrium strategy here is a complete plan of action.

GAME 2—Adding Numbers (Lose If Go to 100 or over, Win at 99)

This game is also described in Exercise U5 of this chapter, part b. In this version, two players

again take turns choosing a number between 1 and 10 (inclusive), and a cumulative total of

their choices is kept. This time, the player who causes the total to equal or exceed 100 is the

loser.

Again, you can have pairs play in front of the class or have pairs work together toward

a solution. Regardless of the approach you choose, eventually everyone will have figured out

that starting at 0 (being the first mover) guarantees not a win but a loss. In this version of the

game, it is better to go second: let the first player choose any number and then say 11 minus

what the other says. Here, the second player takes the total succes sively to 11, 22, . . . , 77, 88,

99; the first player must then take the total to 100 (or more) and lose. You can hold a brief

discussion comparing the two versions of the game; this helps make the point about order

advantages in different games.