15.3 15.2 Two-Person Total-Conflict Games: Mixed Strategies
Most competitive games do not have a saddlepoint like the one we found in our first location-game example. Rather, as is illustrated in our modified location/schedule game—in which the maximin and minimax are not the same—players must try to keep secret their strategy choices, lest their opponent use this information to his or her advantage.
629
In particular, players must take care to conceal the strategy they will select until the encounter actually takes place, when it is too late for the opponent to alter his or her choice. If the game is repeated, a player will want to vary his or her strategy in order to surprise the opponent.
In parlor games like poker, players often use the tactic of bluffing. This tactic involves a player sometimes raising the stakes when he has a low hand so that opponents cannot guess whether or not his hand is high or low—and may, therefore, miscalculate whether to stay in or drop out of the game. (A player would prefer opponents to stay in when he has a high hand and drop out when he has a low hand.) In military engagements, too, secrecy and even deception are often crucial to success.
In many sporting events, a team tries to surprise or mislead its opposition. A pitcher in baseball will not signal the type of pitch he or she intends to throw in advance, mixing up pitches throughout the game to try to keep the batter off balance. A football team will vary how it approaches two-point conversions, sometimes rushing the ball and other times passing it. A kicker in a penalty shootout of a soccer match will kick the ball sometimes to the left of the goal and sometimes to the right, while the goalie will often guess one side or the other. A kicker-goalie interaction is considered in the following example.
EXAMPLE 3 A Penalty Kick Shootout
After a tie overtime period in a FIFA World Cup soccer match, penalty shootouts are used to determine which team advances to the next round. A penalty shootout consists of five kicks for each team, in alternating order. If at the end of the five kicks, the teams are still tied, then the two teams continue to alternate penalty kicks until the tie is broken—the team that scores when the other doesn’t advances to the next round. Penalty shootouts have even decided the World Cup winner, as when Italy defeated France 5-3 in a shootout in 2006.
In soccer, the goal is 8 feet tall by 24 feet wide. A kick in a penalty shootout is taken at 36 feet from the goal, and the ball travels upwards of 100 miles per hour. Because of the wide goal and the distance and speed that the ball travels, the goalie typically guesses either left or right. Likewise, the kicker decides on either kicking the ball to the goalie’s left or to the goalie’s right. Players vary their kicking techniques; if they don’t, then a well-prepared goalie can learn players’ tendencies to kick to one side or the other. Indeed, Petr Cech saved all five penalty kicks in a penalty shootout by guessing the correct direction, thereby helping Chelsea Football Club of England defeat Bayern Munich of Germany to win the 2012 UEFA European Champions League. Cech had prepared by watching every penalty kick the Bayern Munich players attempted since 2007.
Assume that a particular left-footed kicker can kick the ball either to the goalie’s left or to the goalie’s right and so has two strategies: goalie’s left (denoted by ) or goalie’s right (). The goalie decides between diving to the left or to the right, and likewise has two strategies: left (denoted by ) and right (). Being left-footed, the kicker’s strong side is to kick to the goalie’s left, resulting in a more powerful, but less accurate, shot. The kicker is more accurate when kicking the ball to the right, which results in a less forceful shot. Assume that the kicker’s success rates for the different strategies by the players are given below and that both players know these rates:
630
- 0.2 if the kicker kicks the ball to the goalie’s left () and the goalie dives left ()
- 0.9 if the kicker kicks the ball to the goalie’s left () and the goalie dives right ()
- 0.95 if the kicker kicks the ball to the goalie’s right () and the goalie guesses left ()
- 0.15 if the kicker kicks the ball to the goalie’s right () and the goalie guesses right ()
The kicker’s success rate is the number of goals scored divided by the number of attempts. Hence, 0.2 means that the kicker succeeds 20% of the time, or 2 out of every 10 shots, on average.
This game is summarized in Table 15.4. The payoffs in the table, or matrix (called a payoff matrix), represent the likelihood that the kicker is successful. Because the goalie wishes to minimize this likelihood, the game is zero sum. We see from the right-hand column in the table that the kicker’s maximin is 0.2, which is realized when the kicker chooses . Always going with the power side, the kicker is assured of successfully scoring at least 20% of the time—hardly a successful outcome.
We see from the bottom row of the table that the goalie’s minimax is 0.9, which is obtained by guessing right (). The maximin and minimax are not equal, which means that the penalty shootout game does not have a saddlepoint. By varying his or her strategies, the kicker’s success rate should be somewhere between 0.2 and 0.9. In a sense, the strategies are to determine how much of the difference is split between the two players. The goalie wishes to push down the success rate as far as possible, whereas the kicker wants to raise it from 0.2 as much as possible.
| Goalie | Row Minima (maximum circled) | |||
|---|---|---|---|---|
| Kicker | 0.2 | 0.9 | 0.2 | |
| 0.95 | 0.15 | 0.15 | ||
| Column Maxima (minimum circled) |
0.95 | 0.9 | ||
Trying to Think Ahead and Outguess One’s Opponent
To see that there is no saddlepoint, let’s consider the four possible outcomes separately and how the players might try to outguess one another. If the kicker chooses (the maximin strategy) and the goalie chooses (the maximin strategy), then the outcome would be 0.9 and the goalie has an incentive to switch to , thereby keeping the kicker at the maximin payoff of 0.2. However, the kicker can anticipate the goalie’s choice of and counteract by choosing , giving the kicker the highest likelihood of success with a rate of 0.95. But the goalie can think this far ahead, too, and return to the original strategy of , which results in the lowest success rate of 0.15 for the kicker. From the proposed () outcome, the kicker now wishes to switch back to the original strategy of !
631
This type of cyclical reasoning, in which the players anticipate one another’s decisions and try to outguess one another, can go on forever, as depicted in the diagram in Figure 15.2.
It fails to provide resolution to the players’ decision problem, precisely because the players fail to vary their behaviors. Once the kicker settles on a particular side to kick the ball, then the goalie can exploit it. Similarly, once the goalie chooses left or right, then the kicker can exploit the decision.
Clearly, there is no best side to kick the ball and no best side to guess under all circumstances. Nevertheless, both the kicker and the goalie can do better, but not by trying to anticipate each other’s choices. The answer to their problem lies in the notion of a mixed strategy.
A Better Idea
The play of many games requires an element of surprise, which can be realized in practice by making use of a mixed strategy, in which a player randomizes what he or she does.
Pure Strategy DEFINITION
Each of the definite courses of action that a player can choose is called a pure strategy.
All the choices for players—Mark and Lisa, the kicker and the goalie—that we have considered so far are pure strategies, in which each player in the end makes a definite choice.
Mixed Strategy DEFINITION
A mixed strategy is a strategy in which the course of action is randomly chosen from one of the pure strategies in the following way: Each pure strategy is assigned some probability, indicating the relative frequency with which that pure strategy will be played. The specific strategy used in any given play of the game can be selected using some appropriate randomization device (like rolling a die, flipping a coin, or using a random number generator on a computer).
632
Note that a pure strategy is a special case of a mixed strategy, with the probability of 1 assigned to just one pure strategy and 0 to all the rest. When a player resorts to a mixed strategy, the resulting outcome of the game is no longer predictable. (For example, if a goalie chooses to guess and with equal probability of 0.5 each, then the kicker cannot predict in which direction the goalie will move. This may be viewed as if in repeated interactions the goalie chooses and half of the time.) The payoff must be described in terms of the probabilistic notion of an expected value or expected payoff, which is the average payoff of the game if it were played many, many times.
Expected Value DEFINITION
If each of the payoffs, , will occur with the probabilities , respectively, then the average, or expected value , is given by
We assume that the probabilities sum to 1 and that each probability is never negative. That is, we assume that and .
Self Check 4
Suppose a player has three strategies and plays them with probabilities , and . If and , then what is ? If the three payoffs , and occur with probabilities , and , then what is the expected value?
The probabilities must add to 1. Because , then . The expected value because .
To see how mixed strategies and expected payoffs are used in the analysis of games, we turn to what is perhaps the simplest of all competitive games without a saddlepoint.
EXAMPLE 4 Matching Pennies
In Matching Pennies, each of two players simultaneously shows either a head or a tail . if the two coins match—either two heads or two tails—then the first player (Player I) receives both coins (a win of 1 for Player I). If the coins do not match, that is, if one is an and the other is a , then the second player (Player II) receives the two coins (a loss of 1 for Player I). These wins and losses for Player I are shown in the zero-sum payoff matrix in Table 15.5.
| Player II | |||
|---|---|---|---|
| Player I | 1 | −1 | |
| −1 | 1 | ||
It is fruitless for one player to attempt to outguess the other in this game. Both should instead resort to mixed strategies and use expected values to estimate their likely gains or losses.
633
To illustrate, assume that Player I randomly selects half the time and half the time. This mixed strategy can be expressed as
Note that the probabilities of choosing and () of choosing do indeed sum to 1, as required; in particular, when .
Player II gains nothing by knowing that Player I is using the optimal mixed strategy . However, Player I must not reveal to Player II whether or will be displayed in any given play of the game before Player II makes his or her own choice of or . Even without this information, if Player II knew that Player I was using a particular nonoptimal mixed strategy , where (i.e., not choosing a 50-50 mixture between and ), then Player II could take advantage of this knowledge and increase his or her average winnings over time to something greater than the value of 0 (see Exercise 18 on page 661).
This mixture can be realized in practice by the flip of a coin. Whenever Player II plays (first column of Table 15.5), Player I’s resulting expected value is
Similarly, whenever Player II plays (second column), Player I’s resulting expected value is
We will develop the tools later in this section to see that neither player can guarantee a better payoff than to choose and with equal likelihood (i.e., p = ), making this strategy optimal (see Exercise 18).
Like Mark’s maximin strategy from the location/schedule game, an optimal mixed strategy in a zero-sum game for the row player provides the highest expected payoff that the row player can guarantee, regardless of the column player’s strategy. Similarly, an optimal strategy for the column player is similar to Lisa’s minimax strategy, as it caps the amount that the row player can make in expected value. Just as when there is a saddlepoint, these two values are equal.
Value DEFINITION
The value of a zero-sum game is the expected value when the row player or the column player plays an optimal strategy.
When the value of a zero-sum game can be realized only by mixed strategies, then the value generalizes the notion of a saddlepoint. Because the value of 0 in Matching Pennies is an expected value, it must be understood in a statistical sense. That is, in a given play of the game, Player I will either win 1 or lose 1. However, his or her expectation over many plays of this game is 0. The optimal mixed strategy for Player II is likewise a 50-50 mix of and , which also leads to an expectation of 0, making the game fair.
Fair Game DEFINITION
A zero-sum game is fair if it has a value of 0, and, consequently, it favors neither player when at least one player uses an optimal (mixed) strategy—one that guarantees the resulting expected payoff is the best that this player can obtain against all possible strategy choices (pure or mixed) by an opponent.
634
EXAMPLE 5 Another Matching Game
In this game, Players I and II can again show either heads or tails . When two Hs appear, Player II pays $5 to Player I. When two Ts appear, Player II pays $1 to Player I. When one and one are displayed, then Player II collects $3 from Player I. The payoffs (that Player I receives from Player II) for this game are given in Table 15.6.
| Player II | |||
|---|---|---|---|
| Player I | 5 | −3 | |
| −3 | 1 | ||
A worst-case analysis, like that which solved our initial location/schedule game, is of little help here. Player I may lose $3 whether he plays or , making his maximin . Player II can keep down her losses to $1 by always playing (and thus avoiding the loss of $5 when two Hs appear), so Player Il’s minimax is 1. However, if Player II chooses and Player I knows this, then Player I will also play and collect $1 from Player II. Can Player II do better than lose $1 in each play of the game?
Consider the situation where Player I uses a mixed strategy , which involves playing with probability and playing with probability , where . Against Player Il’s pure strategy , Player I’s expected value is
Against Player Il’s pure strategy , Player I’s expected value is
Algebra Review Appendix
Graphing a Line in Slope-Intercept Form
These two linear equations in the variable are depicted in Figure 15.3. Note that the four points where these two lines intersect the two vertical lines, and , are the four payoffs appearing in the payoff matrix.
635
The point at which the lines given by and intersect can be found by setting , yielding
Algebra Review Appendix
Linear Equations in Two Variables
so . To the left of , , and to the right, ; at , . If Player I chooses , he can ensure an average payoff of
regardless of what Player II does.
In other words, Player I’s optimal mixed strategy is to pick and with probabilities and , respectively, which gives Player I an expected value of and prevents him from having a bigger average loss. As can be seen from Figure 15.3, is the highest expected value that Player I can guarantee against both strategies and of Player II. Although yields Player I a higher expected value for , and yields him a higher expected value for , Player I’s choice of protects him against an expected loss greater than , which neither of his pure strategies does (each may produce a maximum loss of −3). Put another way, the intersection of and at is the minimum of the function given by to the left and to the right (shown by the dashed line in Figure 15.3). If Player II had more than two strategies, this approach to finding a minimum that puts a floor on Player I’s expected loss can be extended.
A similar calculation for Player II results in the same optimal mixed strategy and expected value . But because the payoffs for Player II are losses, means that she gains on the average. It is a coincidence that Player I and Il’s optimal mixed strategies are identical; in the penalty shootout that we will return to in Example 6, this is not the case.
Therefore, this game is unfair, even though the sum of the amounts ($6) that Player I might have to pay Player II when he loses is the same as the sum that Player II might have to pay Player I when she loses. Interestingly, Player II, who will win an average of cents each time the game is played, is favored, even though she may have to pay more to Player I when she loses (a maximum of $5) than Player I will ever have to pay her (a maximum of $3).
Scoring in professional chess tournaments usually assigns a payoff of 1 for winning, 0 for losing, and to each player for a tie, making the sum of the payoffs to the two players always 1. Such games, called constant-sum games, can readily be converted to zero-sum games. Thus, chess could as well be scored −1 for a loss, +1 for a win, and 0 for a tie, making the constant 0 in this case. Although constant- sum and zero-sum games have the same strategic nature, constant-sum games are a more general class because the constant need not be 0.
The solution to Matching Pennies illustrated how the mixed strategy of guarantees each player the value of 0, but we did not give a solution technique for finding optimal mixed strategies. In the second matching game, we illustrated a procedure that can be applied to every payoff matrix in which each player has only two strategies.
We must use more complex methods, which we will not describe here, to find mixed-strategy solutions when one or both players have more than two strategies. However, one should always check first to see whether a game has a saddlepoint before employing any technique for finding optimal mixed strategies.
636
In our next example, which picks up on the penalty shootout between the kicker and the goalie given by the payoff matrix in Table 15.4, there is no saddlepoint, as we already showed. Thus, the solution will necessarily be in mixed strategies. We now proceed to find what mix is optimal.
EXAMPLE 6 The Penalty Shootout Revisited
In Table 15.7, we add probabilities, which we explain next, to Table 15.4. The goalie should use a mixed strategy , where represents the probability that the goalie guesses left (i.e., dives to the left) and represents the probability that the goalie guesses right. Notice that , as required, assuring that the goalie chooses a side! The probabilities and (where ) are indicated below the game matrix and under the corresponding strategies, and , for the goalie. If the goalie plays a mixed strategy against the two pure strategies, and , for the kicker, then the respective expected values for the kicker are
| Goalie | ||||
|---|---|---|---|---|
| Kicker | 0.2 | 0.9 |
|
|
| 0.95 | 0.15 | |||
As in the second matching game, the solution to this game occurs at the intersection of the two lines given by and . Setting the equations of these lines equal to each other so that yields or , giving .
Thus, the goalie should use the optimal mixed strategy by choosing with probability and with probability . This choice limits the success rate of the kicker to 0.55, or 55%, which is the value of the game. The value of the game is statistical in nature in that it means that if the goalie follows the prescribed strategy, then the kicker will, on average, successfully score 55% of the time. Remember that this doesn’t provide information about what will happen on any one particular kick.
Assume that the kicker uses a mixed strategy , as indicated to the right of the game matrix in Table 15.7. This means that the kicker kicks the ball to the goalie’s left with probability and kicks the ball to the goalie’s right with probability . This mixed strategy, when played against the goalie’s pure strategies, and , results in the following expected values:
Algebra Review Appendix
Linear Equations in Two Variables
The probability can be found by solving for in the equation so that . The intersection of these two lines occurs at the point , giving . The kicker’s optimal mixed strategy is therefore , to kick the ball with probability 8/15 to the goalie’s left and with probability 7/15 to the goalie’s right, which gives the kicker the same success rate of 0.55.
637
Self Check 5
Suppose that . Solve for and find the expected value , so .
- Solving for in the equation yields or , which reduces to .
We have seen that the expected payoff or expected success rate of 0.55, which is the value of the game, occurs when either the goalie selects the optimal mixed guessing strategy (1/2, 1/2) or the kicker selects the optimal mixed kicking strategy (8/15, 7/15). That there is a value for every zero-sum game when the two players are allowed to use mixed strategies is called the fundamental theorem of zero-sum games and is known as the minimax theorem.
Minimax Theorem THEOREM
The minimax theorem guarantees that there is a unique game value and an optimal strategy for each player so that either player alone can realize at least this value by playing this strategy, which may be pure or mixed.
The unique value in Example 6 is 0.55.