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

3. In your answer to this question you must show detailed reasoning. A two-person zero-sum game is represented by the following pay-off matrix for player A.

1. Verify that there is no stable solution to this game. Player B plays their option X with probability \(p\).
2. Use a graphical method to find the optimal value of \(p\) and hence find the best strategy for player B.
3. Find the value of the game to player A .
4. Hence find the best strategy for player A .

3. Terry and June play a zero-sum game. The pay-off matrix shows the number of points that Terry scores for each combination of strategies.

1. Explain the meaning of 'zero-sum' game.
2. Verify that there is no stable solution to the game.
3. Write down the pay-off matrix for June.
4. 1. Find the best strategy for June, defining any variables you use.
   2. State the value of the game to Terry. Let Terry play option A with probability \(t\).
5. By writing down a linear equation in \(t\), find the best strategy for Terry.

3. A two-person zero-sum game is represented by the following pay-off matrix for player \(A\).

1. 1. Show that this game is stable.
   2. State the value of this game to player \(B\). Option S is removed from player A's choices and the reduced game, with option S removed, is no longer stable.
2. Write down the reduced pay-off matrix for player \(B\). Let \(B\) play option X with probability \(p\) and option Y with probability \(1 - p\).
3. Use a graphical method to find the optimal value of \(p\) and hence find the best strategy for player \(B\) in the reduced game.
4. 1. Find the value of the reduced game to player \(A\).
   2. State which option player \(A\) should never play in the reduced game.
   3. Hence find the best strategy for player \(A\) in the reduced game.

3. Haruki and Meera play a zero-sum game. The game is represented by the following pay-off matrix for Haruki.

1. Determine whether the game has a stable solution. Option Y for Meera is now removed.
2. Write down the reduced pay-off matrix for Meera.
3. 1. Given that Meera plays Option X with probability \(p\), determine her best strategy.
   2. State the value of the game to Haruki.
   3. State which option(s) Haruki should never play. The number of points scored by Haruki when he plays Option C and Meera plays Option X changes from - 1 to \(k\) Given that the value of the game is now the same for both players,
4. determine the value of \(k\). You must make your method and working clear.

4. A two person zero-sum game is represented by the following pay-off matrix for player A.

1. Verify that there is no stable solution.
2. 1. Find the best strategy for player A.
   2. Find the value of the game to her.

4. A two person zero-sum game is represented by the pay-off matrix for player A shown above.

1. Verify that there is no stable solution to this game. Player A intends to make a random choice between options \(\mathrm { P } , \mathrm { Q }\) and R , choosing option P with probability \(p _ { 1 }\), option Q with probability \(p _ { 2 }\) and option R with probability \(p _ { 3 }\) Player A wants to find the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm. Player A formulates the following linear programming problem for the game, writing the constraints as inequalities. $$\begin{aligned} & \text { Maximise } P = V \\ & \text { subject to } V \geqslant 3 p _ { 1 } - 4 p _ { 2 } + p _ { 3 } \\ & \\ & V \geqslant - 2 p _ { 1 } + 4 p _ { 2 } + 2 p _ { 3 } \\ & V \geqslant - 2 p _ { 2 } - p _ { 3 } \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 \\ & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , V \geqslant 0 \end{aligned}$$
2. Correct the errors made by player A in the linear programming formulation of the game, giving reasons for your answer.
3. Write down an initial Simplex tableau for the corrected linear programming problem. The Simplex algorithm is used to solve the corrected linear programming problem. The optimal values are \(p _ { 1 } = 0.6 , p _ { 2 } = 0\) and \(p _ { 3 } = 0.4\)
4. Calculate the value of the game to player A.
5. Determine the optimal strategy for player B, making your reasoning clear.

7. Alexis and Becky are playing a zero-sum game. Alexis has two options, Q and R . Becky has three options, \(\mathrm { X } , \mathrm { Y }\) and Z .
Alexis intends to make a random choice between options Q and R , choosing option Q with probability \(p _ { 1 }\) and option R with probability \(p _ { 2 }\) Alexis wants to find the optimal values of \(p _ { 1 }\) and \(p _ { 2 }\) and formulates the following linear programme, writing the constraints as inequalities. $$\begin{aligned} & \text { Maximise } P = V \\ & \text { where } V = 3 + \text { the value of the gan } \\ & \text { subject to } V \leqslant 6 p _ { 1 } + p _ { 2 } \\ & \qquad \begin{aligned} & V \leqslant 8 p _ { 2 } \\ & V \leqslant 4 p _ { 1 } + 2 p _ { 2 } \\ & p _ { 1 } + p _ { 2 } \leqslant 1 \\ & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , V \geqslant 0 \end{aligned} \end{aligned}$$

1. Complete the pay-off matrix for Alexis in the answer book.
2. Use a graphical method to find the best strategy for Alexis.
3. Calculate the value of the game to Alexis. Becky intends to make a random choice between options \(\mathrm { X } , \mathrm { Y }\) and Z , choosing option X with probability \(q _ { 1 }\), option Y with probability \(q _ { 2 }\) and option Z with probability \(q _ { 3 }\)
4. Determine the best strategy for Becky, making your method and working clear.

3 Lee and Maria are playing a strategy game. The tables below show the points scored by Lee and the points scored by Maria for each combination of strategies. Points scored by Lee Lee's choice \begin{table}[h] \end{table} Points scored by Maria Lee's choice \includegraphics[max width=\textwidth, alt={}, center]{a51b112d-1f3f-4214-94c1-8b9cd7eb831c-3_335_481_392_1139}

1. Show how this game can be reformulated as a zero-sum game.
2. By first using dominance to eliminate one of Lee's choices, use a graphical method to find the optimal mixed strategy for Lee.

3 The pay-off matrix for a zero-sum game is

1. Show that the game does not have a stable solution.
2. Use a graphical technique to find the optimal mixed strategy for the player on columns.
3. Formulate an initial simplex tableau for the problem of finding the optimal mixed strategy for the player on rows.

6 Sam is playing a computer game in which he is trying to drive a car in different road conditions. He chooses a car and the computer decides the road conditions. The points scored by Sam are shown in the table. Sam is trying to maximise his total points and the computer is trying to stop him.

1. Explain why Sam should never choose \(S _ { 1 }\) and why the computer should not choose \(C _ { 3 }\).
2. Find the play-safe strategies for the reduced 2 by 2 game for Sam and the computer, and hence show that this game does not have a stable solution.
3. Sam uses random numbers to choose \(S _ { 2 }\) with probability \(p\) and \(S _ { 3 }\) with probability \(1 - p\).
   1. Find expressions for the expected gain for Sam when the computer chooses each of its two remaining strategies.
   2. Calculate the value of \(p\) for Sam to maximise his total points.
   3. Hence find the expected points gain for Sam.

      Surname

      Other Names

      Centre Number

      Candidate Number

      Candidate Signature

      \section*{General Certificate of Education January 2006
      Advanced Level Examination} \section*{MATHEMATICS
      Unit Decision 2} MD02 \section*{Insert} Wednesday 18 January 20061.30 pm to 3.00 pm Insert for use in Questions 3 and 4.
      Fill in the boxes at the top of this page.
      Fasten this insert securely to your answer book.

4

1. Two people, Ros and Col, play a zero-sum game. The game is represented by the following pay-off matrix for Ros.

   \multirow{2}{*}{}	\multirow[b]{2}{*}{Strategy}	Col
   		X	Y	Z
   \multirow{3}{*}{Ros}	I	-4	-3	0
   	II	5	-2	2
   	III	1	-1	3

   1. Show that this game has a stable solution.
   2. Find the play-safe strategy for each player and state the value of the game.
2. Ros and Col play a different zero-sum game for which there is no stable solution. The game is represented by the following pay-off matrix for Ros.

   \cline { 2 - 5 } \multicolumn{1}{c|}{}	Col
   \cline { 2 - 5 } \multicolumn{1}{c|}{}	Strategy	\(\mathbf { C } _ { \mathbf { 1 } }\)	\(\mathbf { C } _ { \mathbf { 2 } }\)	\(\mathbf { C } _ { \mathbf { 3 } }\)
   \multirow{2}{*}{Ros}	\(\mathbf { R } _ { \mathbf { 1 } }\)	3	2	1
   \cline { 2 - 5 }	\(\mathbf { R } _ { \mathbf { 2 } }\)	- 2	- 1	2

   1. Find the optimal mixed strategy for Ros.
   2. Calculate the value of the game.

3 Two people, Rob and Con, play a zero-sum game. The game is represented by the following pay-off matrix for Rob.

1. Explain what is meant by the term 'zero-sum game'.
2. Show that this game has no stable solution.
3. Explain why Rob should never play strategy \(R _ { 3 }\).
4. 1. Find the optimal mixed strategy for Rob.
   2. Find the value of the game.

4

1. Two people, Raj and Cal, play a zero-sum game. The game is represented by the following pay-off matrix for Raj.

   	Cal
   \cline { 2 - 5 }	Strategy	X	Y	Z
   Raj	I	- 7	8	- 5
   \cline { 2 - 5 }	II	6	2	- 1
   \cline { 2 - 5 }	III	- 2	4	- 3
   \cline { 2 - 5 }
   \cline { 2 - 5 }

   Show that this game has a stable solution and state the play-safe strategy for each player.
2. Ros and Carly play a different zero-sum game for which there is no stable solution. The game is represented by the following pay-off matrix for Ros, where \(x\) is a constant.

   	Carly
   \cline { 2 - 4 }	Strategy		\(\mathbf { C } _ { \mathbf { 1 } }\)
   \cline { 2 - 4 }\cline { 2 - 3 } \(\operatorname { Ros }\)	\(\mathbf { R } _ { \mathbf { 1 } }\)	5	\(\mathbf { C } _ { \mathbf { 2 } }\)
   \cline { 2 - 4 }	\(\mathbf { R } _ { \mathbf { 2 } }\)	- 2	\(x\)
   \cline { 2 - 4 }			4

   Ros chooses strategy \(\mathrm { R } _ { 1 }\) with probability \(p\).
   1. Find expressions for the expected gains for Ros when Carly chooses each of the strategies \(\mathrm { C } _ { 1 }\) and \(\mathrm { C } _ { 2 }\).
   2. Given that the value of the game is \(\frac { 8 } { 3 }\), find the value of \(p\) and the value of \(x\).

6 Two people, Rowan and Colleen, play a zero-sum game. The game is represented by the following pay-off matrix for Rowan. Colleen

1. Explain the meaning of the term 'zero-sum game'.
2. Show that this game has no stable solution.
3. Explain why Rowan should never play strategy \(R _ { 1 }\).
4. 1. Find the optimal mixed strategy for Rowan.
   2. Find the value of the game.

      Surname

      Other Names

      Centre Number

      Candidate Number

      Candidate Signature

      \section*{MATHEMATICS
      Unit Decision 2} \section*{Insert} Thursday 8 June 2006 9.00 am to 10.30 am Insert for use in Questions 1, 3 and 4.
      Fill in the boxes at the top of this page.
      Fasten this insert securely to your answer book.

3 Two people, Rose and Callum, play a zero-sum game. The game is represented by the following pay-off matrix for Rose.

1. 1. State the play-safe strategy for Rose and give a reason for your answer.
   2. Show that there is no stable solution for this game.
2. Explain why Rose should never play strategy \(\mathbf { R } _ { \mathbf { 3 } }\).
3. Rose adopts a mixed strategy, choosing \(\mathbf { R } _ { \mathbf { 1 } }\) with probability \(p\) and \(\mathbf { R } _ { \mathbf { 2 } }\) with probability \(1 - p\).
   1. Find expressions for the expected gain for Rose when Callum chooses each of his three possible strategies. Simplify your expressions.
   2. Illustrate graphically these expected gains for \(0 \leqslant p \leqslant 1\).
   3. Hence determine the optimal mixed strategy for Rose.
   4. Find the value of the game.

3 Two people, Roseanne and Collette, play a zero-sum game. The game is represented by the following pay-off matrix for Roseanne.

1. 1. Find the optimal mixed strategy for Roseanne.
   2. Show that the value of the game is - 0.5 .
2. 1. Collette plays strategy \(\mathrm { C } _ { 1 }\) with probability \(p\) and strategy \(\mathrm { C } _ { 2 }\) with probability \(q\). Write down, in terms of \(p\) and \(q\), the probability that she plays strategy \(\mathrm { C } _ { 3 }\).
   2. Hence, given that the value of the game is - 0.5 , find the optimal mixed strategy for Collette.

2 Two people, Rowena and Colin, play a zero-sum game.
The game is represented by the following pay-off matrix for Rowena.

1. Explain what is meant by the term 'zero-sum game'.
2. Determine the play-safe strategy for Colin, giving a reason for your answer.
3. Explain why Rowena should never play strategy \(R _ { 3 }\).
4. Find the optimal mixed strategy for Rowena.

5 Mark and Owen play a zero-sum game. The game is represented by the following pay-off matrix for Mark.

1. Explain why Mark should never play strategy B.
2. It is given that the value of the game is 0.6 . Find the optimal strategy for Owen.
   (You are not required to find the optimal mixed strategy for Mark.)
   [0pt] [7 marks]

3. A two-person zero-sum game is represented by the following pay-off matrix for player A.

1. Identify the play safe strategies for each player.
2. State, giving a reason, whether there is a stable solution to this game.
3. Find the best strategy for player A.
4. Find the value of the game to player B.

3 Rose and Colin repeatedly play a zero-sum game. The pay-off matrix shows the number of points won by Rose for each combination of strategies.

1. What is the greatest number of points that Colin can win when Rose plays strategy \(A\) and which strategy does Colin need to play to achieve this?
2. Show that strategy \(B\) dominates strategy \(C\) and also that strategy \(Y\) dominates strategy \(Z\). 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. Is the game stable? Rose makes a random choice between the strategies, choosing strategy \(A\) with probability \(p _ { 1 }\), strategy \(B\) with probability \(p _ { 2 }\) and strategy \(D\) with probability \(p _ { 3 }\). She formulates the following LP problem to be solved using the Simplex algorithm: $$\begin{array} { l l } \text { maximise } & M = m - 5 , \\ \text { subject to } & m \leqslant 4 p _ { 1 } + 10 p _ { 2 } , \\ & m \leqslant 9 p _ { 1 } + 3 p _ { 2 } + 11 p _ { 3 } , \\ & m \leqslant 2 p _ { 1 } + 10 p _ { 2 } + p _ { 3 } , \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 , \\ \text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$ (You are not required to solve this problem.)
4. Explain how \(9 p _ { 1 } + 3 p _ { 2 } + 11 p _ { 3 }\) was obtained. A computer gives the solution to the LP problem as \(p _ { 1 } = \frac { 7 } { 48 } , p _ { 2 } = \frac { 27 } { 48 } , p _ { 3 } = \frac { 14 } { 48 }\).
5. Calculate the value of \(M\) at this solution.

4 Euan and Wai Mai play a zero-sum game. Each is trying to maximise the total number of points that they score in many repeats of the game. The table shows the number of points that Euan scores for each combination of strategies.

1. Explain what the term 'zero-sum game' means.
2. How many points does Wai Mai score if she chooses \(X\) and Euan chooses \(A\) ?
3. Why should Wai Mai never choose strategy \(Z\) ?
4. Delete the column for \(Z\) and find the play-safe strategy for Euan and the play-safe strategy for Wai Mai on the table that remains. Is the resulting game stable or not? State how you know. The value 3 in the cell corresponding to Euan choosing \(D\) and Wai Mai choosing \(X\) is changed to - 5 ; otherwise the table is unchanged. Wai Mai decides that she will choose her strategy by making a random choice between \(X\) and \(Y\), choosing \(X\) with probability \(p\) and \(Y\) with probability \(1 - p\).
5. Write down and simplify an expression for the expected score for Wai Mai when Euan chooses each of his four strategies.
6. Using graph paper, draw a graph showing Wai Mai's expected score against \(p\) for each of Euan's four strategies and hence calculate the optimum value of \(p\).

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

Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\).

1. Rewrite the matrix as necessary and state the new value of the game, \(v\), in terms of \(V\).
2. Define your decision variables.
3. Write down the objective function in terms of your decision variables.
4. Write down the constraints.
   

2. 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\).

6. 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.

2. 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.