7.08f Mixed strategies via LP: reformulate as linear programming problem

5. 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. Explain why the \(4 \times 4\) game above may be reduced to the following \(3 \times 3\) game.
3. Formulate the \(3 \times 3\) game as a linear programming problem for player A. Write the

   - 2	1	3
   - 1	3	2
   1	- 2	- 1

   constraints as inequalities. Define your variables clearly.

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

1. Write down the pay off matrix for player \(B\).
2. Formulate the game as a linear programming problem for player \(B\), writing the constraints as equalities and stating your variables clearly.

6. Anna (A) and Roland (R) play a two-person zero-sum game which is represented by the following pay-off matrix for Anna. Formulate the game as a linear programming problem for player \(\mathbf { R }\). Write the constraints as inequalities. Define your variables clearly.
(Total 8 marks)

8. Laura (L) and Sam (S) play a two-person zero-sum game which is represented by the following pay-off matrix for Laura. Formulate the game as a linear programming problem for Laura, writing the constraints as inequalities. Define your variables clearly.

7. A two person zero-sum game is represented by the following pay-off matrix for player A. Formulate the game as a linear programming problem for player A. Write the constraints as inequalities and define your variables.

7. A two-person zero-sum game is represented by the following pay-off matrix for player A. Formulate the game as a linear programming problem for player A. Write the constraints as inequalities. Define your variables clearly.
(Total 7 marks)

6. 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. Formulate the game as a linear programming problem for player A. Define your variables clearly. Write the constraints as equations.
3. Write down an initial simplex tableau, making your variables clear.

5 Rose and Colin are playing a game in which they each have four cards. Each player chooses a card from those in their hand, and simultaneously they show each other the cards they have chosen. The table below shows how many points Rose wins for each combination of cards. In each case the number of points that Colin wins is the negative of the entry in the table. Both Rose and Colin are trying to win as many points as possible.

1. What is the greatest number of points that Colin can win when Rose chooses and which card does Colin need to choose to achieve this?
2. Explain why Rose should never choose and find the card that Colin should never choose. 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 and show whether or not the game is stable. Rose makes a random choice between her cards, choosing with probability \(x\) with probability \(y\), and with probability \(z\). She formulates the following LP problem to be solved using the Simplex algorithm:
   maximise \(\quad M = m - 6\),
   subject to \(\quad m \leqslant 4 x + 10 y\), \(n \leqslant 9 x + 3 y + 11 z\), \(n \leqslant 2 x + 10 y + z\), \(x + y + z \leqslant 1\),
   and \(x \geqslant 0 , y \geqslant 0 , z \geqslant 0 , m \geqslant 0\).
   (You are not required to solve this problem.)
4. Explain how \(9 x + 3 y + 11 z\) was obtained. The Simplex algorithm is used to solve the LP problem. The solution has \(x = \frac { 7 } { 48 } , y = \frac { 27 } { 48 } , z = \frac { 14 } { 48 }\).
5. Calculate the optimal value of \(M\).

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

1. Alka is considering paying \(\pounds 5\) to play a game. The game involves rolling two fair six-sided dice. If the sum of the numbers on the two dice is at least 8 , she receives \(\pounds 10\), otherwise she loses and receives nothing.

If Alka loses, she can pay a further \(\pounds 5\) to roll the dice again. If both dice show the same number then she receives \(\pounds 35\), otherwise she loses and receives nothing.

1. Draw a decision tree to model Alka's possible decisions and the possible outcomes.
2. Determine Alka's optimal EMV and state the optimal strategy indicated by the decision tree.

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)

2. 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. Explain why the game above can be reduced to the following \(3 \times 3\) game.

   - 3	2	5
   - 2	5	4
   2	- 3	- 1

4. Formulate the \(3 \times 3\) game as a linear programming problem for player A, defining your variables clearly and writing the constraints as inequalities.

4. Eugene and Stephen play a zero-sum game. The pay-off matrix shows the number of points that Eugene scores for each combination of strategies.

1. Find the play-safe strategies for each of Eugene and Stephen, and hence show that this zero-sum game does not have a stable solution.
2. Suppose that Eugene knows that Stephen will use his play-safe strategy. Explain why Eugene should change from his play-safe strategy. You should state as part of your answer which strategy Eugene should now play.
3. Formulate the game as a linear programming problem for Stephen. Define your variables clearly. Write the constraints as equations.

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

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.

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}\)