Finding Strategies

Section 2.2 Finding 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.

🔗

Subsection 2.2.1 Simplifying a Zero-Sum Game Matrix

Example 2.2.1. A Simpler Payoff Matrix.

Consider the zero-sum game with payoff matrix in Table 2.2.2. For simplicity our payoff matrix contains only the payoffs and not the strategy names; but Player 1 still chooses a row and Player 2 still chooses a column.

🔗

Table 2.2.2. The payoff matrix for Example 2.2.1.

🔗

	Player 2
Player 1	\((1, -1)\)	\((-0, 0)\)
	\((-1, 1)\)	\((-2, 2)\)

If we know we are playing a zero-sum game, then the use of ordered pairs seems somewhat redundant: if Player 1 wins 1, then we know that Player 2 must lose 1 (win \(-1\)). Thus, if we KNOW we are playing a zero-sum game, we can simplify our notation by just using Player 1’s payoffs. The above matrix in Table 2.2.2 can be simplified as in Table 2.2.3.

🔗

Table 2.2.3. The payoff matrix for Example 2.2.1 using only Player 1’s payoffs.

🔗

	Player 2
Player 1	\(1\)	\(0\)
	\(-1\)	\(-2\)

🔗

When simplifying, keep a few things in mind:

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

🔗
If it is not otherwise specified, the payoffs represent Player 1’s payoffs.
🔗

🔗
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.
Table 2.2.4. The payoff matrix for Example 2.2.1 using only Player 2’s payoffs.
🔗

Player 2

Player 1 \(-1\) \(0\)

\(1\) \(2\)

🔗

🔗
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.
🔗

🔗

🔗

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?)

🔗

Subsection 2.2.2 Dominated Strategies

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.

🔗

Example 2.2.5. A \(2\times 3\) Game.

Consider the zero-sum game given in Table 2.2.6.

🔗

Table 2.2.6. Payoff matrix for Example 2.2.5.

🔗

	Player 2
Player 1	\(1\)	\(0\)	\(2\)
	\(-1\)	\(-2\)	\(2\)

Determine which row Player 1 should choose. Is there any situation in which Player 1 would choose the other row?

🔗

Example 2.2.7. Another \(2 \times 3\) Game.

Consider the zero-sum game given in Table 2.2.8.

🔗

Table 2.2.8. Payoff matrix for Example 2.2.7.

🔗

	Player 2
Player 1	\(1\)	\(0\)	\(2\)
	\(-1\)	\(-2\)	\(3\)

Determine which row Player 1 should choose. Is there any situation in which Player 1 would choose the other row?

🔗

In Example 2.2.5, 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.7, this is not the case: if Player 2 were to choose Column 3, then Player 1 would prefer Row 2. In Example 2.2.5 we would say that Row 1 dominates Row 2.

🔗

Definition 2.2.9.

A strategy \(X\) dominates a strategy \(Y\) if every entry for \(X\) is greater than or equal to the corresponding entry for \(Y\text{.}\) In this case, we say \(Y\) is dominated by \(X\text{.}\)

🔗

If strategy \(X\) dominates stratgy \(Y\text{,}\) we can write \(X\succ Y\text{.}\)

🔗

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.5, we can eliminate Row 2, as in Figure 2.2.10.

🔗

the game matrix from the example with a line through the second row — Figure 2.2.10. Row 2 is dominated by Row 1.
🔗

Now it is easy to see what Player 2 should do, as we can ignore the crossed out row.

🔗

In Example 2.2.7, 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.11.

🔗

the game matrix from the example with a line through the second column — Figure 2.2.11. Column 3 is dominated by Column 2.
🔗

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

🔗

the game matrix from the example with a line through the second row and a line through the second column — Figure 2.2.12. After eliminating Column 3, Row 2 is dominated by Row 1.
🔗

Again, in the reduced game it is easy to determine what each player should do.

🔗

Activity 2.2.1. Check equilibrium pairs.

Check that the strategy pairs we determined in Example 2.2.5 and Example 2.2.7 are, in fact, equilibrium pairs.

🔗

Eliminating Dominated Strategies.

Given a zero-sum game matrix with Player 1’s payoffs. We find a dominated strategy with the following process. Note, you can compare either rows or columns first.

Choose two rows.
🔗

🔗
Compare the corresponding values in the two rows.
🔗

🔗
If in each comparison, one row has values less than or equal to the values in the other row, eliminate the row with the smaller values.
🔗

🔗

🔗

Choose two columns.
🔗

🔗
Compare the corresponding values in the two columns.
🔗

🔗
If in each comparison, one column has values greater than or equal to the values in the other column, eliminate the column with the larger values.
🔗

🔗

🔗

Once you have eliminated a row or column, you can repeat the process with the remaining rows or columns, ignoring any eliminated values. The process of elimininating dominated strategies is helpful for simplifying the game.

🔗

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

🔗

Activity 2.2.2. Eliminating dominated strategies.

Use the idea of eliminating dominated strategies to determine what each player should do in the Arnold/ Bainbridge examples in Table 2.1.10, Table 2.1.12, and Table 2.1.14. Do you get the same strategy pairs as you determined in the related activities (Activity 2.1.1, Activity 2.1.2, Activity 2.1.3)?

🔗

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

🔗

Activity 2.2.3. More practice with dominated strategies.

Use the idea of eliminating dominated strategies to determine any equilibrium pairs in the zero-sum game given in Table 2.2.13. Note, since it is a zero-sum game we need only show Player 1’s payoffs. Explain all the steps in your solution. If you are unable to find an equilibrium pair, explain what goes wrong.

🔗

Table 2.2.13. Payoff matrix for Activity 2.2.3.

🔗

		Player 2
		W	X	Y	Z
	A	\(1\)	\(0\)	\(0\)	\(10\)
Player 1	B	\(-1\)	\(0\)	\(-2\)	\(9\)
	C	\(1\)	\(1\)	\(1\)	\(8\)
	D	\(-2\)	\(0\)	\(0\)	\(7\)

🔗

Activity 2.2.4. Determine equilibrium pairs.

Determine any equilibrium pairs in the zero-sum game given in Table 2.2.14. Explain all the steps in your solution. If you are unable to find an equilibrium pair, explain what goes wrong.

🔗

Table 2.2.14. Payoff matrix for Activity 2.2.4.

🔗

		Player 2
		W	X	Y	Z
	A	\(1\)	\(2\)	\(3\)	\(4\)
Player 1	B	\(0\)	\(-1\)	\(0\)	\(5\)
	C	\(-1\)	\(3\)	\(2\)	\(4\)
	D	\(0\)	\(1\)	\(-1\)	\(1\)

🔗

Activity 2.2.5. Practice finding equilibrium pairs.

Determine any equilibrium pairs in the zero-sum game given in Table 2.2.15. Explain all the steps in your solution. If you are unable to find an equilibrium pair, explain what goes wrong.

🔗

Table 2.2.15. Payoff matrix for Activity 2.2.5.

🔗

		Player 2
		W	X	Y	Z
	A	\(-2\)	\(0\)	\(3\)	\(20\)
Player 1	B	\(1\)	\(-2\)	\(-3\)	\(0\)
	C	\(10\)	\(-10\)	\(-1\)	\(1\)
	D	\(0\)	\(0\)	\(10\)	\(15\)

🔗

Activity 2.2.6. A more challenging example.

Determine any equilibrium pairs in the zero-sum game given in Table 2.2.16. Explain all the steps in your solution. If you are unable to find an equilibrium pair, explain what goes wrong.

🔗

Table 2.2.16. Payoff matrix for Activity 2.2.6.

🔗

		Player 2
		W	X	Y	Z
	A	\(-2\)	\(0\)	\(3\)	\(20\)
Player 1	B	\(1\)	\(-2\)	\(-5\)	\(-3\)
	C	\(10\)	\(-10\)	\(-1\)	\(1\)
	D	\(0\)	\(0\)	\(10\)	\(8\)

🔗

Chances are you had trouble determining an equilibrium pair for the game in Activity 2.2.6. 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.

🔗

Subsection 2.2.3 Maximin and Minimax Strategies

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.

🔗

Example 2.2.17. Playing Against the Best.

Assume you are Player 1, and you are playing against this “infinitely smart” Player 2. Consider the game in Table 2.2.13. If you pick row A, what will Player 2 do? Player 2 will pick column X or Y. Try this for each of the rows. Which row is your best choice? If you pick A, you will get \(0\text{;}\) if you pick B, you will get \(-2\text{;}\) if you pick C, you will get \(1\text{;}\) and if you pick D you will get \(-2\text{.}\) Thus, your best choice is to choose C and get \(1\text{.}\) Now assume you are Player 2, and Player 1 is “infinitely smart.” Which column is your best choice? If you pick W, Player 1 will get \(1\) (you will get \(-1\)); if you pick X, Player 1 will get \(1\text{;}\) if you pick Y, Player 1 will get \(1\text{;}\) and if you pick Z, Player 1 will get \(10\text{.}\) Thus, you can choose W, X, or Y (since you want Player 1 to win the least) and get \(-1\text{.}\)

🔗

Activity 2.2.7. A new method.

Using the method described in Example 2.2.17, determine what each player should do in the game in Table 2.2.14.

🔗

Activity 2.2.8. More practice with the new method.

Using the method described in Example 2.2.17, determine what each player should do in the game in Table 2.2.15.

🔗

After working through a few examples can you describe more generally the process used in Example 2.2.17? 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?

🔗

Activity 2.2.9. Generalizing the new method.

Generalize the method described in Example 2.2.17. In other words, give a general rule for how Player 1 should determine his or her best move. Do the same for Player 2.

🔗

Activity 2.2.10. The new method and equlibrium points.

What do you notice about using this method on the games in Table 2.2.13, Table 2.2.14, and Table 2.2.15? Is the solution an equilibrium pair?

🔗

Activity 2.2.11. The new method on the challenging example.

Now try this method on the elusive payoff matrix in Table 2.2.16. What should each player do? Do you think we get an equilibrium pair? Explain.

🔗

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 activities explore these questions.

🔗

Finding the Maximin and Minimax Strategies.

Given a zero-sum game matrix with Player 1’s payoffs. We find the maximin strategy with the following process.

Find the smallest value in each row.
🔗

🔗
From the smallest values you found in step (1), choose the largest.
🔗

🔗
Player 1 chooses the row corresponding to the value found in (2).
🔗

🔗

🔗

Given a zero-sum game matrix with Player 1’s payoffs. We find the minimax strategy with the following process.

Find the largest value in each column.
🔗

🔗
From the largest values you found in step (1), choose the smallest.
🔗

🔗
Player 2 chooses the column corresponding to the value found in (2).
🔗

🔗

🔗

Since we often will look for the maximin strategy for Player 1 and the minimax strategy for Player 2 in a game, this strategy pair will be referred to as the maximin/minimax strategy (or strategy pair).

🔗

Activity 2.2.12. Look for dominated strategies.

Let’s consider another game matrix, given in Table 2.2.18. Explain why you cannot use dominated strategies to find an equilibrium pair. Do you think there is an equilibrium pair for this game (why or why not)?

🔗

Table 2.2.18. Payoff matrix for Activity 2.2.12.

🔗

		Player 2
		W	X	Y	Z
	A	\(-2\)	\(0\)	\(3\)	\(20\)
Player 1	B	\(1\)	\(2\)	\(-3\)	\(0\)
	C	\(10\)	\(-10\)	\(-1\)	\(1\)
	D	\(0\)	\(0\)	\(10\)	\(15\)

🔗

Activity 2.2.13. Find the maximin/minimax strategy.

If both players use the maximin/ minimax strategy, what is the outcome of the game in Table 2.2.18?

🔗

Activity 2.2.14. Predicting a maximin strategy.

In the game in Table 2.2.18, if Player 1’s opponent can guess that Player 1 will choose to use a maximin strategy, is Player 1 better off not using the maximin strategy?

🔗

Activity 2.2.15. Deviating from the maximin/minimax strategy.

Suppose both players initially decide to use the maximin/minimax strategy in the game in Table 2.2.18. Is Player 1 better off choosing a different strategy? If Player 2 guesses a change, is Player 2 better off changing strategies? Continue this line of reasoning for several iterations. What strategies do each of the players choose? Is at least one player always better off switching strategies? Can we conclude that the maximin/ minimax strategy does not lead to an equilibrium pair?

🔗

Activity 2.2.16. Comparing examples.

Compare the game in Activity 2.2.12 to what happens in Activity 2.2.3, Activity 2.2.4, and Activity 2.2.5. Can you identify any key differences between the games in Activity 2.2.12 and Activity 2.2.3, Activity 2.2.4, and Activity 2.2.5?

🔗

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.

🔗

Reading Questions 2.2.4 Check Your Understanding

1.

Suppose we are looking for dominated strategies in the following matrix.

Table 2.2.19.

🔗

	Player 2
Player 1	\(-1\)	\(0\)	\(2\)
	\(5\)	\(-2\)	\(1\)
	\(0\)	\(1\)	\(4\)

🔗

Which row can we eliminate?

🔗

Row 1
🔗
Row 1 is dominated by Row 3.
Row 2
🔗
Row 2 is not dominated by either Row 1 or Row 3.
Row 3
🔗
Row 3 is not dominated by either Row 1 or Row 2.
We can’t eliminate any rows.
🔗
There is a dominated row.

🔗

2.

Suppose we are looking for dominated strategies in the matrix Table 2.2.19.

🔗

Which column can we eliminate?

🔗

Column 1
🔗
Column 1 is not dominated by Column 2 or Column 3.
Column 2
🔗
Column 2 is not dominated by either Column 1 or Column 3. Remember Player 2 prefers smaller values since these are PLayer 1’s payoffs.
Column 3
🔗
Column 3 is dominated by Column 2.
We can’t eliminate any columns.
🔗
There is a dominated column.