The IDSDS algorithm is defined by the following series of steps:
Step 1 Delete all strictly dominated strategies from the original game. (This step is predicated on the assumption that players are ra- tional.)
Step 2 Delete all strictly dominated strategies from the game derived after performing step 1. (This step is predicated on the assumption that each player believes that all players are rational.)
Step 3 Delete all strictly dominated strategies from the game derived after performing step 2. (This step is predicated on the assump- tion that each player believes that all players believe that all play- ers are rational.)
Step 4 Delete all strictly dominated strategies from the game derived after performing step 3. (This step is predicated on the assump- tion that each player believes that all players believe that all play- ers believe that all players are rational.)
.
.
.
Step t Delete all strictly dominated strategies from the game derived after performing step t � 1.
The procedure continues until no more strategies can be eliminated. In a game with an infinite number of strategies for each player, the procedure could go on forever, but that is not typical. Usually, after a finite number of steps, no more strategies can be eliminated. What remains are the strategies that are said to survive the IDSDS.
Returning to the chapter-opening quote of Sherlock Holmes, we see that IDSDS eliminates the “impossible,” and then whatever remains is what is possible. If only one strategy remains for each player (note that at least one strategy must survive), then the game is dominance solvable and the IDSDS delivers a unique prediction regarding behavior.
Let’s go through an example to make sure that we under- stand the procedure. Consider the two-player game illustrated in FIGURE 3.21.
For step 1, consider first player 1. Does she have any strictly dominated strategies? To answer this question, you
76 CHAPTER 3: ELIMINATING THE IMPOSSIBLE: SOLVING A GAME WHEN RATIONALITY IS COMMON KNOWLEDGE
FIGURE 3.21 Applying the IDSDS
3,2 4,1
4,4
5,1
1,3
3,1
3,1
2,5 Player 1
Player 2
a
b
c
d
2,3
2,3
3,1
1,2
0,4
1,4
4,2
0,4
w x y z
3.4 Solving a Game when Rationality Is Common Knowledge 77
could consider each strategy and determine whether there is another strategy that produces a strictly higher payoff for every strategy of player 2. A shortcut is to first determine which strategies are optimal for player 1 for some strat- egy of player 2. Those strategies cannot be strictly dominated, since they are best in some circumstances.
In deploying the tactic of first identifying optimal strategies for player 1, note that if player 2 uses strategy w, then strat- egy d is optimal for player 1 (giving her a payoff of 5, which exceeds the payoff from any other strategy). Thus, d cannot be strictly dominated. If player 2 uses x, then a is best for player 1, so a cannot be strictly dominated. When player 2 uses y, then c is best, so it is not strictly dominated either. Finally, if player 2 uses z, then c is best, but we already know that c is not strictly dominated. Thus far, we’ve learned that a, c, and d are not strictly dominated for player 1. This leaves only one remaining strategy to consider, which is b. In fact, b is strictly dominated by d. So, since player 1 is rational, player 1 will avoid using b. Thus, as depicted in FIGURE 3.22, we can delete strategy b from the game in Figure 3.21.
We’re not finished with step 1, as the same exercise has to be performed on player 2. Working again with the game in Figure 3.21, we see that if player 1 uses strategy a, then z is best for player 2, in which case z is not strictly dom- inated. If player 1 uses b, then x is best for player 2, so x is not strictly domi- nated. If player 1 uses c, then w is optimal for player 2, so w is not strictly dominated. And if player 1 uses d, then z is again optimal for player 2. Hence, strategies w, x, and z are not strictly dominated. The remaining strategy, y, is, however, strictly dominated by z. Since player 2 is rational, we conclude that he will not use y. We can then scratch out strategy y. (See FIGURE 3.23.)
Turning to step 2, we show the reduced game in FIGURE 3.24, where strategy b has been eliminated for player 1 and strategy y has been eliminated for player 2. Are there any strictly dominated strategies that we can eliminate from this game? None are strictly dominated for player 1. (Convince yourself.) For player 2, z strictly dominates x. Note that x was not strictly dominated by z in the original game, because it produced a higher payoff than z (and any other strategy) when player 1 used b. However, since b is strictly dominated for player 1, player 2 doesn’t think that player 1 will use it, because player 2
FIGURE 3.22 Eliminating Player 1’s Strictly Dominated Strategy
3,2 4,1
4,4
5,1
1,3
3,1
3,1
2,5 Player 1
Player 2
a
b
c
d
2,3
2,3
3,1
1,2
0,4
1,4
4,2
0,4
w x y z
FIGURE 3.23 Eliminating Player 2’s Strictly Dominated Strategy
3,2 4,1
4,4
5,1
1,3
3,1
3,1
2,5 Player 1
Player 2
a
b
c
d
2,3
2,3
3,1
1,2
0,4
1,4
4,2
0,4
w x y z
FIGURE 3.24 Reduced Game After One Round of IDSDS
3,2 4,1
5,1
1,3
3,1
3,1Player 1
Player 2
a
c
d
0,4
1,4
4,2
w x z
believes that player 1 is rational. Hence, b has been eliminated and, along with it, the reason for keeping x around as a possibly useful strategy. Player 2’s other strategies remain undominated.
Since a strategy was eliminated in step 2, the procedure is not over, and we move to step 3. With the elimination of strategy x for player 2, the game is as shown in FIGURE 3.25. Recall that no strategies were eliminated for player 1. Examining Figure 3.25, note that d strictly dominates a for player 1, while c and d remain undominated. Of course, w and z are still not strictly dominated: They were not strictly dominated in step 2, and the strategies for player 1 in step 3 are the same as those in step 2.
After deleting strategy a, we find that the reduced game is as in FIGURE 3.26, which brings us to step 4. At this point, no strategy is strictly dominated. Since
we can’t delete any more strategies, the procedure is completed. Our conclusion is that strategies c and d for player 1 and strategies w and z for player 2 survive the IDSDS. Thus, assuming that rationality is common knowledge is insufficient to deliver a unique prediction, but it does allow us to eliminate 12 of the 16 possible
strategy pairs. All we can say right now is that player 1 will use c or d and player 2 will use w or z.