Zero-sum game LP formulation

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.

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}

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.

7. Alexis and Becky are playing a zero-sum game. Alexis has two options, Q and R . Becky has three options, \(\mathrm { X } , \mathrm { Y }\) and Z .
Alexis intends to make a random choice between options Q and R , choosing option Q with probability \(p _ { 1 }\) and option R with probability \(p _ { 2 }\) Alexis wants to find the optimal values of \(p _ { 1 }\) and \(p _ { 2 }\) and formulates the following linear programme, writing the constraints as inequalities. $$\begin{aligned} & \text { Maximise } P = V \\ & \text { where } V = 3 + \text { the value of the gan } \\ & \text { subject to } V \leqslant 6 p _ { 1 } + p _ { 2 } \\ & \qquad \begin{aligned} & V \leqslant 8 p _ { 2 } \\ & V \leqslant 4 p _ { 1 } + 2 p _ { 2 } \\ & p _ { 1 } + p _ { 2 } \leqslant 1 \\ & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , V \geqslant 0 \end{aligned} \end{aligned}$$

1. Complete the pay-off matrix for Alexis in the answer book.
2. Use a graphical method to find the best strategy for Alexis.
3. Calculate the value of the game to Alexis. Becky 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 }\)
4. Determine the best strategy for Becky, making your method and working clear.

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.

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.

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.

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)

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