Chapter 10
Strategic Zero-Sum Games with Perfect Information

So far, we have focused most of our attention on random games where the player is pitted against a non-intelligent opponent. We now turn our attention to strategic games, in which two rational opponents attempt to outsmart each other. In this type of situation, players still attempt to maximize their respective utilities, but they now need to cope with their opponent's ability to anticipate their actions and act accordingly. Because of this, the process of choosing the optimal action involves predicting what our opponent will prefer when faced with his own options, and our own optimal strategies need to be devised by conditioning on what we expect our opponent to rationally prefer.

To emphasize the difference, compare the games of blackjack and poker. While playing blackjack, we designed our basic strategy knowing that the dealer will always stay with 17 or more and hit with 16 or less. That made it reasonable for us to stay with relatively low numbers (say 14) as long as the dealer's face-up card suggested that he had a good chance of going bust (e.g., if the dealer shows a 6). This is so because the house always plays the same strategy, and the dealer will hit with 16 even if our current hand is only 14. This is different from the situation in poker, where we need to account for the fact that the other players might be bluffing when they raise their bets.

We start by considering the simplest possible strategic game, which includes two intelligent opponents who try to outwit each other in a game, where the winnings of one player translate into losses for the other. These types of games are called strategic zero-sum games because one player's profit equals the loss of its opponents.

10.1 Games with Dominant Strategies

Consider the following strategic “game” involving two companies that sell mineral water. We will call the companies Pevier and Errian. Each company has a fixed cost of $5000 per period, regardless of whether they sell anything or not. The two companies are competing for the same market, and each firm must choose a high price ($2 per bottle) or a low price ($1 per bottle). The rules of the game are:

• At a price of $2, a total of 5000 bottles can be sold for a total revenue of $10,000.
• At a price of $1, a total of 10,000 bottles can be sold for a total revenue of $10,000.
• If both companies charge the same price, they split the sales evenly between them.
• If one company charges a higher price, the company with the lower price sells the whole amount, and the company with the higher price sells nothing.
• Both companies aim at maximizing their profit, which is simply the revenue from sales minus the $5000 in fixed costs.

Under these rules, there are four situations that could arise:

• If both companies charge the high price ($2), then 5000 bottles are sold at a price of $2 each, for a total revenue of $10,000 that is split evenly between both companies. Therefore, each company has a revenue of $5000 and a net profit of $0 once the fixed costs are subtracted.
• If both companies charge the low price ($1), then 10,000 bottles are sold at a price of $1 each. Again the total revenue is $10,000, which is split evenly between Errian and Pevier. As before, this leads to both companies having a net profit of $0.
• If Pevier charges the high price and Errian the low price, then all the revenue ($10,000) goes to Errian, which makes a net profit of $5000. In turn, this means that Pevier has no revenue and makes a net loss of $5000.
• Under the same logic, if Pevier charges the low price and Errian charges the high price, then Pevier makes $5000 net profit and Errian loses $5000.

Table 10.1 summarizes the utility (in this case, profit) that each company gets under each of the four combinations of strategies. This type of table is called the normal form of the game. The first number on each cell represents Errian's net profit for that combination of strategies, while the second number corresponds to Pevier's net profit. Note that, in every box, the sum of the two numbers is the same (zero in this case). Indeed, this game is an example of a zero-sum game.

Zero-Sum Games

In zero-sum games, the sum of utilities for all players in the game, for every combination of strategies, is constant (typically, but not necessarily, zero). More informally, in a zero-sum, a player benefits only at the equal expense of its opponents.

Table 10.1 Profits in the game between Pevier and Errian

		Pevier
		Low price	High price
Errian	Low price
		High price

Our goal when dealing with strategic games such as this is to predict how each of the player will behave (in our running example, what price they will choose). We call this prediction the solution of the game. To construct our solution, we assume that both companies anticipate the actions of their opponent and act accordingly to try to maximize their own profit. To do this, we first look at the problem from Pevier's perspective by exploring the consequences of its choices:

• First, assume that the Errian decides to set the price of its product to $1 (i.e., we are in the first row of Table 10.1). In this case, Pevier needs to pick between losing $5000 (if it chooses the high price) or making no profit (if it chooses the low price). Hence, Pevier's best option (called its best response) in this case is to set its price to $1.
• Next, assume that the Errian decides to set the price of its product to $2 (i.e., we are in the second row of Table 10.1). Therefore, Pevier will either make no profit (if it chooses to price their water at $2) or it could potentially make $5000 profit if it decides to set the price to $1. Again, Pevier's best alternative is to set the price of its water to $1.

Hence, no matter what Errian decides to do, Pevier's optimal decision is to set a low price (), so Errian can reasonably expect that Pevier will do exactly that. Because the game is symmetric (i.e., the same reasoning applies if we look at the problem from Errian's perspective), we can predict that Errian will also select to price its water at the low price of $1 (). In summary, we can be fairly certain that the rational outcome of the game is for both players to select the low price for their product, which we represent as . This problem is an example of a game where both players have a dominant strategy.

Dominant Strategy

A dominant strategy is a strategy that is at least as good as the alternatives in all circumstances and better in some. When a rational player has a dominant strategy, we can be fairly sure that he will play exactly that strategy.

The solution given by the dominant strategies we just found has some interesting properties. For example, imagine that the two companies reassess the price of their products every 6 months (i.e., they play the game multiple times) and they used the strategy in the previous round. Then, as long as they believe that the other player will stick to the strategy used this round, none of them has an incentive to change the strategy in the next one. That is, unilateral changes in strategy are not beneficial to any of the players, and therefore extremely unlikely. Note that this property is not shared by any of the other three strategies. In addition, each player's strategy is the best possible response to the other's player action (if Errian sets a low price, the best response that Pevier can adopt is also a low price, and vice-versa). We call pairs of strategies that satisfy these two properties Nash equilibria, in honor of John Forbes Nash, whose life has been portrayed in the movie A Beautiful mind.

Nash Equilibrium

In a two-person game of perfect information, a pair of strategies (one for each player) is called a Nash equilibrium if they are mutual best responses.

We can rationalize Nash equilibria as the consequence of players learning after playing the game repeatedly. For example, assume that Errian and Pevier play their game multiple times and that in the beginning both players adopt the high-price strategy. After acting in this way for a while, one of the players (say, Errian) is likely to wise up and realize that they can make money out of their opponent by changing to a low price strategy in order to minimize loses. But once the high-price holdout (Pevier) realizes that the other player will stick to the low price, they will also turn to a low price strategy. Once both players have decided to charge a low price, there is no reason for them to change their strategies unilaterally. Note, however, that, this interpretation is useful only for games that can be repeated over and over, just as in the case of the frequentist interpretation of probability discussed in Chapter 1.

The strategies we have used so far involve players repeatedly using one of their actions. This type of strategies are called pure strategies.

Pure-strategy Nash equilibrium

We say that a Nash equilibrium involves pure strategies if, in equilibrium, each player always takes the same action.

Note that the process we used to obtain our solution to the game makes a few assumptions about the players. First, we are assuming that all players are rational (i.e., they maximize some utility function). Second, we assume that all players know that the other players are rational, follow the same rules, and know what the utility function of other players are (i.e., rationality and utility functions are common knowledge). Finally, we are assuming that players act simultaneously without the knowledge of the other player's choice (in the Perrier vs Errian example this last assumption did not make a difference, but in the future it might). Unless noted otherwise, we will retain these assumptions in the remainder of this book.

10.2 Solving Games with Dominant and Dominated Strategies

Let's now consider another example related to politics. Two presidential candidates (call them Ling and Matt) are engaged in a debate, and they need to decide where they stand on two conflicting issues (e.g., whether to raise income taxes or not) or whether they will dodge the issue. Assume that, after extensive polls, there is agreement among political analysts on the percentage of the vote each candidate will receive for each combination of positions. Table 10.2 presents these percentages.

Table 10.2 Poll results for Matt versus Ling (first scenario)

		Matt
		Increase	No increase	Dodge issue
Ling	Increase	(45%, 55%)	(50%, 50%)	(40%, 60%)
		No increase	(60%, 40%)	(55%, 45%)	(50%, 50%)
		Dodge issue	(45%, 55%)	(55%, 45%)	(40%, 60%)

As stated earlier, the first number in each cell represents Ling's percentage of the vote, and the second represents Matt's percentage. Even though the sum of the entries in each cell is 100% instead of 0, this is still a zero-sum game. Indeed, since the solution of the game depends on the ordering of the preferences but not their exact values, we could subtract 50 from every entry in Table 10.2, making the values in each entry add to 0 without altering the solution.

Let's consider first the game from Matt's perspective and find his best response to each of Ling's actions. If Ling supports an increase in taxes, Matt should dodge the issue, leaving him with 60% of the vote. On the other hand, if Ling decides not to support an increase in taxes, Matt should also dodge the issue, in which case both candidates will tie. Finally, if Ling decides to dodge the issue, Matt should yet again dodge the issue in order to get 60% of the vote. These observations are summarized in Table 10.3.

Table 10.3 Best responses for Matt (first scenario)

If Ling decides ...	Matt should ...
... to support an increase in taxes,	... dodge the issue.
... not to support an increase in taxes,	... dodge the issue.
... to dodge the discussion,	... dodge the issue.

Let's turn to Ling's best responses. If Matt decides to support an increase in taxes, Ling should not support it, netting her 60% of the vote. If Matt decides not to support the tax increase, then Ling could either not support it or dodge the issue, which would leave her with 55% of the vote. Finally, if Matt dodges the issue, Ling should not support the increase, again leaving both with 50% of the vote each. Again, we summarize these results in Table 10.4.

Table 10.4 Best responses for Ling (first scenario)

If Matt decides ...	Ling should ...
... to support an increase in taxes,	... not support an increase in taxes.
... not to support an increase in taxes,	... not support it or dodge.
... to dodge the discussion,	... not support an increase in taxes.

Once the best responses have been obtained, the analysis of this game is relatively simple. Note that, no matter what Ling does, Matt should always dodge a discussion about taxes. In addition, note that no matter what Matt does, not supporting a tax increase is always optimal for Ling. In other words, these two strategies are dominant. Therefore, it is reasonable to expect that Ling will not support the increase in taxes, and Matt will avoid any discussion on the topic, leaving the electorate evenly split among the candidates. As before, this solution corresponds to a Nash equilibrium because they are mutual best responses, and therefore there is no incentive for the players to unilaterally alter their strategies.

Consider now a slight modification of this political game where the share of the vote for each candidate is instead given in Table 10.5. In this case, if Ling chooses to support an increase in taxes Matt is better off not supporting the increase. On the other hand, if Ling does not support an increase, Matt should dodge the issue, and if Ling dodges the issue, Matt should not support the increase. From Ling's perspective, if Matt supports an increase, Ling should not support the increase. If Matt does not support the increase, Ling should again not support the increase. Finally, if Matt dodges the issue of tax increases, then Ling should (for a third time) not support the increase. These results are summarized in Tables 10.6 and 10.7.

Table 10.5 Poll results for Matt versus Ling (second scenario)

			Matt
			Increase	No increase	Dodge issue
	Ling	Increase	(45%, 55%)	(10%, 90%)	(40%, 60%)
		No increase	(60%, 40%)	(55%, 45%)	(50%, 50%)
		Dodge issue	(45%, 55%)	(10%, 90%)	(40%, 60%)

Table 10.6 Best responses for Matt (second scenario)

If Ling decides ...	Matt should ...
... to support an increase in taxes,	... not support an increase in taxes.
... not to support an increase in taxes,	... dodge the issue.
... to dodge the discussion,	... not support an increase in taxes.

Table 10.7 Best responses for Ling (second scenario)

If Matt decides ...	Ling should ...
... to support an increase in taxes,	... not support an increase in taxes.
... not to support an increase in taxes,	... not support it or dodge.
... to dodge the discussion,	... not support an increase in taxes.

Unlike our previous example, Matt does not have a dominant strategy. This might suggest that solving the game is much harder. However, this is not the case. Not supporting the increase is a dominant strategy for Ling; consequently, we can be sure that she will adopt it. Once we know that Ling will not support an increase on taxes, our previous discussion suggests that Matt's rational reaction should be to dodge the issue, which again leads to both candidates splitting the vote 50% each. This solution is again a Nash equilibrium.

Let's consider one last set of payoffs, as given in Table 10.8. Tables 10.9 and 10.10 contain the best responses. In this case, none of the players has a dominant strategy, that is, it is not immediately obvious what any given player should do. However, it is clear what Matt should not do. Indeed, Table 10.10 suggests that Matt should never dodge the issue, as dodging is never a best response. Similarly, from Table 10.9 note that supporting a tax increase is never a good idea for Ling. This observation indicates that dodging (in the case of Matt) and supporting the tax increase (in the case of Ling) are dominated strategies.

Dominated Strategy

A strategy that is no better than the alternatives in all circumstances, and worse in some, is called a dominated strategy. If a player has a dominated strategy, we can be fairly certain that they will never play it.

Table 10.8 Poll results for Matt versus Ling (third scenario)

			Matt
			Increase	No increase	Dodge issue
	Ling	Increase	(35%, 65%)	(10%, 90%)	(60%, 40%)
		No increase	(45%, 55%)	(55%, 45%)	(50%, 50%)
		Dodge issue	(40%, 60%)	(10%, 90%)	(65%, 35%)

Table 10.9 Best responses for Ling (third scenario)

If Ling decides ...	Matt should ...
... to support an increase in taxes,	... not support an increase in taxes.
... not to support an increase in taxes,	... support an increase in taxes.
... to dodge the discussion,	... not support an increase in taxes.

Table 10.10 Best responses for Matt (third scenario)

If Matt decides ...	Ling should ...
... to support an increase in taxes,	... not support an increase in taxes.
... not to support an increase in taxes,	... not support an increase in taxes.
... to dodge the discussion,	... also dodge the discussion.

Finding dominated strategies can help us solve a game by reducing the number of actions that we need to consider. Indeed, since Matt will never dodge the issue and Ling will never support an increase in taxes, we could simply eliminate the corresponding row and column from the table and work with the reduced game (see Table 10.11). In this reduced game, we only need to consider Ling's reactions to Matt supporting or not supporting an increase in taxes and Matt's reactions to Ling not supporting the increase or dodging the issue. Hence, it is easy to see that no matter which rational option Matt chooses, Ling's optimal response is not to support an increase in taxes. In other words, even though the original game did not have any dominant strategy, once the dominated strategies are eliminated, not supporting a tax increase becomes a dominant strategy for Ling. The final solution of the game is obtained by noting that Matt's best response to Ling's dominant strategy of not supporting the tax is for Matt to support it, which will lead to 45% of the electorate to support Ling and 55% to support Matt.

Table 10.11 Reduced table for poll results for Matt versus Ling

		Matt
		Increase	No increase
Ling	No increase	(45%, 55%)	(55%, 45%)
		Dodge issue	(40%, 60%)	(10%, 90%)

10.3 General Solutions for Two Person Zero-Sum Games

When dominant or dominated strategies are present, the solution of a game can often be obtained by applying the two insights we discussed earlier:

• If a strategy is dominant for one player, we can be sure that she will use it, and therefore we only need to look at the best response of the other player to the dominant strategy.
• If a strategy is dominated for one player, we can simply remove the corresponding column or row of the matrix and work with the reduced game.

However, not all games have dominant or dominated strategies, so these tools are not always enough to solve a non-zero sum game. A more general approach to solving games uses the fact that a Nash equilibrium corresponds to the pair of strategies that are mutual best responses. For example, consider the two-person game whose outcomes are presented in Table 10.12. The best responses for each of the two players are summarized in Tables 10.13 and 10.14.

Table 10.12 A game without dominant or dominated strategies

			Player 2
	Player 1

Table 10.13 Best responses for Player 1 in our game without dominant or dominated strategies

If Player 2 chooses ...	Player 1 should choose ...
... ,	... .
... ,	... .
... ,	... .

Table 10.14 Best responses for Player 2 in our game without dominant or dominated strategies

If Player 1 chooses ...	Player 2 should choose ...
... ,	... .
... ,	... .
... ,	... .

It should be clear from the tables of best responses that there are no dominant or dominated strategies for any of the players. However, note that the pair is made of mutual best responses ( is the best response to and is the best response to ), and that this is the only pair with this characteristic. Hence the pair is the unique pure-strategy Nash equilibrium for this game.

It is also important to note that Nash equilibria might not be unique. For example, consider the game represented in Table 10.15, which has four equilibria: , , , and . In the case of zero-sum games, all the equilibria must have the same payoffs, so players will be indifferent among them (but for more general games such as the ones discussed in Chapter 12, the payoffs might be different).

Table 10.15 Example of a game with multiple equilibria

			Player 2
	Player 1

10.4 Exercises

1. 1. A recent New York Times article contained the following statement: “The answer is simple because the zero-sum game nature of our politics demands that one party represent progress and the other the status quo.” Explain what the phrase “zero-sum game” means in this context.

2. 2. The following table corresponds to the payoff of a zero-sum game to Player A, when A plays the strategy in the row and B corresponds to the strategy in the column.

   			Player B
   	Player A		19	0	1
   			11	9	3
   			23	7

   1. a. Is there any dominated strategy for either player?
   2. b. Is there any dominant strategy for either player?
   3. c. What is an equilibrium strategy for this game?
   4. d. What is the payoff for the game?

3. 3. The following table corresponds to the payoff of a zero-sum game to player Liza, when Liza plays the strategy in the row and Jose choices correspond to the strategies in the columns.

   			Jose
   			1	2	3
   	Liza	1		1	1
   		2		0	2
   		3			4

   1. a. Is there any dominated strategy for either player?
   2. b. Is there any dominant strategy for either player?
   3. c. What is an equilibrium strategy for this game?
   4. d. What is the payoff for the game?

4. 4. The following table corresponds to the payoff of a zero-sum game to player L. Gaga , when L. Gaga plays the strategy in the row, and the strategies in the columns correspond to choices available to player Shakira.

   			Shakira
   	L. Gaga		2	1	3
   				1	2
   				0	1

   1. a. Is there any dominated strategy for either player?
   2. b. Is there any dominant strategy for either player?
   3. c. What is an equilibrium strategy for this game?
   4. d. What is the payoff for the game?

5. 5. Show that the game presented in Table 10.15 indeed has the four Nash equilibria (A,A), (A,C), (C,A), and (C,C).

6. 6. In a simplified, single-move sword duel, each player has four different moves: two attacking moves (A1 and A2) and two defensive moves (D1 and D2). Attacking move A1 is very effective against attacking move A2 and defensive move D2 (it leads to a gain of 4 and 3 points, respectively, to the player who uses it). Defensive move D1 is very effective against attacking move A1 (leads to a gain of 2 points), it's a poor move against A2 ( point) and is marginally better than defensive move D2 (1 victory point). Finally, defending move does very badly against attacking move A2 ( points). When the two players choose the same move, the result is a draw (0 points each), and whatever one player wins/looses the other player looses/wins (respectively). Is this a two-person zero-sum game? Is there an equilibrium point for this game?

7. 7. Even or odd? is a children's two-person game in Portugal. Players take turns saying “even” (or “odd”); on the count of three, players show a number with their hand; one wins if the sum of both numbers is even and one said “even”, or if the sum is odd and you said odd. A draw occurs if both players guess right, or if both guess wrong. Is this a zero-sum game? Why? Set-up up the game in normal form and see if it has a pure strategy.

8. 8. Two players are bargaining over how to split 1. Both players simultaneously name shares they would like to have, x and y, where 0 ≤ x, y ≤ 1. If the sum of the shares is less than one, each one receives the shares they named. On the other hand, if the sum is greater than 1 , then both players receive zero. Show that a 50%–50% split is a pure-strategy Nash equilibrium for this problem. Is this equilibrium unique? To answer this question, assume that the utility function of the players is strictly monetary (i.e., they do not derive any utility from “screwing” their opponents). Hint: Recall the definition of a Nash equilibrium as a pair of actions that are mutual best responses. Is a 30%–70% split an equilibrium point? Is a 1%–99% split an equilibrium point?