15.2 15.1 Two-Person Total-Conflict Games: Pure Strategies

The application of game theory requires modeling some interaction as a game by determining the players, their strategies—a list of options or courses of action available to them—and the possible outcomes, which describe the consequences of their choices. We assume that the players have preferences for the outcomes, which are represented by numbers called payoffs. Game theory analyzes the rational choice of strategies—that is, how players select strategies to obtain preferred outcomes. In this section and the next, we start with the simplest type of two-person games: total-conflict games, in which what one player wins the other player loses.

EXAMPLE 1 Determining Work Schedule and Location

After moving to a new town so that Lisa can take a job as a newspaper editor, newlyweds Mark and Lisa must decide which position Mark should accept as an emergency room nurse. There are three area hospitals, each with openings for three 8-hour shifts. Concerned about saving for a down payment on a house, Mark wants to choose the shift and hospital location that pays the most money. Lisa is less concerned about finances and more concerned about their quality of life. A tougher schedule and a more active emergency room translate into a higher hourly wage, but a lower quality of life. In this way, their preferences are diametrically opposed. What is better for Mark is worse for Lisa, and vice versa.

Lisa and Mark make a table with the shifts listed along the top row and the hospitals listed along the left column (see Table 15.1). The entries in the table give the hourly wage Mark will receive for working at the hospital, given by the row, and for the shift, given by the column. The hourly wages are the payoffs to Mark for the different outcomes.

Table 15.1: TABLE 15.1 Hourly Wage (in Dollars) for the 9 Hospital-Shift Possibilities
Shifts
Hospitals 12 A.M.–8 A.M. 8 A.M.–4 P.M. 4 P.M.–12 A.M.
Rural 23 24 22
Suburban 27 26 29
Downtown 30 23 25

Payoff Matrix DEFINITION

A payoff matrix (illustrated by Table 15.1) is a table whose rows and columns correspond to the strategies of the two players. For a total-conflict game, the numerical entries of the matrix give the payoffs to the row player when these strategies are chosen.

Lisa and Mark turn the table into a competitive game to determine which job Mark should accept—such a game represented by a payoff matrix is called a game in strategic form. Mark will select one of the three hospitals—Rural, Suburban, or Downtown—and Lisa will simultaneously choose one of the three shifts—beginning at 12 A.M., 8 A.M., or 4 P.M. Because their choices will be made simultaneously, neither knows beforehand what the other will do.

624

Because Lisa’s preferences are diametrically opposed to Mark’s preferences, Lisa’s payoffs are represented by −1 times the hourly wage. For example, if the outcome is for Mark to work at the rural hospital from 12 A.M. to 8 A.M., then Mark’s payoff is 23 I while Lisa’s payoff is −23. This is the origin of the term zero-sum game.

Zero-Sum Game DEFINITION

A zero-sum game is one in which the payoff to one player is the negative of the corresponding payoff to the other, so the sum of the payoffs to the two players is always 0.

Zero-sum games are total-conflict games in which what one player wins the other loses. But not all total-conflict games are zero-sum—in particular, the sum of the payoffs could be some constant other than 0. Nevertheless, the strategic nature of these two types of games is the same.

Continuing the game in Example 1, Mark, worried that Lisa will choose a shift that will result in lower pay, tries to determine the highest hourly wage he can guarantee by picking one of the three hospitals. For each choice of a hospital, this means considering the worst-case (lowest) hourly wage. These are the dollar amounts 22, 26, and 23, which are the respective row minima, indicated in the right-hand column of Table 15.2. He notes that the highest of these values is 26. By choosing the corresponding suburban hospital, Mark can guarantee himself an hourly wage of $26 per hour.

Table 15.2: TABLE 15.2 Hourly Wage (in Dollars) from Table 15.1, with the Row Minima (Maximum Circled) and Column Maxima (Minimum Circled)
Lisa Shifts
Hospitals 12 A.M.–8 A.M. 8 A.M.–4 P.M. 4 P.M.–12 A.M. Row Minima
Mark Rural 23 24 22 22
Suburban 27 26 29 26
Downtown 30 23 25 23
Column
Maxima
30 26 29

Maximin DEFINITION

The maximin is the maximum value of the minimum numbers in the rows in a table. The strategy of the row player—Mark, in this case—that corresponds to the maximin is called its maximin strategy.

The number 26 in the right-hand column of Table 15.2, which is circled, is the maximin. The suburban hospital is Mark’s maximin strategy.

625

Self Check 1

In the following table, the payoffs represent gains to the row player and losses to the column player. This makes the game a zero-sum game like the game between Mark and Lisa. Calculate the row minima to help determine which row is the maximin strategy for the game represented by the table.

9 6 2
7 8 5
4 1 3

  • The row minima for rows 1, 2, and 3 are 2, 5, and 1, respectively. Because 5 is the maximum of the minimum values, row 2 is the associated minimax strategy.

Lisa likewise does a worst-case analysis and lists the highest—for her, the worst in terms of quality of life—hourly wages. These numbers, 30, 26, and 29, are the column maxima and are listed in the bottom row of Table 15.2. From Lisa’s point of view, the best of these outcomes is 26. If she picks the 8 A.M. to 4 P.M. shift, then Lisa is guaranteed that Mark’s workload will result in him earning an hourly wage of no more than $26 per hour.

Minimax DEFINITION

The minimax is the minimum value of the maximum numbers in the columns. The strategy of the column player—Lisa, in this case—that corresponds to the minimax is called its minimax strategy.

The number 26 at the bottom row of Table 15.2, which is circled, is the minimax. The 8 A.M. to 4 P.M. shift is Lisa’s minimax strategy.

Self Check 2

In the following table, the payoffs represent gains to the row player and losses to column player; again, this is a zero-sum game. Calculate the column maxima to help determine which column is the minimax strategy for the game represented by the table.

9 6 2
7 8 5
4 1 3

  • The column maxima for columns 1, 2, and 3 are 9, 8, and 5, respectively. Because 5 is the minimum of the maximum values, column 3 is the associated maximin strategy.

To summarize the results of the game in Example 1, Mark has a strategy that will ensure an hourly wage of $26 per hour or more, and Lisa has a strategy that will ensure an hourly wage of $26 per hour or less. The hourly wage of $26 per hour is, simultaneously, the lowest amount Mark can earn at the suburban hospital and the most he can earn for working the 8 A.M. to 4 P.M. shift. In other words, the maximin and the minimax are both equal to $26 per hour for this location/schedule game.

626

Saddlepoint and Value DEFINITION

For a zero-sum game, when a row minimum and a column maximum are the same, the resulting payoff is called a saddlepoint. In this case, it is also called the value of the game.

To see the reason for the term saddlepoint, consider the saddle-shaped payoff surface of Mark’s hourly wage shown in Figure 15.1. The middle point on a horse saddle (26) is simultaneously the lowest point along the spine of the horse (because 27 and 29 are higher) and the highest point between the rider’s legs (because 23 and 24 are lower). The saddle structure assures Mark an hourly wage of $26 an hour, which is simultaneously the maximin and minimax. If a game has a saddlepoint, players can guarantee the saddlepoint payoff by choosing their maximin and minimax strategies.

image
Figure 15.1: Figure 15.1 The payoff surface shows Mark’s hourly wage as it depends on Mark’s and Lisa’s possible choices (in dollars per hour).

Self Check 3

In the following table, the payoffs represent gains to the row player and losses to the column player. What is the value for the game represented by the table?

9 6 2
7 8 5
4 1 3

  • The game has a saddlepoint because the maximum of the minimum row values is equal to the minimum of the maximum column values. The value of the game is 5, which is the payoff when the players follow the maximin and minimax strategies.

There is no need for secrecy in a game with a saddlepoint. For the location/schedule game, Lisa has no incentive to change her selection for Mark’s schedule, even if Mark were to reveal that he is going to select the suburban hospital, because $26 is the lowest hourly wage at the suburban hospital. Similarly, Mark has no incentive to change his selection of a hospital location, even if Lisa were to reveal that she is going to select the 8 A.M. to 4 P.M. shift, because $26 is the highest hourly wage for the 8 A.M. to 4 P.M. shift. Hence, the value of $26 per hour occurs when Mark picks the suburban hospital and Lisa picks the 8 A.M. to 4 P.M. time slot.

627

In games with saddlepoints, players’ worst-case analyses lead to the best guaranteed outcome—in the sense that each player can ensure that he or she does not do worse than a certain amount (26 in our example) and may even do better (if the opponent deviates from a maximin or minimax strategy). Zero-sum games without saddlepoints also have a “value,” as we shall see later.

Another well-known game with a saddlepoint is tic-tac-toe. Two players alternately place an X or an O, respectively, in one of the unoccupied spaces in a grid with 9 cells. The winner is the first player to have three Xs, or three Os, in the same row, in the same column, or along a diagonal; if no player does this when all cells are filled in, the game ends in a tie.

An explicit list of all strategies for either the first- or second-moving player in tic-tac-toe is long and complicated because it specifies a complete plan for all possible contingencies that can arise. For the first-moving player, for example, a strategy might be to “put an X in the middle cell, then an X in the corner if your opponent puts an O in a noncorner cell,” and so on. While young children initially find this game fun to play, before long they discover that each player can always prevent the other player from winning by forcing a tie, making the game uninteresting. Unlike the game between Mark and Lisa, the list of possible strategies in tic-tac-toe is lengthy, but only those that force a tie, it turns out, are a saddlepoint. Tic-tac-toe is an example of a combinatorial game. These two- player games have players alternating moves without the use of any randomizing elements such as a die.

EXAMPLE 2 The Restricted Location/Schedule Game

Assume that Mark and Lisa revisit the location/schedule game once Mark and Lisa have their first child. To limit the number of hours their child must spend in daycare, Mark and Lisa agree that Mark cannot work the 8 A.M. to 4 P.M. shift, because this conflicts with Lisa’s work schedule. A new game is formed by eliminating the 8 A.M. to 4 P.M. shift column in Table 15.1. As before, Mark and Lisa can each do a worst-case analysis. Mark is worried about the minimum number in each row, and Lisa is concerned with the maximum number in each column. The result, along with minimum row and maximum column information, appears in Table 15.3.

Table 15.6: TABLE 15.3 Hourly Wage (in dollars) from Table 15.1, with the Row Minima (Maximum Circled) and Column Maxima (Minimum Circled)
Lisa Shifts
Hospitals 12 A.M.–8 A.M. 4 P.M.–12 A.M. Row Minima
Mark Rural 23 22 22
Suburban 27 29 27
Downtown 30 25 25
Column Maxima 30 29

628

Mark sees that his maximin is now 27, so he can guarantee an hourly wage of $27 per hour, instead of the $26 per hour from before. Lisa notices that her minimax is now 29. When the maximin and the minimax are not the same, then the game does not have a saddlepoint, but it does have a value (described in the next section).

If Mark plays his maximin strategy, the suburban hospital, and Lisa plays her minimax strategy, the 4 P.M. to 12 A.M. shift, then the resulting payoff is 29. However, Lisa may be motivated to gamble in this case by playing her other strategy, the 12 A.M. to 8 A.M. shift. If she switches while Mark still selects the suburban hospital, then Mark’s hourly wage will decrease to $27 per hour.

If Mark thinks that Lisa will select the 12 A.M. to 8 A.M. shift, then he has an incentive to select the downtown hospital instead. The highest hourly wage that Mark can receive is by working the 12 A.M. to 8 A.M. shift at the downtown hospital.

However, if Lisa looks far enough ahead, she can respond to Mark’s reasoning by playing her minimax strategy. The result is $25 per hour if Mark selects the downtown hospital and Lisa selects the 4 P.M. to 12 A.M. shift. The $25 per hour is less than the $29 per hour when Lisa plays her minimax strategy and Mark plays his maximin strategy. This ? means that Mark has an incentive to return to his maximin strategy.

In two-player games that have saddlepoints, like our original location/schedule game and tic-tac-toe, each player can calculate the maximin and minimax strategies for both players before the game is even played. Once the solution has been determined by either mathematical analysis or practical experience (as was probably true of tic-tac-toe), there may be little interest in actually playing the game.

But this is decidedly not the case for much more complex games, like chess, whose solution has not yet been determined—and is unlikely to be determined in the foreseeable future. Even though computers are able to beat world champions, the computer’s winning moves will not necessarily be optimal against those of all other opponents. Nevertheless, we know that chess, like tic-tac-toe, has a saddle- point. (All games of perfect information, in which the players know each other’s moves at every step, have a saddlepoint.) What we do not know is whether it yields a win for white, a win for black, or a draw.

Unlike chess, many games, such as the modified location/schedule game (the column game), do not have an outcome that can always be guaranteed. These games, which include poker, involve uncertainty and risk. In such games, one does not want to have one’s strategy detected in advance because this information can be exploited by an opponent. It is no surprise, then, that poker players try to keep a “poker face,” revealing nothing about their likely choices. But keeping a poker face does not tell the players what to actually do in the game, such as how many cards to ask for in draw poker.

We will show that there are optimal ways to play two-person total-conflict games without a saddlepoint so as not to reveal one’s choices. But their solution is by no means as straightforward as that of games with a saddlepoint.