Zero-sum game optimal mixed strategy

7. (a) Explain briefly what is meant by a zero-sum game. A two person zero-sum game is represented by the following pay-off matrix for player \(A\). (b) Verify that there is no stable solution to this game.
(c) Find the best strategy for player \(A\) and the value of the game to her.
(d) Formulate the game as a linear programming problem for player \(B\). Write the constraints as inequalities and define your variables clearly.
(Total 17 marks)

5. (a) In game theory, explain the circumstances under which column \(( x )\) dominates column \(( y )\) in a two-person zero-sum game. Liz and Mark play a zero-sum game. This game is represented by the following pay-off matrix for Liz. (b) Verify that there is no stable solution to this game.
(c) Find the best strategy for Liz and the value of the game to her. The game now changes so that when Liz plays 1 and Mark plays 3 the pay-off to Liz changes from 2 to
4. All other pay-offs for this zero-sum game remain the same.
(d) Explain why a graphical approach is no longer possible and briefly describe the method Liz should use to determine her best strategy.
(2) (Total 16 marks)

3. 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.
2. Reduce the game so that player B has a choice of only two actions.
3. Write down the reduced pay-off matrix for player B.
4. Find the best strategy for player B and the value of the game to player B.

5. Agent Goodie is planning to break into Evil Doctor Fiendish's secret base. He uses game theory to determine whether to approach the base from air, sea or land.
Evil Doctor Fiendish decides each day which of three possible plans he should use to protect his base. Agent Goodie evaluates the situation. He assigns numbers, negative indicating he fails in his mission, positive indicating success, to create a pay-off matrix. The numbers range from - 3 (he fails in his mission and is captured) to 5 (he successfully achieves his mission and escapes uninjured) and the pay-off matrix is shown below.

1. Reduce the game so that Agent Goodie has only two choices, explaining your reasoning.
2. Use game theory to determine Agent Goodie's best strategy.
3. Find the value of the game to Agent Goodie.

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.

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.

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.

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.

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.

4

1. Two people, Adam and Bill, play a zero-sum game. The game is represented by the following pay-off matrix for Adam. 4
2. Roza plays a different zero-sum game against a computer. The game is represented by the following pay-off matrix for Roza.

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]

4 Monica and Vladimir play a zero-sum game. The game is represented by the following pay-off matrix for Monica.

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.