CHAPTER 15: GAME THEORY
Example 1: In early 1943, the Japanese controlled the northern half of the island of New Guinea, while the allies controlled the southern half. Intelligence reports indicated that the Japanese were assembling a convoy to reinforce their troops on the island. The convoy would take one of two routes: (1) north of New Britain, where rain and bad visibility were predicted, or (2) south, where the weather was expected to be fair. It was estimated that the trip would take 3 days on either route.
Upon receiving these intelligence estimates, the Supreme Allied Commander, General Douglas McArthur, ordered General George C. Kenney, commander of the Allied Air Forces in the Southwest Pacific Area, to inflict maximum possible damage on the Japanese convoy. Kenney had the choice of sending the bulk of his reconnaissance aircraft on either the southern or northern route. His objective was to maximize the expected number of days the convoy could be bombed, so he wanted to have his aircraft find the convoy as quickly as possible. Consequently, Kenney had two choices: (1) use most of his aircraft to search the northern route, or (2) focus his search in the south.
The payoff would then be measured by the expected number of days Kenney would have at his disposal to bomb the convoy. The overall situation facing the two commanders in what came to be known as the Battle of Bismarck Sea can be represented as follows, where the entries indicate the expected number of days of bombing by Kenney following detection of the Japanese convoy.
JapaneseSail north / Sail South
Allies
/ Search North / 2 days / 2 daysSearch South / 1 day / 3 days
What is the best strategy for each commander?
Solution: The rectangular array of numbers is called a payoff matrix. The rows are labeled with the choices available to General Kenney, while the columns represent the alternatives at the disposal of the Japanese commander. By convention, the entries in the matrix are taken to be the payoff to the row player, in this case the Allies. Since the interests of the Allies and the Japanese are directly opposed, the payoffs to the column player, the Japanese, are simply the negatives of these numbers. To analyze the game, let’s imagine General Kenney’s thought process: “If I search south, I may only get to bomb one day whereas if I search north I am guaranteed 2 days of bombing no matter what my opponent does.” The rational thing to do is to look at the worst-case scenario for each option and then pick the better one. Mathematically, this is equivalent to writing down the row minima and then choosing the largest of these—called the maximin.
JapaneseSail north / Sail South / row minima
Allies
/ Search North / 2 days / 2 days / 2Search South / 1 day / 3 days / 1
column maxima / 2 / 3
The Japanese commander might think “If I sale north, my worst-case scenario is enduring 2 days of bombing but if I sail south my worst-case scenario is being bombed for three days. I will sail north.” This is equivalent to writing down the column maxima and picking the smallest—called the minimax. These two numbers coincide at the pair of decisions: sail north for the Japanese and search north for the Allies. Such a combination of strategies, where the maximin strategy for the row player equals the minimax strategy for the column player, is called a saddlepoint of the game. This is because the saddle on a horse is the maximum point in the left-right direction and the minimum in the front-back direction. By choosing these actions the two players guarantee themselves a certain minimal payoff, regardless of what their opponent chooses to do. Notice that either player can announce his choice in advance to the opponent, secure in the knowledge that the opponent cannot make use of this information to get a better payoff. By the way, in the actual Battle of Bismarck Sea, the two commanders did indeed make these optimal decisions. The two days of bombing led to a crushing defeat for the Japanese.
Not every game has a saddlepoint but, if it does, that point gives the value of the game. In our example the value of the game was 2. In a game that can be played repeatedly, the optimal choice for each player is to always take his or her saddlepoint decision. A strategy that says to select the same row or column on every turn is called a pure strategy.
Example 2: Consider the following two-person game between players ROW and COLUMN. ROW has two possible strategies R1 and R2. COLUMN has the strategies C1 and C2.
ColumnRow / 3
-3
3 / 6
a) What is the minimax of this game?
b) What is the maximin of this game?
c) Is the minimax equal to the maximin?
d) Is there an element of this matrix that is both a row minimum and a column maximum?
e) Does this game have a saddlepoint?
f) What strategies should ROW and COLUMN use?
g) What is the value of this game?
h) Is this a fair game?
Your text sometimes refers to the ROW player as player 1 and the COLUMN player as player 2.
Now we will consider two-person games without saddle points.
Example 3: Every weekend, Colonel Blotto’s forces attempt to defend Rome and Carthage, but his troops are strong enough to protect only one city. On the other hand, although the Huns constitute a horde 10,000 strong, they are capable of attacking only one city at a time. Colonel Blotto has estimated that if he defends the city where the Huns attack, he can save six million people. On the other hand, if he defends Carthage, but the Huns attack Rome, he can save five million people. Finally, if he defends Rome, but the Huns attack Carthage, then he can save only one million people. Find the best strategy for each player.
Solution: Since the payoffs (number of people saved) are stated for Colonel Blotto, we’ll make him the row player, giving us the following payoff matrix (with the payoffs in millions).
Attack Carthage / Attack RomeDefend Carthage / 6 / 5
Defend Rome / 1 / 6
What is the maximin? What is the minimax? Is there saddlepoint?
Let’s see if we can figure out what the opponents might be thinking:
Colonel Blotto: “Maybe I should defend Carthage since it looks like I can save more lives.”
The Huns: We bet Blotto is going to defend Carthage, so we will attack Rome.”
Colonel Blotto: I’ll bet the Huns think I’m going to defend Carthage, so they’ll attack Rome. I’ll fool them and defend Rome.”
The Huns: “We bet that sneaky Blotto thinks that we think he’s going to defend Carthage, and so he’s going to defend Rome. We’ll trick him and attack Carthage.”
By this time, Colonel Blotto’s brain is about to give out. He realizes, though, that it is not the best plan to adopt the same strategy week after week. He is going to vary his strategy from week to week. This is what we call a mixed strategy as opposed to the games with saddlepoints where we use a pure strategy. Let’s let x denote the proportion of the time that Blotto defends Carthage, so 1 – x will represent the proportion of the time he defends Rome. Let’s see how many people Blotto can expect to save with a mixed strategy.
E(Huns attack Carthage) = 6x + 1(1 – x)
E(Huns attack Rome) = 5x + 6(1 – x)
If we let y = the expected number of people saved (in millions), we get two linear equations:
y = 5x + 1 and y = - x + 6. Let’s graph these on the interval [0, 1] since x cannot fall outside that interval. Remember, the idea in Game Theory is to maximize your worst-case scenario. The worst-case scenario to Blotto is the minimum payoff. The minimum payoff is given by that part of the graph that lies lowest. It is the line 5x + 1 to the left of the intersection point and the line – x + 6 to the right of the intersection point. What point maximizes the worst-case scenario? The point of intersection, which we can find algebraically. 5x + 1 = - x + 6
So Blotto’s optimal strategy is to defend Carthage 5/6 of the time and defend Rome 1/6 of the time. Let’s now find the best strategy for the Huns. Let’s let x = the proportion of the time the Huns attack Carthage and hence 1 – x will represent the proportion of the time they attack Rome.
E(Blotto defends Carthage) = 6x + 5(1 – x)
E(Blotto defends Rome) = 1x + 6(1 – x)
Letting y represent the expected number (in millions) of people saved, we graph y = x + 5 and
y = - 5x + 6. The worst-case scenario to the Huns is maximizing the people saved. That is given by the portion of the graph of
y = –5x + 6 to the left of the intersection point and the part of the graph of y = x + 5 to the right of the intersection point. Maximizing the worst-case scenario (which is minimizing the people saved) again yields the intersection point.
- 5x + 6 = x + 5
So the Huns should attack Carthage 1/6 of the time and attack Rome 5/6 of the time. Of course each player does not tell the other player what he plans to do on any single play, but each player should mix up the respective options randomly. For instance a roll of the die could determine each player’s move on a particular weekend.
Example 4: If both players use the optimal strategies in the previous example, what is the expected payoff for each play of the game?
Solution: Let’s add the probabilities of each outcome to the payoff matrix
Attack Carthage / Attack RomeDefend Carthage / 6 (1/6)(5/6)=5/36 / 5
(5/6)(5/6)=25/36
Defend Rome / 1
(1/6)(1/6)=1/36 / 6
(5/6)(1/6)=5/36
The expected value is million people. This represents the average amount (in the long run) of people saved (in millions) per battle. We say that Colonel Blotto’s strategy is optimal because he can be assured an expected payoff of at least 5.167 per play no matter what strategy the Hun’s use. On the other hand, we can say the Huns’ strategy is also optimal in the sense that Colonel Blotto will not save more than 5.167 million people per battle in the long run no matter what Blotto does. You may find this mixed strategy strange, but if you consider that randomness is the best way to hide predictability, then it may not seem so strange.
On a test, you do not have to draw the graphs to find the intersection point.
Example 5 : Suppose a baseball pitcher throws only two pitches: a fastball and a curve. Many hitters try to guess what pitch will be thrown so the batter’s two strategies are also Fastball and Curve. The hitter’s batting averages are given in the matrix. Solve the game.
Pitcher throwsFastball / Curve
Batter
guesses / Fastball / .300 / .200
Curve / .150 / .250
Solution: Solve the game means to find each player’s optimal strategies. First check to see if there is a saddlepoint: Minimax = , Maximin = . Since there isn’t, we will seek a mixed strategy. Let p represent the proportion of the time the batter guesses fastball and 1 – p the proportion of the time he guesses curve.
E(pitcher throws fastball) =
E(pitcher throws curveball) =
The graphs intersect when the expected values are equal.
.
So the batter should guess fastball half the time and guess curveball half the time. Let’s find the optimal strategy for the pitcher. Let q represent the proportion of the time the pitcher should throw a fastball and 1 – q the proportion of the time he should throw a curve.
E(batter guesses fastball) =
E(batter guesses curve) =
So the pitcher should throw fastballs of the time and curves of the time. And remember, he should decide randomly which pitch to throw.
Example 6: Find the value of the previous game.
Solution: Let’s add the probabilities of each payoff to out matrix:
Pitcher throwsFastball / Curve
Batter
guesses / Fastball / .300 / .200
Curve / .150 / .250
The value of the game is
This means that if both players follow their optimal strategy, in the long run the batter will get hits 22.5% of the time (or bat .225).
All of the games we have considered so far have been 2 x 2 games (2 rows and 2 columns).
Now let’s consider larger games.
Example 7: There is a dispute between Florida and Mississippi over offshore drilling rights in the Gulf of Mexico. It is an election year and both parties have called simultaneous news conferences to announce their positions on the dispute. The leaders of both parties calculate what they think will happen under certain pairs of strategies and arrive at the following matrix, whose payoffs are the percentage of the vote that will go to the Republicans.
Democrats take Florida’s side / Democrats take Mississippi’s side / Democrats remain neutralRepublicans take Florida’s side / 45% / 50% / 40%
Republicans take Mississippi’s side / 60% / 55% / 50%
Republican’s remain neutral / 45% / 55% / 40%
What is each party’s best strategy?
Solution: As in the 2 x 2 case, we always look for a saddlepoint first. The row minima are , , and so the maximin = . The column maxima are , , and so the minimax = . So there is a saddlepoint. Here, the Republicans should take Mississippi’s side and the Democrats should remain neutral.
Example 8: What is the best strategy for each player in the following game?
C1 / C2 / C3R1 / 3 / 4 / 0
R2 / 5 / 6 / 2
R3 / 4 / 1 / 3
Solution: Let’s see if there is a saddle point.
C1 / C2 / C3 / Row minimaR1 / 3 / 4 / 0
R2 / 5 / 6 / 2
R3 / 4 / 1 / 3
Column maxima
Since there is no saddlepoint, there is no pure strategy. Notice that the row player should never play strategy R1 since R2 always produces a higher payoff. If every entry in row A is greater than or equal to every entry in row B, we say row A represents the dominant strategy. Row B represents what is called the dominated strategy, or what some texts call the recessive strategy. Since strategy R1 will never be used, we delete that row.