Iterated elimination of dominated strategies
From Theory
Notes for CS 8803 - Game Theory and Computer Science. Spring 2008
Contents |
Elimination of dominated strategies
If a strategy is strictly dominated, then it makes sense to rule it out as a possiblity for a rational player. Why would they choose that strategy when there is another strategy that is always better? Even eliminating weakly dominated strategies sounds quite reasonable. Iterated elimination of dominated strategies (IEDS) is a process in which we delete dominated strategies from a game. This may proceed one strategy at a time. (As we will see below, the order very much matters.) Or it may proceed in rounds: first eliminate all dominated strategies for player 1, then eliminate all dominated strategies for player 2, etc. In the homework, I will ask you to show that chess can be solved in only two rounds of iterated elimination of dominated strategies. (Note that chess is a finite two-person zero-sum game of perfect information, and there are only three possible payoffs.) A round will be defined as eliminating strategies for player 
.
Note that in prisoner's dilemma, IEDS leads to defecting. In fact, defecting is a strictly dominant strategy. In the ultimatum game, it is a dominant strategy to offer your opponent as little as possible.
Iterated elimination in two-person zero-sum games of perfect information
In finite two-person zero-sum games of perfect information, iterated elimination of dominated strategies is actually quite powerful. It is enough to solve for optimal play in the game, and gives a means for computing the value. It is essentially backwards induction. In this case, order doesn't matter in terms of affecting the computed value of the game. Wow, so chess really isn't as complex as I thought!
Well, certainly it's not polynomial time, right? Not excatly!
Chess is a finite game due to the rule that if the same position is repeated three times, the game ends in a draw. The game may therefore be represented as a finite extensive-form game with perfect information. The "size" of the game is quite huge, greater than the number of atoms in the universe. As we discussed any two-person zero-sum perfect-information extensive-form game can be solved in polynomial time by backward induction.
Of course, chess is a complex game. In fact, it is quite computationally difficult to figure out who wins. On the third hand, we have chess programs that beat the best human players. Kudos to AI search algorithms. So, what is going on?
Great question! Somehow game theory has little to say about games like chess. Complexity theory seems to suggest that it is hard to solve them for optimal strategies. But in the end of the day, you need to play (or choose a program to play). How will you decide?
On the other hand, it was shown that on an 
board, chess requires exponential time:
A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214.
As the title suggests, this paper shows that you need time exponential in n to figure out who wins on arbitrary positions in generalized chess on an board.
Tough guy makes a tender offer
One of the cooler examples of dominated strategies in economics is a two-tiered tender offer that was given by entrepreneur Robert Campeau. Read about it in this amazon book. Click on the link. Click "GO" on the search for "tough-guy tender-offer". Read away, starting at page 81. (I wonder how long this link will be active....)
Complexity in normal-form games
However, the following example illustrates that the order of eliminating strategies matters.
| A | B | |
|---|---|---|
| I | 0,0 | 2,5 |
| II | 5,5 | 100,5 |
| III | 5,5 | 0,0 |
We could:
- Eliminate I for player 1
- Eliminate B for player 2
- Eliminate II for player 1
OR, we could:
- Eliminate III for player 1
- Eliminate A for player 2
- Eliminate I for player 1
This gives different payoffs to the two players. Next we will discuss the following paper.
The complexity of eliminating dominated strategies, by Gilboa, Kalai, and Zemel. Mathematics of Operations Research, pages 553-565, 18(3), 1993.
This was one of the earlier papers on the intersection of computer science and game theory. It shows that the problem of figuring out whether IEDS can lead to a unique pair of actions is NP-complete.
The production of this material was supported in part by NSF award SES-0734780.
