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

7 Kez and Lui play a zero-sum game. The game does not have a stable solution. The game is represented by the following pay-off matrix for Kez. 7

1. State, with a reason, why Kez should never play strategy \(\mathbf { K } _ { \mathbf { 2 } }\) 7
2. \(\quad\) Kez and Lui play the game 20 times.
   Kez plays their optimal mixed strategy.
   Find the expected number of times that Kez will play strategy \(\mathbf { K } _ { \mathbf { 3 } }\) Fully justify your answer.

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}

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

1. Explain, with justification, why this matrix may be reduced to a \(3 \times 3\) matrix by removing option S from player A's choices.
2. Verify that there is no stable solution to the reduced game. Player A intends to make a random choice between options \(\mathrm { Q } , \mathrm { R }\) and T , choosing option Q with probability \(p _ { 1 }\), option R 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 linear programme, writing the constraints as inequalities. Maximise \(P = V\), where \(V =\) the value of original game + 3 $$\begin{aligned} \text { subject to } & V \leqslant 4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \\ & V \leqslant 8 p _ { 1 } + p _ { 3 } \\ & V \leqslant 6 p _ { 1 } + 4 p _ { 2 } + 3 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}$$
3. Explain why \(V\) cannot exceed any of the following expressions $$4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \quad 8 p _ { 1 } + p _ { 3 } \quad 6 p _ { 1 } + 4 p _ { 2 } + 3 p _ { 3 }$$
4. Explain why it is necessary to use the constraint \(p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1\) The Simplex algorithm is used to solve the linear programming problem.
   Given that the optimal value of \(p _ { 1 } = \frac { 7 } { 11 }\) and the optimal value of \(p _ { 3 } = 0\)
5. calculate the value of the game to player A .
   (3) Player B 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 }\)
6. Determine the optimal strategy for player B, making your working clear.

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.

Andrew (\(A\)) and Barbara (\(B\)) play a zero-sum game. This game is represented by the following pay-off matrix for Andrew. $$A \begin{pmatrix} 3 & 5 & 4 \\ 1 & 4 & 2 \\ 6 & 3 & 7 \end{pmatrix}$$

1. Explain why this matrix may be reduced to $$\begin{pmatrix} 3 & 5 \\ 6 & 3 \end{pmatrix}$$ [8]
2. Hence find the best strategy for each player and the value of the game.

Emma and Freddie play a zero-sum game. This game is represented by the following pay-off matrix for Emma. \(\begin{pmatrix} -4 & -1 & 3 \\ 2 & 1 & -2 \end{pmatrix}\)

1. Show that there is no stable solution. [3]
2. Find the best strategy for Emma and the value of the game to her. [8]
3. Write down the value of the game to Freddie and his pay-off matrix. [3]

(Total 14 marks)

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

	\(B\) plays 1	\(B\) plays 2	\(B\) plays 3
\(A\) plays 1	5	7	2
\(A\) plays 2	3	8	4
\(A\) plays 3	6	4	9

1. Formulate the game as a linear programming problem for player \(A\), writing the constraints as equalities and clearly defining your variables. [5]
2. Explain why it is necessary to use the simplex algorithm to solve this game theory problem. [1]
3. Write down an initial simplex tableau making your variables clear. [2]
4. Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use. [8]

(Total 16 marks)

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

	B
	I	II	III
\multirow{3}{*}{A}	I	6	\(-4\)	\(-1\)
	II	\(-2\)	5	3
	III	5	1	\(-3\)

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 marks]
2. Define your decision variables. [2 marks]
3. Write down the objective function in terms of your decision variables. [2 marks]
4. Write down the constraints. [2 marks]

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

	Y
	\(Y_1\)	\(Y_2\)
\multirow{2}{*}{X}	\(X_1\)	\(-2\)	4
	\(X_2\)	6	\(-1\)

1. Explain why the game does not have a saddle point. [3 marks]
2. Find the optimal strategy for
   1. player X, [8 marks]
   2. player Y.
3. Find the value of the game. [2 marks]

The payoff matrix for player \(A\) in a two-person zero-sum game is shown below. \begin{array}{c|c|c|c|c} & & \multicolumn{3}{c}{B}
& & \text{I} & \text{II} & \text{III}
\hline \multirow{2}{*}{A} & \text{I} & -2 & 3 & -1
& \text{II} & 4 & -5 & 2
\end{array}

1. Formulate this information as a linear programming problem, the solution to which will give the optimal strategy for player \(B\). [7 marks]
2. By solving this linear programming problem, find the optimal strategy for player \(B\) and the value of the game. [14 marks]

[21 marks]

Kira and Julian play a zero-sum game that does not have a stable solution. Kira has three strategies to choose from: \(\mathbf{K_1}\), \(\mathbf{K_2}\) and \(\mathbf{K_3}\) To determine her optimal mixed strategy, Kira begins by defining the following variables: \(v =\) value of the game for Kira \(p_1 =\) probability of Kira playing strategy \(\mathbf{K_1}\) \(p_2 =\) probability of Kira playing strategy \(\mathbf{K_2}\) \(p_3 =\) probability of Kira playing strategy \(\mathbf{K_3}\) Kira then formulates the following linear programming problem. Maximise \(v\) subject to \(7p_1 + p_2 + 8p_3 \geq v\) \(3p_1 + 7p_2 + 2p_3 \geq v\) \(9p_1 + 2p_2 + 4p_3 \geq v\) and \(p_1 + p_2 + p_3 \leq 1\) \(p_1, p_2, p_3 \geq 0\)

1. 1. Explain why the condition \(p_1 + p_2 + p_3 \leq 1\) is necessary in Kira's linear programming problem. [1 mark]
   2. Explain why the condition \(p_1, p_2, p_3 \geq 0\) is necessary in Kira's linear programming problem. [1 mark]
2. Julian has three strategies to choose from: \(\mathbf{J_1}\), \(\mathbf{J_2}\) and \(\mathbf{J_3}\) Complete the following pay-off matrix which represents the game for Kira. [3 marks]

   	Julian
   Strategy	\(\mathbf{J_1}\)	\(\mathbf{J_2}\)	\(\mathbf{J_3}\)
   \(\mathbf{K_1}\)	7
   Kira \(\mathbf{K_2}\)
   \(\mathbf{K_3}\)

Janet and Samantha play a zero-sum game. The game is represented by the following pay-off matrix for Janet. Samantha

	Strategy	\(S_1\)	\(S_2\)	\(S_3\)
\multirow{4}{*}{Janet}	\(J_1\)	2	7	6
	\(J_2\)	5	5	1
	\(J_3\)	4	3	8
	\(J_4\)	1	6	4

1. Explain why Janet should never play strategy \(J_4\) [1 mark]
2. Janet wants to maximise her winnings from the game. She defines the following variables. \(p_1 = \) the probability of Janet playing strategy \(J_1\) \(p_2 = \) the probability of Janet playing strategy \(J_2\) \(p_3 = \) the probability of Janet playing strategy \(J_3\) \(v = \) the value of the game for Janet Janet then formulates her situation as the following linear programming problem. Maximise \(P = v\) subject to \(2p_1 + 5p_2 + 4p_3 \geq v\) \(7p_1 + 5p_2 + 3p_3 \geq v\) \(6p_1 + p_2 + 8p_3 \geq v\) and \(p_1 + p_2 + p_3 \leq 1\) \(p_1, p_2, p_3 \geq 0\)
   1. Complete the initial Simplex tableau for Janet's situation in the grid below. [2 marks]

      \(P\)	\(v\)	\(p_1\)	\(p_2\)	\(p_3\)			value

   2. Hence, perform one iteration of the Simplex algorithm, showing your answer on the grid below. [2 marks]

      \(P\)	\(v\)	\(p_1\)	\(p_2\)	\(p_3\)			value

3. Further iterations of the Simplex algorithm are performed until an optimal solution is reached. The grid below shows part of the final Simplex tableau.

   \(p_1\)	\(p_2\)	value
   1	0	\(\frac{1}{12}\)
   0	1	\(\frac{1}{2}\)

   Find the probability of Janet playing strategy \(J_3\) when she is playing to maximise her winnings from the game. [1 mark]