7.08e Mixed strategies: optimal strategy using equations or graphical method

5 A card game between two players consists of several rounds. In each round the players both choose a card from those in their hand; they then show these cards to each other and exchange tokens. The number of tokens that the second player gives to the first player depends on the colour of the first player's card and the design on the second player's card. The table shows the number of tokens that the first player receives for each combination of colour and design. A negative entry means that the first player gives tokens to the second, zero means that no tokens are exchanged. Let the stages be \(0,1,2,3,4,5\). Stage 0 represents arriving at the sanctuary entrance. Stage 1 represents visiting the first bird, stage 2 the second bird, and so on, with stage 5 representing leaving the sanctuary. Let the states be \(0,1,2,3,4\) representing the entrance/exit, kite, lark, moorhen and nightjar respectively.

1. Calculate how many minutes it takes to travel the route $$( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 4 ) - ( 5 ; 0 ) .$$ The friends then realise that if they try to find the quickest route using dynamic programming with this (stage; state) formulation, they will get the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\), or this in reverse, taking 27 minutes.
2. Explain why the route \(( 0 ; 0 ) - ( 1 ; 1 ) - ( 2 ; 2 ) - ( 3 ; 3 ) - ( 4 ; 1 ) - ( 5 ; 0 )\) is not a solution to the friends' problem. Instead, the friends set up a dynamic programming tabulation with stages and states as described above, except that now the states also show, in brackets, any birds that have already been visited. So, for example, state \(1 ( 234 )\) means that they are currently visiting the kite and have already visited the other three birds in some order. The partially completed dynamic programming tabulation is shown opposite.
3. For the last completed row, i.e. stage 2, state 1(3), action 4(13), explain where the value 18 and the value 6 in the working column come from.
4. Complete the table in the insert and hence find the order in which the birds should be visited to give a quickest route and find the corresponding minimum journey time.

   Stage	State	Action	Working	Suboptimal minimum
   \multirow{4}{*}{4}	1(234)	0	10	10
   	2(134)	0	14	14
   	3(124)	0	12	12
   	4(123)	0	17	17
   \multirow{12}{*}{3}	1(23)	4(123)	\(17 + 6 = 23\)	23
   	1(24)	3(124)	\(12 + 2 = 14\)	14
   	1(34)	2(134)	\(14 + 3 = 17\)	17
   	2(13)	4(123)	\(17 + 4 = 21\)	21
   	2(14)	3(124)	\(12 + 2 = 14\)	14
   	2(34)	1(234)	\(10 + 3 = 13\)	13
   	3(12)	4(123)	\(17 + 3 = 20\)	20
   	3(14)	2(134)	\(14 + 2 = 16\)	16
   	3(24)	1(234)	\(10 + 2 = 12\)	12
   	4(12)	3(124)	\(12 + 3 = 15\)	15
   	4(13)	2(134)	\(14 + 4 = 18\)	18
   	4(23)	1(234)	\(10 + 6 = 16\)	16
   \multirow{12}{*}{2}	1(2)	3(12) 4(12)	\(20 + 2 = 22\)	21
   	1(3)	2(13) 4(13)	\(21 + 3 = 24 18 + 6 = 24\)	24
   	1(4)
   	2(1)
   	2(3)
   	2(4)
   	3(1)
   	3(2)
   	3(4)
   	4(1)
   	4(2)
   	4(3)
   \multirow{4}{*}{1}	1
   	2
   	3
   	4
   0	0	1 2 3 4

6 Rowena and Colin play a game in which each chooses a letter. The table shows how many points Rowena wins for each combination of letters. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rowena and Colin are trying to win as many points as possible. Colin's letter \begin{table}[h] \end{table}

1. Write down Colin's play-safe strategy, showing your working. What is the maximum number of points that Colin can win if he plays safe?
2. Explain why Rowena would never choose the letter \(W\). Rowena uses random numbers to choose between her three remaining options, so that she chooses \(X , Y\) and \(Z\) with probabilities \(x , y\) and \(z\), respectively. Rowena then models the problem of which letter she should choose as the following LP. $$\begin{array} { c l } \text { Maximise } & M = m - 1 \\ \text { subject to } & m \leqslant 2 x + 6 y + z , \\ & m \leqslant 4 x + 2 y , \\ & m \leqslant 3 y + 2 z , \\ & m \leqslant 2 x + 2 z , \\ & x + y + z \leqslant 1 \\ \text { and } & m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 \end{array}$$
3. Show how the expression \(2 x + 6 y + z\) was formed. The Simplex algorithm is used to solve the LP problem. The solution has \(x = 0.3 , y = 0.2\) and \(z = 0.5\).
4. Show that the optimal value of \(M\) is 0.6 . Colin then models the problem of which letter he should choose in a similar way. When Rowena plays using her optimal solution, from above, Colin finds that he should never choose the letter \(N\). Letting \(p , q\) and \(t\) denote the probabilities that he chooses \(P , Q\) and \(T\), respectively, Colin obtains the following equations. $$- 3 p + q - t = - 0.6 \quad - p - 2 q + t = - 0.6 \quad p - q - t = - 0.6 \quad p + q + t = 1$$
5. Explain how the equation \(- 3 p + q - t = - 0.6\) is obtained.
6. Use the third and fourth equations to find the value of \(p\). Hence find the values of \(q\) and \(t\).

5 Rose and Colin are playing a game in which they each have four cards. Each player chooses a card from those in their hand, and simultaneously they show each other the cards they have chosen. The table below shows how many points Rose wins for each combination of cards. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rose and Colin are trying to win as many points as possible.

1. What is the greatest number of points that Colin can win when Rose chooses and which card does Colin need to choose to achieve this?
2. Explain why Rose should never choose and find the card that Colin should never choose. Hence reduce the game to a \(3 \times 3\) pay-off matrix.
3. Find the play-safe strategy for each player on the reduced game and show whether or not the game is stable. Rose makes a random choice between her cards, choosing with probability \(x\) with probability \(y\), and with probability \(z\). She formulates the following LP problem to be solved using the Simplex algorithm:
   maximise \(\quad M = m - 6\),
   subject to \(\quad m \leqslant 4 x + 10 y\), \(n \leqslant 9 x + 3 y + 11 z\), \(n \leqslant 2 x + 10 y + z\), \(x + y + z \leqslant 1\),
   and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0 , m \geqslant 0\).
   (You are not required to solve this problem.)
4. Explain how \(9 x + 3 y + 11 z\) was obtained. The Simplex algorithm is used to solve the LP problem. The solution has \(x = \frac { 7 } { 48 } , y = \frac { 27 } { 48 } , z = \frac { 14 } { 48 }\).
5. Calculate the optimal value of \(M\).

2 The table gives the pay-off matrix for a zero-sum game between two players, A my and Bea. The values in the table show the pay-offs for A my. A my makes a random choice between strategies \(\mathbf { P }\) and \(Q\), choosing strategy \(P\) with probability \(p\) and strategy Q with probability \(1 - \mathrm { p }\).

1. Write down and simplify an expression for the expected pay-off for Amy when Bea chooses strategy X . Write down similar expressions for the cases when B ea chooses strategy Y and when she chooses strategy \(Z\).
2. Using graph paper, draw a graph to show A my's expected pay-off against p for each of Bea's choices of strategy. Using your graph, find the optimal value of pfor A my. A my and Bea play the game many times. A my chooses randomly between her strategies using the optimal value for p.
3. Showing your working, calculate A my's minimum expected pay-off per game. W hy might A my gain more points than this, on average?
4. W hat is B ea's minimum expected loss per game? How should B ea play to minimise her expected loss?

3 Basil runs a luxury hotel. He advertises summer breaks at the hotel in several different magazines. Last summer he won the opportunity to place a full-page colour advertisement in one of four magazines for the price of the usual smaller advertisement. The table shows the expected additional weekly income, in \(\pounds\), for each of the magazines for each possible type of weather. Basil wanted to maximise the additional income.

1. Explain carefully why no magazine choice can be rejected using a dominance argument.
2. Treating the choice of strategies as being a zero-sum game, find Basil's play-safe strategy and show that the game is unstable.
3. Calculate the expected additional weekly income for each magazine choice if the weather is rainy with probability 0.4 and sunny with probability 0.6 . Suppose that the weather is rainy with probability \(p\) and sunny with probability \(1 - p\).
4. Which magazine should Basil choose if the weather is certain to be sunny ( \(p = 0\) ), and which should he choose if the weather is certain to be rainy ( \(p = 1\) )?
5. Graph the expected additional weekly income against \(p\). Hence advise Basil on which magazine he should choose for the different possible ranges of values of \(p\).

4 A group of rowers have challenged some cyclists to see which team is fitter. There will be several rounds to the challenge. In each round, the rowers and the cyclists each choose a team member and these two compete in a series of gym exercises. The time by which the winner finishes ahead of the loser is converted into points. These points are added to the score for the winner's team and taken off the score for the loser's team. The table shows the expected number of points added to the score for the rowers for each combination of competitors. Rowers \begin{table}[h] \end{table}

1. Regarding this as a zero-sum game, find the play-safe strategy for the rowers and the play-safe strategy for the cyclists. Show that the game is stable. Unfortunately, Wendy and Kath are needed by their coaches and cannot compete.
2. Show that the resulting reduced game is unstable.
3. Suppose that the cyclists are equally likely to choose Chris or Jamie. Calculate the expected number of points added to the score for the rowers when they choose Andy and when they choose Zac. Suppose that the cyclists use random numbers to choose between Chris and Jamie, so that Chris is chosen with probability \(p\) and Jamie with probability \(1 - p\).
4. Showing all your working, calculate the optimum value of \(p\) for the cyclists.
5. The rowers use random numbers in a similar way to choose between Andy and Zac, so that Andy is chosen with probability \(q\) and Zac with probability \(1 - q\). Calculate the optimum value of \(q\).

4 Ross and Collwen are playing a game in which each secretly chooses a magic spell. They then reveal their choices, and work out their scores using the tables below. Ross and Collwen are both trying to get as large a score as possible.

1. Explain how this can be rewritten as the following zero-sum game.

   		Collwen's choice
   		Fire	Ice	Gale
   \cline { 2 - 5 }	Fire	- 3	3	- 2
   \cline { 2 - 5 } Ross's choice	Ice	2	- 2	0
   \cline { 2 - 5 }	Gale	1	- 3	- 1
   \cline { 2 - 5 }

2. If Ross chooses Ice what is Collwen's best choice?
3. Find the play-safe strategy for Ross and the play-safe strategy for Collwen, showing your working. Explain how you know that the game is unstable.
4. Show that none of Collwen's strategies dominates any other.
5. Explain why Ross would never choose Gale, hence reduce the game to a \(2 \times 3\) zero-sum game, showing the pay-offs for Ross. Suppose that Ross uses random numbers to choose between Fire and Ice, choosing Fire with probability \(p\) and Ice with probability \(1 - p\).
6. Use a graphical method to find the optimal value of \(p\) for Ross.

4 Rowan and Colin are playing a game of 'scissors-paper-rock'. In each round of this game, each player chooses one of scissors ( \(\$$ ), paper ( \)\square\( ) or rock ( \)\bullet$ ). The players reveal their choices simultaneously, using coded hand signals. Rowan and Colin will play a large number of rounds. At the end of the game the player with the greater total score is the winner. The rules of the game are that scissors wins over paper, paper wins over rock and rock wins over scissors. In this version of the game, if a player chooses scissors they will score \(+ 1,0\) or - 1 points, according to whether they win, draw or lose, but if they choose paper or rock they will score \(+ 2,0\) or - 2 points. This gives the following pay-off tables. \includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_476_773_667_239} \includegraphics[max width=\textwidth, alt={}, center]{490ff276-6639-40a1-bffb-dc6967f3ab21-5_478_780_667_1071}

1. Use an example to show that this is not a zero-sum game.
2. Write down the minimum number of points that Rowan can win using each strategy. Hence find the strategy that maximises the minimum number of points that Rowan can win. Rowan decides to use random numbers to choose between the three strategies, choosing scissors with probability \(p\), paper with probability \(q\) and rock with probability \(( 1 - p - q )\).
3. Find and simplify, in terms of \(p\) and \(q\), expressions for the expected number of points won by Rowan for each of Colin's possible choices. Rowan wants his expected winnings to be the same for all three of Colin's possible choices.
4. Calculate the probability with which Rowan should play each strategy.

6 Rose is playing a game against a computer. Rose aims a laser beam along a row, \(A , B\) or \(C\), and, at the same time, the computer aims a laser beam down a column, \(X , Y\) or \(Z\). The number of points won by Rose is determined by where the two laser beams cross. These values are given in the table. The computer loses whatever Rose wins.

1. Find Rose's play-safe strategy and show that the computer's play-safe strategy is \(Y\). How do you know that the game does not have a stable solution?
2. Explain why Rose should never choose row \(C\) and hence reduce the game to a \(2 \times 3\) pay-off matrix.
3. Rose intends to play the game a large number of times. She decides to use a standard six-sided die to choose between row \(A\) and row \(B\), so that row \(A\) is chosen with probability \(a\) and row \(B\) is chosen with probability \(1 - a\). Show that the expected pay-off for Rose when the computer chooses column \(X\) is \(4 - 3 a\), and find the corresponding expressions for when the computer chooses column \(Y\) and when it chooses column \(Z\). Sketch a graph showing the expected pay-offs against \(a\), and hence decide on Rose's optimal choice for \(a\). Describe how Rose could use the die to decide whether to play \(A\) or \(B\). The computer is to choose \(X , Y\) and \(Z\) with probabilities \(x , y\) and \(z\) respectively, where \(x + y + z = 1\). Graham is an AS student studying the D1 module. He wants to find the optimal choices for \(x , y\) and \(z\) and starts off by producing a pay-off matrix for the computer.
4. Graham produces the following pay-off matrix.

   3	1	0
   0	1	2

   Write down the pay-off matrix for the computer and explain what Graham did to its entries to get the values in his pay-off matrix.
5. Graham then sets up the linear programming problem: $$\begin{array} { l l } \text { maximise } & P = p - 4 , \\ \text { subject to } & p - 3 x - y \leqslant 0 , \\ & p - y - 2 z \leqslant 0 , \\ & x + y + z \leqslant 1 , \\ \text { and } & p \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0 . \end{array}$$ The Simplex algorithm is applied to the problem and gives \(x = 0.4\) and \(y = 0\). Find the values of \(z , p\) and \(P\) and interpret the solution in the context of the game. {}

1. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

Find the optimal strategy for each player and the value of the game.

5. The payoff matrix for player \(X\) in a two-person zero-sum game is shown below.

1. Using a graphical method, find the optimal strategy for player \(X\).
2. Find the optimal strategy for player \(Y\).
3. Find the value of the game.

3. A two-person zero-sum game is represented by the payoff matrix for player \(A\) shown below.

1. Represent the expected payoffs to \(A\) against \(B\) 's strategies graphically and hence determine which strategy is not worth considering for player \(B\).
2. Find the best strategy for player \(A\) and the value of the game.

6. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

1. Applying the dominance rule, explain, with justification, which strategy can be ignored by
   1. player \(A\),
   2. player \(B\).
2. For the reduced table, find the optimal strategy for
   1. player \(A\),
   2. player \(B\).
3. Find the value of the game.

4. The payoff matrix for player \(A\) in a two-person zero-sum game is shown below.

1. Explain why the game does not have a saddle point.
2. Using a graphical method, find the optimal strategy for player \(B\).
3. Find the optimal strategy for player \(A\).
4. Find the value of the game.

6 Drew and Emma play a game in which they each choose a strategy and then use the tables below to determine the pay-off that each receives.

1. Convert the game into a zero-sum game, giving the pay-off matrix for Drew.
2. Determine the optimal mixed strategy for Drew.
3. Determine the optimal mixed strategy for Emma.

6 Ryan and Casey are playing a card game in which they each have four cards.

• Ryan's cards have the letters A, B, C and D.
• Casey's cards have the letters W, X, Y and Z.

Each player chooses one of their four cards and they simultaneously reveal their choices. The table shows the number of points won by Ryan for each combination of strategies. \begin{table}[h] \end{table} For example, if Ryan chooses A and Casey chooses W then Ryan wins 4 points (and Casey loses 4 points). Both Ryan and Casey are trying to win as many points as possible.

1. Use dominance to reduce the \(4 \times 4\) table for the zero-sum game above to a \(4 \times 2\) table.
2. Determine an optimal mixed strategy for Casey.

3 A zero-sum game is being played between two players, \(X\) and \(Y\). The pay-off matrix for \(X\) is given below. \section*{Player X}

1. Find an optimal mixed strategy for player \(X\).
2. Give one assumption that must be made about the behaviour of \(Y\) in order to make the mixed strategy of Player \(X\) valid.

6 The pay-off matrix for a game between two players, Sumi and Vlad, is shown below. If Sumi plays A and Vlad plays X then Sumi gets X points and Vlad gets 1 point. Sumi You are given that cell ( \(\mathrm { A } , \mathrm { X }\) ) is a Nash Equilibrium solution.

1. Find the range of possible values of X .
2. Explain what the statement 'cell (A, X) is a Nash Equilibrium solution' means for each player.
3. Find a cell where each player gets their maximin pay-off. Suppose, instead, that the game can be converted to a zero-sum game.
4. Determine the optimal strategy for Sumi for the zero-sum game.

5 In each turn of a game between two players they simultaneously each choose a strategy and then calculate the points won using the table below. They are each trying to maximise the number of points that they win. In each cell the first value is the number of points won by player 1 and the second value is the number of points won by player 2 .

1. Find the play-safe strategy for each player.
2. Explain why player 2 would never choose strategy Z .
3. Find the Nash equilibrium solution(s) or show that there is no Nash equilibrium solution. Player 2 chooses strategy X with probability \(p\) and strategy Y with probability \(1 - p\). You are given that when player 1 chooses strategy A, the expected number of points won by each player is the same.
4. 1. Calculate the value of \(p\).
   2. Determine which player expects to win the greater number of points when player 1 chooses strategy B.

7 Player 1 and player 2 are playing a two-person zero-sum game.
In each round of the game the players each choose a strategy and simultaneously reveal their choice. The number of points won in each round by player 1 for each combination of strategies is shown in the table below. Each player is trying to maximise the number of points that they win.
Player 2 Player 1

1. 1. Determine play-safe strategies for each player.
   2. Show that the game is not stable.
2. Show that the number of strategies available to player 1 cannot be reduced by dominance. You must make it clear which values are being compared. Player 1 intends to make a random choice between strategies \(\mathrm { X } , \mathrm { Y } , \mathrm { Z }\), choosing strategy X with probability \(x\), strategy Y with probability \(y\) and strategy Z with probability \(z\).
   Player 1 formulates the following LP problem so they can find the optimal values of \(x , y\) and \(z\) using the simplex algorithm. Maximise \(M = m - 4\) subject to \(m \leqslant 6 x + 4 y + 2 z\) $$\begin{aligned} & m \leqslant x + 5 y + 6 z \\ & m \leqslant 7 y + 8 z \\ & x + y + z \leqslant 1 \end{aligned}$$ and \(m \geqslant 0 , x \geqslant 0 , y \geqslant 0 , z \geqslant 0\)
3. Explain how the inequality \(m \leqslant 6 x + 4 y + 2 z\) was formed. The problem is solved by running the simplex algorithm on a computer.
   The printout gives a solution in which \(\mathrm { x } + \mathrm { y } = 1\).
   This means that the LP problem can be reduced to the following formulation.
   Maximise \(M = m - 4\) subject to \(m \leqslant 4 + 2 x\) \(\mathrm { m } \leqslant 5 - 4 \mathrm { x }\) \(m \leqslant 7 - 7 x\) and \(m \geqslant 0 , x \geqslant 0\)
4. Solve this problem to find the optimal values of \(x , y\) and \(z\) and the corresponding value of the game to player 1.

2 Annie and Brett play a two-person, simultaneous play game. The table shows the pay-offs for Annie and Brett in the form ( \(a , b\) ). So, for example, if Annie plays strategy K and Brett plays strategy S, Annie wins 2 points and Brett wins 6 points.

1. 1. Determine the play-safe strategy for Annie.
   2. Show that the play-safe strategy for Brett is T.
2. 1. If Annie knows that Brett is planning on playing strategy T, which strategy should Annie play to maximise her points?
   2. If Brett knows that Annie is planning on playing the strategy identified in part (b)(i), which strategy should Brett play to maximise his points?
3. Show that, for Brett, strategy R is weakly dominated.
4. Using a graphical method, determine the optimal mixed strategy for Brett.
5. Show that the game has no Nash equilibrium points.

8 John and Danielle play a zero-sum game which does not have a stable solution. The game is represented by the following pay-off matrix for John. Find the optimal mixed strategy for John.

2.

1. Explain what the term 'zero-sum game' means. Two teams, A and B , are to face each other as part of a quiz.
   There will be several rounds to the quiz with 10 points available in each round.
   For each round, the two teams will each choose a team member and these two people will compete against each other until all 10 points have been awarded. The number of points that Team A can expect to gain in each round is shown in the table below.

   \cline { 3 - 5 } \multicolumn{2}{c|}{}	Team B
   \cline { 3 - 5 } \multicolumn{2}{c|}{}	Paul	Qaasim	Rashid
   \multirow{3}{*}{Team A}	Mischa	5	6	3
   \cline { 2 - 5 }	Noel	4	1	7
   \cline { 2 - 5 }	Olive	4	5	8

   The teams are each trying to maximise their number of points.
2. State the number of points that Team B will expect to gain each round if Team A chooses Noel and Team B chooses Rashid.
3. Explain why subtracting 5 from each value in the table will model this situation as a zero-sum game.
4. 1. Find the play-safe strategies for the zero-sum game.
   2. Explain how you know that the game is not stable. At the last minute, Olive becomes unavailable for selection by Team A.
      Team A decides to choose its player for each round so that the probability of choosing Mischa is \(p\) and the probability of choosing Noel is \(1 - p\).
5. Use a graphical method to find the optimal value of \(p\) for Team A and hence find the best strategy for Team A. For this value of \(p\),
6. 1. find the expected number of points awarded, per round, to Team A,
   2. find the expected number of points awarded, per round, to Team B.
      

4. The table below gives the pay-off matrix for a zero-sum game between two players, Aljaz and Brendan. The values in the table show the pay-offs for Aljaz. You may not need to use all of these tables
You may not need to use all the rows and columns \includegraphics[max width=\textwidth, alt={}, center]{bbdfa492-6578-484a-a0b5-fcdb78020b83-06_437_832_1201_139}

3. Two teams, A and B , each have three team members. One member of Team A will compete against one member of Team B for 10 rounds of a competition. None of the rounds can end in a draw. Table 1 shows, for each pairing, the expected number of rounds that the member of Team A will win minus the expected number of rounds that the member of Team B will win. These numbers are the scores awarded to Team A. This competition between Teams A and B is a zero-sum game. Each team must choose one member to play. Each team wants to choose the member who will maximise its score. \begin{table}[h] \end{table}

1. 1. Find the number of rounds that Team A expects to win if Team A chooses Mischa and Team B chooses Paul.
   2. Find the number of rounds that Team B expects to win if Team A chooses Noel and Team B chooses Qaasim. Table 1 models this zero-sum game.
2. 1. Find the play-safe strategies for the game.
   2. Explain how you know that the game is not stable.
3. Determine which team member Team B should choose if Team B thinks that Team A will play safe. Give a reason for your answer. At the last minute, Rashid is ill and is therefore unavailable for selection by Team B.
4. Find the best strategy for Team B, defining any variables you use.