D2 June 2009 Q8
8. Laura (L) and Sam (S) play a two-person zero-sum game which is represented by the following pay-off matrix for Laura.
| S plays 1 | S plays 2 | S plays 3 | |
|---|---|---|---|
| L plays 1 | −2 | 8 | −1 |
| L plays 2 | 7 | 4 | −3 |
| L plays 3 | 1 | −5 | 4 |
Formulate the game as a linear programming problem for Laura, writing the constraints as inequalities. Define your variables clearly. (7)
| Scheme | Marks |
|---|---|
| E.g. Add 6 to make all elements positive \(\begin{bmatrix}4 & 14 & 5 \\ 13 & 10 & 3 \\ 7 & 1 & 10\end{bmatrix}\) | B1 |
| Let Laura play 1, 2 and 3 with probabilities \(p_1\), \(p_2\) and \(p_3\) respectively Let \(V\) = value of game + 6 | B1 |
| e.g. Maximise \(P = V\) | B1 |
| Subject to: \(V - 4p_1 - 13p_2 - 7p_3 \leqslant 0\) \(V - 14p_1 - 10p_2 - p_3 \leqslant 0\) \(V - 5p_1 - 3p_2 - 10p_3 \leqslant 0\) \(p_1 + p_2 + p_3 \leqslant 1\) \(p_1, p_2, p_3 \geqslant 0\) | M1 A3,2ft,1ft,0 |
| (7) | |
| (7 marks) |
Notes
1B1: Making all elements positive
2B1: Defining variables
3B1: Objective, cao word and function
1M1: At least one constraint in terms of their variables, must be going down columns. Accept = here.
1A1ft: ft their table. One constraint in V correct.
2A1ft: ft their table. Two constraints in V correct.
3A1: CAO all correct.
Alt using \(x_i\) method
Now additionally need: let \(x_i = \dfrac{p_i}{v}\) for 2B1
\[\begin{aligned}&\text{minimise } (P) = x_1 + x_2 + x_3 = \frac{1}{v}\\ &\text{subject to:}\\ &4x_1 + 13x_2 + 7x_3 \geqslant 1\\ &14x_1 + 10x_2 + x_3 \geqslant 1\\ &5x_1 + 3x_2 + 10x_3 \geqslant 1\\ &x_i \geqslant 0\end{aligned}\]