D2 January 2006 Q5
5. 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 | B plays 4 | |
|---|---|---|---|---|
| A plays 1 | −2 | 1 | 3 | −1 |
| A plays 2 | −1 | 3 | 2 | 1 |
| A plays 3 | −4 | 2 | 0 | −1 |
| A plays 4 | 1 | −2 | −1 | 3 |
(a) Verify that there is no stable solution to this game. (3)
(b) Explain why the \(4 \times 4\) game above may be reduced to the following \(3 \times 3\) game. (2)
| −2 | 1 | 3 |
| −1 | 3 | 2 |
| 1 | −2 | −1 |
(c) Formulate the \(3 \times 3\) game as a linear programming problem for player A. Write the constraints as inequalities. Define your variables clearly. (8)
| Scheme | Marks |
|---|---|
| Row minimums \(\{-2, -1, -4, -2\}\) row maximum \(= -1\) | M1 |
| Column maximums \(\{1, 3, 3, 3\}\) column minimum \(= 1\) | A1 |
| Since \(1 \neq -1\) not stable | A1 |
| (3) |
| Scheme | Marks |
|---|---|
| Row 2 dominates Row 3 | B1 |
| Column 1 dominates column 4 | B1 |
| (2) |
| Scheme | Marks |
|---|---|
| Let A play row \(\text{R}_1\) with probability \(\text{p}_1\), \(\text{R}_2\) with probability \(\text{p}_2\) and “\(\text{R}_3\)” with probability \(\text{p}_3\). | B1 |
| \(\begin{pmatrix}-2&1&3\\-1&3&2\\1&-2&-1\end{pmatrix}\ \underset{+3}{\overset{\text{eg}}{\to}}\ \begin{pmatrix}1&4&6\\2&6&5\\4&1&2\end{pmatrix}\) | M1 (2) |
| e.g. maximise \(\text{P} = \text{V}\) | M1 A1 |
| subject to \(\text{V} - \text{p}_1 - 2\text{p}_2 - 4\text{p}_3 \leqslant 0\) \(\text{V} - 4\text{p}_1 - 6\text{p}_2 - \text{p}_3 \leqslant 0\) \(\text{V} - 6\text{p}_1 - 5\text{p}_2 - 2\text{p}_3 \leqslant 0\) \(\text{p}_1 + \text{p}_2 + \text{p}_3 \leqslant 1\) \(\text{V}, \text{p}_1, \text{p}_2, \text{p}_3 \geqslant 0\) | A4ft, 3ft, 2ft, 1ft, 0 (6) |
| (13 marks) |
Notes
OR
| e.g. Let \(x_i = \dfrac{p_i}{v}\quad \therefore\ \dfrac{1}{v} = x_1 + x_2 + x_3\) | M1 |
| minimise \(\text{P} = x_1 + x_2 + x_3\) | A1 |
| subject to \(x_1 + 2x_2 + 4x_3 \geqslant 1\) \(4x_1 + 6x_2 + x_3 \geqslant 1\) \(6x_1 + 5x_2 + 2x_3 \geqslant 1\) \(x_1, x_2, x_3 \geqslant 0\) | A4ft 3ft 2ft 1ft 0 (6) |
+ other equivalent methods.
(Corrected from the printed mark scheme: \(\text{p}_1 + \text{p}_2 + \text{p}_3 \leqslant 1\) is printed as \(\text{p}_1 + \text{p}_2 - \text{p}_3 \leqslant 1\); in the alternative, \(6x_1 + 5x_2 + 2x_3\) is printed as \(6x_1 + 5x_1 + 2x_3\) and \(x_1, x_2, x_3 \geqslant 0\) as \(x_1 + x_2 + x_3 \geqslant 0\).)