Home Mathematics



Examples of ZeroSum GamesIn this section, we present several illustrative examples of the theory of total conflict games. We present the scenario, discuss the outcomes used in the payoff matrix, and present a possible solution for the game. In most game theory problems, the solution suggests insights in how to play the game rather than a definite methodology to “winning” the game. Example 7.4. The Battle of the Bismarck Sea. The Battle of the Bismarck Sea is set in the South Pacific in 1943. See Figure 7.2. The historical facts are that General Imamura had been ordered to transport Japanese troops to New Guinea. General Kenney, the United States commander in the region, wanted to bomb the troop transports prior to their arrival at their destination. Imamura had two options to choose from as routes to New Guinea: a shorter northern route or a longer southern route. Kenney had to decide where to send his search planes and bombers to find the Japanese fleet. If Kenney sent his planes to the wrong route, he could recall them, but the number of bombing days would be reduced. FIGURE 7.2: The Battle of the Bismarck Sea. Japanese troops were being taken from Rabaul to Lae. (Map Source: The World Fact Book, CIA) We assume that both commanders, Imamura and Kenney, are rational players, each trying to obtain his best outcome. Further, we assume that there are no communications or cooperation which may be inferred since the two are enemies engaging in war. Further, each is aware of the intelligence assets that are available to each side and are aware of what the intelligence assets are producing. We assume that the estimates of number of days that US planes can bomb as well as the number of days to sail to New Guinea are accurate. The players, Kenney and Imamura, both have the same set of strategies for routes: {North, South}, and their payoffs, given as the numbers of exposed days for bombing, are shown in Table 7.7. Imamura loses exactly what Kenney gains. TABLE 7.7: The Battle of the Bismarck Sea with Payoffs (Kenney, Imamura)
Graphing the payoffs, Figure 7.3, shows this is a total conflict game. FIGURE 7.3: Graph of Payoffs for the Battle of the Bismarck Sea As a total conflict game, Table 7.8 only needs to list the outcomes to Kenney in order to find a solution. TABLE 7.8: The Battle of the Bismarck Sea as a Zero Sum Game
There is a dominant column strategy for Imamura: to sail North since the values in the column are correspondingly less than or equal to the values for sailing South. The dominant North column would eliminate the South column. Seeing that as an option, Kenney would search North—that option provides a greater outcome than searching South, (2 > 1). He could also apply the minimax theorem (saddle point method) to find a plausible Nash equilibrium as Kenney searches North and Imamura takes the Northern route. See Table 7.9. TABLE 7.9: Minimax Method (Saddle Point Method)
Applied to the Battle of the Bismarck Sea, the Nash equilibrium (North, North) implies that no player can do unilaterally better by changing their strategy. The solution is for the Japanese to sail North and for Kenney to search North yielding 2 bombing days. This result, (North, North), was indeed the real outcome in 1943. Next, let’s assume that communication is allowed. We will consider first moves by each player. If Kenney moved first, (North, North) would remain the outcome. However, (North, South) also becomes a valid response with the same value of 2. If Imamura moved first, (North, North) would be the outcome. What is important about moving first in a zero sum game is that, although it gives more information, neither player can do better than the Nash equilibrium from the original zero sum game. We conclude from our brief analysis that moving first does not alter the equilibrium of this game. Moving first in a zero sum games does not alter the equilibrium strategies. A Maple solution follows. Remember to begin by entering with(Optimization). First, the solution for Kenney:
We used fnormal to eliminate artifacts from floating point computations. Now, the solution for the Japanese commander, Imamura.
Example 7.5. Penalty Kicks in Soccer^{3}. A penalty kick in soccer is a game between a kicker and the opposing goalie. The kicker has two alternative strategies: he might kick left or kick right. The goalie will also have two strategies: the goalie can dive left or right to block the kick. We will start with a very simple payoff matrix with a 1 for the player that is successful and a —1 for the player that is unsuccessful, assuming a correct dive blocks the kick. The payoff matrix is in Table 7.10. TABLE 7.10: Penalty Kick Payoffs
^{3}This example is adapted from Chiappori, Levitt, and Groseclose [CLG2002]. Or. just the kicker’s prospective, see Table 7.11. TABLE 7.11: Kicker’s Penalty Kick Payoffs
There is no pure strategy. We find a mixed strategy' solution to the zero sum game using either linear programming or the method of oddments^{4}. The mixed strategy results are that the kicker randomly kicks 50% left and 50% right, while the goalie randomly dives 50% left and 50% right. The value of the game to each player is 0. Let’s refine the game using real data. A study was done in the Italian Football League in 2002 by Ignacio PalaciosHucrta.^{1} As he observed, the kicker can aim the ball to the left or to the right of the goalie, and the goalie can dive either left or right as well. The ball is kicked with enough speed that the decisions of the kicker and goalie are effectively made simultaneously. Based on these decisions, the kicker is likely to score or not score. The structure of the game is remarkably similar to our simplified game. If the goalie dives in the direction that the ball is kicked, then he has a good chance of stopping the goal; if he dives in the wrong direction, then the kicker is likely' to score a goal. After analyzing approximately 1400 penalty kicks, PalaciosHuerta determined the empirical probabilities of scoring for each of four outcomes: the kicker kicks left or right, and the goalie dives left or right. His results led to the payoff matrix in Table 7.12. TABLE 7.12: Penalty Kick Probabilities of Scoring
Applying our solution method to the linear programming formulation finds the optimal solution as either pure strategy or mixed strategy.
A shortcut method, the Method of Oddments, is shown in Table 7.13. TABLE 7.13: Method of Oddments
We find the mixed strategy for the kicker is 38.3% kicking left and 61.7% kicking right, while the goalie dives right 58.3% and dives left 41.7%. If we merely count percentages from the data that was collected by PalaciosHuerta in his study of 459 penalty kicks over 5 years of data, we find the kicker did 40% kicking left, and 60% kicking right, while the goalie dove left 42% and right 58%. Since our model closely approximates the data, our game theory approach adequately models the penalty kick. The next example, a batterpitcher duel, continues the theme of technology in sports today. Example 7.6. BatterPitcher Duel. We extend to four strategies for each player. Consider a batterpitcher duel between Aaron .Judge of the New York Yankees, and various pitchers in the American League where the pitcher throws a fastball, a splitfinger fastball, a curve ball, and a changeup. The batter, aware of these pitches, must prepare appropriately for the pitch. We’ll consider right and lefthanded pitchers separately in this analysis. Data is available from many websites, such as www. STATS. com. The data in Table 7.14 has been compiled for an American League right handed pitcher (RHP) versus Aaron Judge. Let FB = fastball, GB = curve ball, CH = changeup, SF = splitfinger fastball. TABLE 7.14: Aaron Judge vs. a RightHanded Pitcher
Both the batter and pitcher want the best possible result . We set this up as a linear programming problem. Our decision variables are xi, X2, X3, and ж4 as the percentages to guess FB, СВ, CH, SF, respectively, and V represents Judge’s batting average.
We solve this linear programming problem with Maple, and find the optimal solution (strategy) is to guess the fastball (FB) 27.49%, guess the curve ball (CB) 64.23%, never guess changeup {CH), and guess splitfinger fastball {SF) 8.27% of the time to obtain a 0.291 batting average. The pitcher also wants to keep the batting average as low as possible. Set up the linear program for the pitcher as follows. The decision variables are t/i, У2, Уз, and j/4 as the percentages to guess FB, CB, CH, SF, respectively, and V again represents Judge’s batting average.
We find the righthanded pitcher (RHP) should randomly throw 65.94% fast balls, no curve balls, 3.24% changeups, and 30.82% splitfinger fastballs for Judge to keep, and not increase, his 0.291 batting average. Statistics for Judge versus a lefthanded pitcher (LHP) are in Table 7.15. TABLE 7.15: Aaron Judge vs. a LeftHanded Pitcher
Set up as before, and solve the linear programming problem.
We find the optimal solution for Judge versus a LHP. Judge should guess as follows: never guess fastball, guess curve ball 24.0%, never guess changeup, and guess splitfinger fastball 76.0% for a batting average of .262. For the lefthanded pitchers facing Judge, solve the following LP:
The pitcher should randomly throw 26.2% fastballs, 62.8% curve balls, no changeups, and no splitfinger fast balls. Then Judge’s batting average will remain at .262, and won’t increase. The manager of the opposing team is in the middle of a close game. There are two outs, runners in scoring position, and Judge is coming to bat. Does the manager keep the LHP in the game or switch to a RHP? The percentages say keep the LHP since 0.262 < 0.291. Tell the catcher and pitcher to randomly select the pitches to be thrown to Judge. Judge’s manager wants to improve his batting ability against both a curve ball and a LHP. Only by improving against these strategies can he effect change. Example 7.7. Operation Overlord. Operation Overlord, the codename for World War IPs Battle of Normandy, can be viewed in the context of game theory. In 1944, the Allies were planning an operation for the liberation of Europe; the Germans were planning their defense against it. There were two known possibilities for an initial amphibious landing: the beaches at Normandy, and those at Calais. Any landing would succeed against a weak defense, so the Germans did not want a weak defense at the potential landing site. Calais was more difficult for a landing, but closer to the Allies targets for success. Suppose the probabilities of an Allied success are as in Table 7.16. TABLE 7.16: Probabilities of a Successful Allied Landing
The Allies successfully landing at Calais would earn 100 points, successfully landing at Normandy would earn 80 points, and failure at either landing would earn 0 points. What decisions should be made? We compute the expected values, placing them in the payoff matrix of Table 7.17. TABLE 7.17: Payoff Matrix for Allied Landing
There are no pure strategy solutions in this example. We use mixed strategies, and determine the game’s outcome. The Allies would employ a mixed strategy of 80% Normandy and 20% Calais to achieve an outcome of 68 points. At the same time, the Germans should employ a strategy of 60% Normandy and 40% Calais for their defenses to keep the Allies at 68 points. Implementation of the landing was certainly not twopronged. So what do the mixed strategies imply in strategic thinking? Most likely a strong feint at Calais and lots of information leaks about Calais, while the real landing at Normandy was a secret. The Germans had a choice as to believe the information about Calais, or somewhat equally divide their defenses. Although the true results were in doubt for a while, the Allies prevailed. Example 7.8. Choosing the Right Course of Action. The US Army Command and General Staff College presented this approach for choosing the best course of action (COA) for a mission. For a possible battle between two forces, we compute the optimal courses of actions for the two opponents using game theory.^{[1]} Steps 1 and 2. List the friendly COAs, and rank order them Best to Worst. COA 1: Decisive Victory COA 4: Attrition Based Victory COA 2: Failure by Culmination COA 3: Defeat in Place Step 3. The enemy is thought to have six distinct possible courses of action. Rank best to worst each COA of the enemy where the row represents the friendly CO A. For example, the friendly СОА 1 is best against the enemy СОА 1 and friendly COA 2 is worst against the enemy COA 6. Step 4. Decide in each case if we think we will Win, Lose, Draw using Table 7.18. TABLE 7.18: Enemy COA vs. Friendly COA
Steps 5 and 6. Provide scores. Since there are 4 friendly COAs and 6 enemy COAs, we use scores from 24 (Best) to 1 (Worst). See Table 7.19. TABLE 7.19: Enemy COA vs. Friendly COA Scores
Steps 7 and 8. Put into numerical order for Loss. Step 9. Fill in the scores for the draw. See Table 7.20.
Step 10. Put the courses of action back in their original order. Add minimax data. See Table 7.21. TABLE 7.21: Enemy COA vs. Friendly COA Minimax
There is no pure strategy solution. Because of the size of the payoff matrix, we did not use the movement diagram, but instead used the Minimax theorem. Basically, we find the minimum in each row, and then the maximum of these minimums. Then we find the maximums in each column, then the minimum of those maximums. If the maximum of the row minimum’s equals the minimum of the column maximums, then we have a pure strategy solution. If not, we have to find the mixed strategy solution. In Step 10 above, the maximum of the minimums is 9, while the minimum of the maximums is 10. They are not equal. Linear programming may be used in zerosum games to find the solutions whether they are pure strategy or mixed strategy solutions. So, we solve this game using a linear program. Let V be the value of the game, xi to a; 4 be the probabilities in which to play strategies (COAs) 1 through 4 for the friendly side. The values y to ye represent the probabilities the enemy should employ СОА 1 to COA 6, respectively, to obtain their best results.
The linear program for the enemy is
Maple gives the solution as V = 9.462 when “friendly” chooses xi = 7.7%, X‘2 = 0, x_{3} = 0, x_{4} = 92.3%, while the “enemy” best results come when y_{4} = 0, J/2 = 0, уз = 0, у4 = 46.2% and yr, = 53.9% holding the “friendly” to 9.462. Interpretation: At 92.3%, we see we should defend along the Vistula River (COA 4) almost all the time. The value of the game, V = 9.462, is greater than the pure strategy solution of 9 for always picking to defend the Vistula River (COA 4). This implies that we benefit from secrecy and employing deception. We can benefit by “selling the enemy” on our “attack North and fix in the South” (COA 1). A negative 9.462 for the enemy does not mean the enemy loses. We need to further consider the significance of the values and mission analysis. Exercises Solve the problems using any method. 1. What should each player do according to the payoff matrix in Table 7.22? TABLE 7.22: Attack and Defense
Use Table 7.23 below for Exercises 2. to 10. TABLE 7.23: Payoff Table
7. Show the value of the game is
11. Consider Table 7.24 of a batterpitcher duel. All the entries in the payoff matrix reflect the percent of hits off the pitcher, the batting average. What strategies are optimal for each player? TABLE 7.24: BatterPitcher Duel Payoffs
12. Find the solution in the game shown in Table 7.25. TABLE 7.25: Two by Three Game
13. Find the solution in the game given in Table 7.26. TABLE 7.26: Four by Four Game
14. Table 7.27 represents a game between a professional athlete (Rose) and management (Colin) for contract decisions. The athlete has two strategies and management has three strategies. The values are in 1,000s. What decision should each make? TABLE 7.27: Two by Three Game
15. Solve the game given in Table 7.28. TABLE 7.28: Game Payoff Table
16. The predator has two strategies for catching the prey: ambush or pursuit. The prey has two strategies for escaping: hide or run. The game matrix appears in Table 7.29. Solve the game.
17. A professional football team has collected data for certain plays against certain defenses. The payoff matrix in Table 7.30 shows the yards gained or lost for a particular play against a particular defense. Find the best strategies. TABLE 7.30: Yards Gained or Lost
18. Solve the .TeterRomero batterpitcher duel using the payoff matrix given in Table 7.31.
19. Solve the game with the payoff matrix of Table 7.32. TABLE 7.32: Payoff Tableau
20. Solve the game with the payoff matrix of Table 7.33. TABLE 7.33: Payoff Tableau
21. Solve the game with the payoff matrix of Table 7.34. TABLE 7.34: Payoff Tableau
22. Find the solution for the game using the payoff matrix in Table 7.35. TABLE 7.35: Payoff Tableau
23. In Table 7.36 of a batterpitcher duel, the entries reflect the percent of hits off the pitcher, the batting average. Find the optimal strategies for each player? TABLE 7.36: BatterPitcher Duel Payoffs
24. Solve the game shown in Table 7.37. TABLE 7.37: Payoff Tableau
25. Solve the game shown in Table 7.38. TABLE 7.38: Payoff Tableau
26. Solve the game shown in Table 7.39. TABLE 7.39: Payoff Tableau
TABLE 7.40: Payoff Tableau
b) TABLE 7.41: Payoff Tableau
e) TABLE 7.42: Payoff Tableau
d) TABLE 7.43: Payoff Tableau
e) TABLE 7.44: Payoff Tableau
28. For the game of Table 7.45 between Rose and Colin, write the linear programming formulation for Rose. Using Maple’s simplex or Optimization packages, find and state the complete solution to the game in context of the game. TABLE 7.45: Payoff Tableau
Projects Project 7.1. Research the solution methodologies for the threeperson games. Analyze the threeperson, zerosum game between Rose, Colin, and Larry shown in Tables 7.46 and 7.47. TABLE 7.46: Payoff Tableau for Larry's D
TABLE 7.47: Payoff Tableau for Larry's D_{2}
Colin vs. RoseLarry: (3, — 3,0) and Rose vs. ColinLarry: (—2,0,2) If no side payments were allowed, would any player be worse off joining a coalition than playing alone? Briefly explain (include the values to justify decisions).

<<  CONTENTS  >> 

Related topics 