7.08d Nash equilibrium: identification and interpretation

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.

2 Alex and Roberto play a zero-sum game. The game is represented by the following pay-off matrix for Alex. \begin{table}[h] \end{table}

1. Show that this game has a stable solution and state the play-safe strategy for each player.
2. List any saddle points.

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.

3 Alex and Sam are playing a zero-sum game. The game is represented by the pay-off matrix for Alex. 3

1. Explain why the value of the game is 2
   3
2. Identify the play-safe strategy for each player.
   Each pipe is labelled with its upper capacity in \(\mathrm { cm } ^ { 3 } \mathrm {~s} ^ { - 1 }\) \includegraphics[max width=\textwidth, alt={}, center]{5a826f8b-4751-4589-ad0a-109fc5c821f2-04_620_940_450_550}

3 Summer and Haf play a zero-sum game. The pay-off matrix for the game is shown below. Haf 3

1. Show that the game has a stable solution.
   3
2. (i) State the value of the game for Summer. 3 (b) (ii) State the play-safe strategy for each player.

6 Xander and Yvonne are playing a zero-sum game. The game is represented by the pay-off matrix for Xander. \begin{table}[h] \end{table} 6

1. Show that the game has a stable solution.
   6
2. State the play-safe strategy for each player. Play-safe strategy for Xander is \(\_\_\_\_\) Play-safe strategy for Yvonne is \(\_\_\_\_\) 6
3. The game that Xander and Yvonne are playing is part of a marbles challenge. The pay-off matrix values represent the number of marbles gained by Xander in each game. In the challenge, the game is repeated until one player has 24 marbles more than the other player. Explain why Xander and Yvonne must play at least 3 games to complete the challenge.

6 Victoria and Albert play a zero-sum game. The game is represented by the following pay-off matrix for Victoria. 6

1. Find the play-safe strategies for each player.
   6
2. State, with a reason, the strategy that Albert should never play.
   6
3. (i) Determine an optimal mixed strategy for Victoria.
   [0pt] [5 marks]
   6 (c) (ii) Find the value of the game for Victoria.
   6 (c) (iii) State an assumption that must made in order that your answer for part (c)(ii) is the maximum expected pay-off that Victoria can achieve.

7 Avon and Roj play a zero-sum game. The game is represented by the following pay-off matrix for Avon. 7 (c)

1. Find the optimal mixed strategy for Avon.
   7
2. Find the value of the game for Avon.
   

7 (d) Roj thinks that his best outcome from the game is to play strategy \(\mathbf { R } _ { \mathbf { 2 } }\) each time. Avon notices that Roj always plays strategy \(\mathbf { R } _ { \mathbf { 2 } }\) and Avon wants to use this knowledge to maximise his expected pay-off from the game. Explain how your answer to part (c)(i) should change and find Avon's maximum expected pay-off from the game. \includegraphics[max width=\textwidth, alt={}, center]{59347089-ea4a-4ee6-b40e-1ab78aa7cdc3-16_2490_1735_219_139}

7. A two person zero-sum game is represented by the pay-off matrix for player A shown above. It is given that \(k\) is an integer.

1. Show that Q is the play-safe option for player A regardless of the value of \(k\). Given that Z is the play-safe option for player B ,
2. determine the range of possible values of \(k\). You must make your working clear.
3. Explain why player B should never play option X. 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 find the optimal values of \(p _ { 1 } , p _ { 2 }\) and \(p _ { 3 }\) using the Simplex algorithm.
   Given that \(k > - 4\), player A formulates the following objective function for the corresponding linear program. $$\text { Maximise } P = V \text {, where } V = \text { the value of the original game } + 4$$
4. 1. Formulate the constraints of the linear programming problem for player A. You should write the constraints as equations.
   2. Write down an initial Simplex tableau, making your variables clear. The Simplex algorithm is used to solve the linear programming problem. It is given that in the final Simplex tableau the optimal value of \(p _ { 1 } = \frac { 7 } { 37 }\), the optimal value of \(p _ { 2 } = \frac { 17 } { 37 }\) and all the slack variables are zero.
5. Determine the value of \(k\), making your method clear.

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

	I	II	III	IV
I	\(-4\)	\(-5\)	\(-2\)	4
II	\(-1\)	1	\(-1\)	2
III	0	5	\(-2\)	\(-4\)
IV	\(-1\)	3	\(-1\)	1

1. Determine the play-safe strategy for each player. [4]
2. Verify that there is a stable solution and determine the saddle points. [3]
3. State the value of the game to \(B\). [1]