Introduction of Backward Induction Technique Using a Classroom Experiment
Summary
This is a classroom activity to introduce students to the idea of backward induction. Students, in teams of two, play the Game of 21 repeatedly with progressively smaller action spaces in every repetition. As the number of available actions become sufficiently small in later repetitions, students discover the obvious winning strategy. This experience is then used to introduce the logic of backward induction and the Subgame Perfect Nash Equilibrium (SPNE) solution concept in Game Theory.
CollapseLearning Goals
Context for Use
This classroom experiment can be used in any introductory or intermediate Game Theory course. The exericise can also be used in Intermediate Microeconomics courses that include a discussion of SPNE.
Many of us do not approach dynamic problems in a backwardly inductive manner. As a result, learning, understanding, and finally using the backward induction logic in solving games do not come naturally. When introducing the topic for the first time, instructors often face reactions ranging from stoicism to complete disbelief from the students.This activity provides a fun-filled introduction to the logic of backward induction, that can help overcome any inhibition towards learning the technique. The experiment takes about 15-20 minutes for a class of 20 students; activity is introduced before starting with lectures on backward induction; no special equipment needed except the blackboard/whiteboard.
Description and Teaching Materials
Description of the game:
Two players take turns to play this game. There are 21 numbers, starting from 1 and ending in 21, presented in an increasing order. Each player at his or her turn is required to pick or remove numbers sequentially starting with the lowest available number. Each player is restricted to choose, at most, three consecutive numbers at every turn. That is, a player at her turn, can pick one, two or three consecutive numbers at a time. The player, who reaches a position to pick number 21 first, wins the game.
Description of the Classroom Activity:
1. Numbers 1 through 21, are written on the blackboard in a single row
2. The rules of the game are introduced with some examples of player moves. (Note: It is important to provide examples of player moves so that students do not think that the numbers can be chosen in random order, and can only be selected in a sequential manner without skipping any numbers in between.
3. Two students are asked to volunteer (Note: an entertaining version can be where the instructor divides the class into groups of two or three, and assign a leader for each group to have a tournament between two groups at a time. The leader is then responsible for taking final decisions at each turn after consulting with the group members). Once the students volunteer, they are given the option to be the first or the second mover.
4. As students take turns to choose the numbers they want removed, the instructor wipes them off the board till a winner emerges( See Example (Acrobat (PDF) 82kB Feb4 13)).
5. Play the game a second time.
6. Next the instructor introduce a modified game in the board where the numbers 18 through 21 are erased to construct a game with a smaller action space, the game of 17!
7. Steps 3 and 4 are repeated.
8. The instructor introduces an even smaller game next – that game of 13! Steps 3 and 4 are repeated.
9. The instructor introduces a further modification of the game with 9 numbers. Steps 3 and 4 are repeated.
10. In the final run the instructor only has 5 numbers on the board.
11. By the time the game is reduced to the game of 5 (with only the numbers 1 through 5) many students start getting an intuitive understanding of the way to proceed in the game. The reduced number of available actions now allow students to envision the end of the game easily, and compare alternative action choices conveniently. At the end of step 10, the instructor goes over the backward-induction solution of the smaller game first, and the full version next. For a visual description of each round see Iterations (Acrobat (PDF) 23kB Feb4 13).
Teaching Notes and Tips
The way to think about the solution for the game is as follows: Suppose players A and B are in the situation where there are only 4 numbers left, and it is player B's turn. By the rules of the game, B is restricted to choosing one, two, or all three numbers at his turn, which means A at her turn can accordingly pick the last three, two or the sole remaining number, to claim victory. Now to ensure that B is left facing four remaining flags at his turn, A, at her previous turn, must leave B facing eight numbers. Using the same logic iteratively would imply B leaving twelve, sixteen, and twenty flags in previous moves, respectively. Therefore, in the beginning with all twenty one numbers displayed, the first player should choose the first number, and then proceed to take four, minus whatever the other takes at his immediately preceding turn.
More generally, if the rules of the game specifies that a player can remove, at most, n numbers, then a player should leave his opponent facing the last n+1 numbers, and before that 2(n+1) numbers, and before that 3(n+1) numbers and so on. It is straightforward to verify that if one uses numbers 1 through 21, the game has a first-mover advantage.
Assessment
The primary purpose of this exercise is to help students to think in a backward inductive manner. Such an analysis allows the student to further understand notions of first-mover or second-mover advantages in certain dynamic situations. The assessment below is meant to evaluate whether students have learned to think in a backward inductive manner, and learned to determine first-mover/second-mover advantages in a dynamic setting.
Pre-test: Before starting the activity above introduce the Game of 21 and provide a slightly different rule. A player at his/her move can remove at most one or two numbers. Ask students to write down whether they have an advantage playing as the first mover or the second mover.
Post-test: After the instructor has explained the procedure of backward induction the Game of 21 is displayed again on the blackboard. The instructor provides the instructions from the pre test, i.e., a player at his/her move can remove at most one or two numbers. The instructor should ask students the backward inductive winning strategy and also whether being a first or a second mover has an advantage.
Finally, to evaluate whether the students can in fact transfer the learning from this game to other dynamic situations, the instructor can consider including variants of the Game of Nim (Acrobat (PDF) 29kB Feb7 13) in a quiz or test.
References and Resources
This activity was based on the paper Dasgupta, U. (2010): "Nudging Students Forward Towards Backward Induction", Journal of Industrial Organization Education, 2010, Vol. 5 Issue 1, Article 3. A short related Bibliography is provided below.
Bibliography
Dixit, A. (Summer 2005): "Restoring Fun to Game Theory," Journal of Economic Education, Vol. 36, pp. 205-219.
Dutta, P.K. (1999) Strategies And Games: Theory and Practice: The MIT Press.
Dufwenberg, M., Sundaram, R. and David J. Butler (2010): "Epiphany in the Game of 21," Journal of Economic Behavior and Organization, 75(2), 132-143.
Gneezy, U., and A. Rustichini A. and Vostroknutov A. (2009): "Experience and Insight in the Race Game," Journal of Economic Behavior and Organization, 75(2), 144-155.
Watson, J. (2002) Strategy: An Introduction to Game Theory: W.W. Norton & Co.