7.08c Pure strategies: play-safe strategies and stable solutions

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.

5 Alex and Beth play a zero-sum game. Alex chooses a strategy P, Q or R and Beth chooses a strategy \(\mathrm { X } , \mathrm { Y }\) or Z . The table shows the number of points won by Alex for each combination of strategies. The entry for cell \(( \mathrm { P } , \mathrm { X } )\) is \(x\), where \(x\) is an integer. \begin{table}[h] \end{table} Suppose that P is a play-safe strategy.

1. 1. Determine the values of \(x\) for which the game is stable.
   2. Determine the values of \(x\) for which the game is unstable. The game can be reduced to a \(2 \times 3\) game using dominance.
2. Write down the pay-off matrix for the reduced game. When the game is unstable, Alex plays strategy P with probability \(p\).
3. Determine, as a function of \(x\), the value of \(p\) for the optimal mixed strategy for Alex. Suppose, instead, that P is not a play-safe strategy and the value of \(x\) is - 5 .
4. Show how to set up a linear programming formulation that could be used to find the optimal mixed strategy for Alex.

4 The table shows the pay-off matrix for player \(A\) in a two-person zero-sum game between \(A\) and \(B\). Player \(A\) Player \(B\)

1. Find the play-safe strategy for player \(A\) and the play-safe strategy for player \(B\). Use the values of the play-safe strategies to determine whether the game is stable or unstable.
2. If player \(B\) knows that player \(A\) will use their play-safe strategy, which strategy should player \(B\) use?
3. Suppose that the value in the cell where both players use their play-safe strategies can be changed, but all other entries are unchanged. Show that there is no way to change this value that would make the game stable.
4. Suppose, instead, that the value in one cell can be changed, but all other entries are unchanged, so that the game becomes stable. Identify a suitable cell and write down a new pay-off value for that cell which would make the game stable.
5. Show that the zero-sum game in the table above has a Nash equilibrium and explain what this means for the players.

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.

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.

8. A two-person zero-sum game is represented by the pay-off matrix for player A shown below. \section*{Player B} Player A

1. Verify that there is no stable solution to this game.
2. Explain why player A should never play option T. You must make your reasoning clear. Player A intends to make a random choice between options \(\mathrm { Q } , \mathrm { R }\) and S , choosing option \(Q\) with probability \(p _ { 1 }\), option \(R\) with probability \(p _ { 2 }\) and option \(S\) with probability \(p _ { 3 }\) Player A wants to calculate the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm.
3. 1. Formulate the game as a linear programming problem for player A. You should write the constraints as equations.
   2. Write down an initial Simplex tableau for this linear programming problem, making your variables clear. The linear programming problem is solved using the Simplex algorithm. The optimal value of \(p _ { 1 }\) is \(\frac { 6 } { 11 }\) and the optimal value of \(p _ { 2 }\) is 0
4. Find the best strategy for player B, defining any variables you use.

7. 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 { R } , \mathrm { S }\) and T , choosing option R with probability \(p _ { 1 }\), option S with probability \(p _ { 2 }\) and option T 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 objective function for the corresponding linear programme. $$\text { Maximise } P = V \quad \text { where } V = \text { the value of the game } + 3$$
2. Determine an initial Simplex tableau, making your variables and working clear. After several iterations of the Simplex algorithm, a possible final tableau is

   b.v.	\(V\)	\(p _ { 1 }\)	\(p _ { 2 }\)	\(p _ { 3 }\)	r	\(s\)	\(t\)	\(u\)	Value
   \(p _ { 3 }\)	0	0	0	1	\(\frac { 1 } { 10 }\)	\(- \frac { 3 } { 80 }\)	\(- \frac { 1 } { 16 }\)	\(\frac { 33 } { 80 }\)	\(\frac { 33 } { 80 }\)
   \(p _ { 2 }\)	0	0	1	0	\(- \frac { 1 } { 10 }\)	\(\frac { 13 } { 80 }\)	\(- \frac { 1 } { 16 }\)	\(\frac { 17 } { 80 }\)	\(\frac { 17 } { 80 }\)
   V	1	0	0	0	\(\frac { 1 } { 2 }\)	\(\frac { 5 } { 16 }\)	\(\frac { 3 } { 16 }\)	\(\frac { 73 } { 16 }\)	\(\frac { 73 } { 16 }\)
   \(p _ { 1 }\)	0	1	0	0	0	\(- \frac { 1 } { 8 }\)	\(\frac { 1 } { 8 }\)	\(\frac { 3 } { 8 }\)	\(\frac { 3 } { 8 }\)
   \(P\)	0	0	0	0	\(\frac { 1 } { 2 }\)	\(\frac { 5 } { 16 }\)	\(\frac { 3 } { 16 }\)	\(\frac { 73 } { 16 }\)	\(\frac { 73 } { 16 }\)

3. 1. State the best strategy for player A.
   2. Calculate the value of the game for player B. Player B intends to make a random choice between options \(\mathrm { X } , \mathrm { Y }\) and Z .
4. Determine the best strategy for player B, making your method and working clear.
   (3)

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

1. Explain, with justification, how this matrix may be reduced to a \(3 \times 3\) matrix.
2. Find the play-safe strategy for each player and verify that there is no stable solution to this game. The game is formulated as a linear programming problem for player A .
   The objective is to maximise \(P = V\), where \(V\) is the value of the game to player A.
   One of the constraints is that \(p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1\), where \(p _ { 1 } , p _ { 2 } , p _ { 3 }\) are the probabilities that player A plays 1, 2, 3 respectively.
3. Formulate the remaining constraints for this problem. Write these constraints as inequalities. The Simplex algorithm is used to solve the linear programming problem.
   The solution obtained is \(p _ { 1 } = 0 , p _ { 2 } = \frac { 3 } { 7 } , p _ { 3 } = \frac { 4 } { 7 }\)
4. Calculate the value of the game to player A.

5 In each round of a card game two players each have four cards. Every card has a coloured number.

• Player A's cards are red 1 , blue 2 , red 3 and blue 4.
• Player B's cards are red 1 , red 2 , blue 3 and blue 4 .

Each player chooses one of their cards. The players then show their choices simultaneously and deduce how many points they have won or lost as follows:

• If the numbers are the same both players score 0 .
• If the numbers are different but are the same colour, the player with the lower value card scores the product of the numbers on the cards.
• If the numbers are different and are different colours, the player with the higher value card scores the sum of the numbers on the cards.
• The game is zero-sum.
  1. Complete the pay-off matrix for this game, with player A on rows.
  2. Determine the play-safe strategy for each player.
  3. Use dominance to show that player A should not choose red 3 . You do not need to identify other rows or columns that are dominated.
  4. Determine, with a reason, whether the game is stable or unstable.

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.