Introduction to Game Theory: a Discovery Approach

Section 2.2 Dominated Strategies

Recall that in a zero-sum game, we know that one player's win is the other player's loss. Furthermore, we know we can rewrite any zero-sum game so that the player's payoffs are in the form \((a, -a)\text{.}\) Note, this works even if \(a\) is negative; in which case, \(-a\) is positive.

When simplifying, keep a few things in mind:

1. You MUST know that the game is zero-sum.

2. If it is not otherwise specified, the payoffs represent Player 1's payoffs.

3. You can always give a similar matrix representing Player 2's payoffs. However, due to (2), you should indicate that the matrix is for Player 2. For example, Player 2's payoff matrix would be given by Table 2.2.4.

   	Player 2
   Player 1	-1	0
   	1	2

4. Both players can make strategy decisions by considering only Player 1's payoff matrix. (Why?) Just to test this out, by looking only at the matrix in Table 2.2.3 determine which strategy each player should choose.

   	Player 2
   Player 1	1	0
   	-1	-2

In this last example, it should be clear that Player 1 is looking for rows which give her the largest payoff. This is nothing new. However, Player 2 is now looking for columns which give Player 1 the SMALLEST payoff. (Why?)

Now that we have simplified our notation for zero-sum games, let's try to find a way to determine the best strategy for each player.

In Example 2.2.6, no matter what Player 2 does, Player 1 would always choose Row 1, since every payoff in Row 1 is greater than or equal to the corresponding payoff in Row 2 (\(1\ge -1\text{,}\) \(0\ge -2\text{,}\) \(2\ge 2\)). In Example 2.2.8, this is not the case: if Player 2 were to choose Column 3, then Player 1 would prefer Row 2. In Example 2.2.6 we would say that Row 1 dominates Row 2.

In mathematical notation, let \(a_{ik}\) be the value in the \(i^{ th}\) row and \(k^{ th}\) column. Similarly, \(a_{jk}\) is the value in the \(j^{ th}\) row and \(k^{ th}\) column. The \(i^{ th}\) row dominates the \(j^{ th}\) row if \(a_{ik}\ge a_{jk}\) for all \(k\text{,}\) and \(a_{ik}> a_{jk}\) for at least one \(k\text{.}\)

This definition can also be used for Player 2: we consider columns instead of rows. If we are looking at Player 1's payoffs, then Player 2 prefers smaller payoffs. Thus one column \(X\) dominates another column \(Y\) if all the entries in \(X\) are smaller than or equal to the corresponding entries in \(Y\text{.}\)

Here is the great thing: we can always eliminate dominated strategies! (Why?) Thus, in Example 2.2.6, we can eliminate Row 2, as in Figure 2.2.11.

Now it is easy to see what Player 2 should do.

In Example 2.2.8, we cannot eliminate Row 2 since it is not dominated by Row 1. However, it should be clear that Column 2 dominates Column 3 (remember, Player 2 prefers SMALLER values). Thus we can eliminate Column 3 as in Figure 2.2.12.

AFTER eliminating Column 3, Row 1 dominates Row 2. Now, in Figure 2.2.13 we can eliminate Row 2.

Again, now it is easy to determine what each player should do.

Now, look back at the election examples from Subsection 2.1.1 and apply the process of eliminating dominated strategies.

The next three exercises provide more practice in using dominated strategies to find equilibrium pairs.

Chances are you had trouble determining an equilibrium pair for the game in Exercise 2.2.22. Does this mean there isn't an equilibrium pair? Not necessarily, but we are stuck if we try to use only the idea of eliminating dominated strategies. So we need a new method.

We might think of our next method as the “worst case scenario,” or “extremely defensive play.” The idea is that we want to assume our opponent is the best player to ever live. In fact, we might assume our opponent is telepathic. So no matter what we do, our opponent will always guess what we are going to choose.

After working through a few examples can you describe more generally the process used in Example 2.2.24? What is Player 1 looking for in each row? Then how does she choose which row to play? What is Player 2 looking for in each column? How does he choose which column to play?

The strategies we found using the above method have a more official name. Player 1's strategy is called the maximin strategy. Player 1 is maximizing the minimum values from each row. Player 2's strategy is called the minimax strategy. Player 2 is minimizing the maximum values from each column. Notice, we can find the maximin and minimax strategies for any zero-sum game. But do our players always want to use these strategies? Will they always result in an equilibrium pair? The next five exercises explore these questions.

Given a zero-sum matrix game, we can find equilibruim pairs (if they exist) by the “guess and check” method, by eliminating dominated strategies, and by looking for the minimax/maximin strategies. You should be able to apply all three methods and think about which method might be the most appropriate for a given matrix game. For example, although “guess and check” should always find an equilibrium point if it exists, it may be very tedious to apply to a really large matrix. The maximin/minimax method might be much faster.