Converting games to linear programming problemsAQA A-Level Further Maths: Subtopic test

1. 1
   Rowan and Colin play a zero-sum game with pay-off matrix for Rowan $\begin{pmatrix} -3 & 2 & 1 \\ 1 & -1 & 0 \\ 2 & 0 & -2 \end{pmatrix}$. Rowan wants to convert the game into a linear programming problem to find his optimal mixed strategy, and first adds the same constant to every entry.

   (a)

   What is the least integer that must be added to every entry so that no entry is negative?

   [1 mark]

   • A3
   • B2
   • C4
   • D1

   (b)

   The adjusted game has value $3$. What is the value of the original game?

   [1 mark]

   • A$6$
   • B$3$
   • C$0$
   • D$-3$

   (c)

   State the effect of adding the constant on Rowan's optimal strategy and on the value of the game, giving a reason.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Rowan and Colin play a zero-sum game. After a constant has been added, Rowan's pay-off matrix is $\begin{pmatrix} 3 & 1 \\ 2 & 4 \\ 1 & 5 \end{pmatrix}$, with rows 1, 2, 3 for Rowan and columns 1, 2 for Colin. Rowan plays rows 1, 2, 3 with probabilities $p_1$, $p_2$, $p_3$, and $V$ is the value of this game. Rowan wishes to maximise $V$.

   (a)

   Which inequality comes from Colin playing column 2?

   [1 mark]

   • A$V-3p_1-2p_2-p_3\leq0$
   • B$V-p_1-4p_2-5p_3\geq0$
   • C$V-3p_1-p_2\leq0$
   • D$V-p_1-4p_2-5p_3\leq0$

   (b)

   Which constraint ensures that the probabilities are valid?

   [1 mark]

   • A$p_1+p_2+p_3\geq1$
   • B$p_1+p_2+p_3\leq1$
   • C$p_1=p_2=p_3$
   • D$V\leq p_1+p_2+p_3$

   (c)

   Explain, in context, why $V$ must be no greater than Rowan's expected pay-off against each of Colin's columns.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Rowan and Colin play a zero-sum game with pay-off matrix for Rowan $\begin{pmatrix} -1 & 2 & 1 \\ 2 & -2 & 0 \\ 0 & 1 & -1 \end{pmatrix}$. Two is added to every entry, giving $\begin{pmatrix} 1 & 4 & 3 \\ 4 & 0 & 2 \\ 2 & 3 & 1 \end{pmatrix}$. Rowan plays rows 1, 2, 3 with probabilities $p_1$, $p_2$, $p_3$, and $V$ is the value of the adjusted game.

   (a)

   Formulate Rowan's problem as a linear programming problem, in the form of an objective function and constraints, ready to be solved by the simplex algorithm.

   [3 marks]

   (b)

   The simplex algorithm gives $V=\frac{30}{13}$, $p_1=\frac{6}{13}$, $p_2=\frac{5}{13}$ and $p_3=\frac{2}{13}$. Find the value of the original game and Rowan's optimal strategy, and say how many times in 130 plays Rowan should choose row 2.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Rowan and Colin play a zero-sum game with pay-off matrix for Rowan $\begin{pmatrix} -2 & 3 & -1 \\ 1 & -2 & 2 \\ -1 & 0 & 1 \end{pmatrix}$. Rowan plays rows 1, 2, 3 with probabilities $p_1$, $p_2$, $p_3$ and wants to find his optimal strategy by linear programming.

   (a)

   Add the least integer to every entry that makes all entries non-negative, and formulate the problem as a linear programming problem ready for the simplex algorithm.

   [6 marks]

   (b)

   The simplex algorithm gives $V=\frac{15}{8}$, $p_1=\frac38$, $p_2=\frac58$ and $p_3=0$ for the adjusted game. Find the value of the original game and Rowan's optimal strategy. Find Rowan's expected pay-off in the adjusted game against each of Colin's columns, and deduce which column Colin never plays.

   [6 marks]

   Total for question 4: 12 marks

End of questions