D2 June 2010 Q7

EdexcelOld spec7 marksGame Theory

7. 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	−4	5	1
A plays 2	3	−1	−2
A plays 3	−3	0	2

Formulate the game as a linear programming problem for player A. Write the constraints as inequalities and define your variables. (7)

Mark scheme

Scheme

Marks

\(\begin{bmatrix}-4 & 5 & 1 \\ 3 & -1 & -2 \\ -3 & 0 & 2\end{bmatrix}\rightarrow \text{add 5 to all entries}\begin{bmatrix}1 & 10 & 6 \\ 8 & 4 & 3 \\ 2 & 5 & 7\end{bmatrix}\)

Either	Or
Define variables e.g. let \(p_1\), \(p_2\) and \(p_3\) be the probability that A plays rows 1, 2 and 3 respectively. Maximise \(P = V\) Subject to: \(V - p_1 - 8p_2 - 2p_3 \leqslant 0\) \(V - 10p_1 - 4p_2 - 5p_3 \leqslant 0\) \(V - 6p_1 - 3p_2 - 7p_3 \leqslant 0\) \(p_1 + p_2 + p_3 \leqslant 1\) \(p_1, p_2, p_3 \geqslant 0\)	Define variables e.g. let \(p_1\), \(p_2\) and \(p_3\) be the probability that A plays rows 1, 2 and 3 respectively. Let \(x_i = \dfrac{p_i}{V}\) Minimise \(P = x_1 + x_2 + x_3\) Subject to \(x_1 + 8x_2 + 2x_3 \geqslant 1\) \(10x_1 + 4x_2 + 5x_3 \geqslant 1\) \(6x_1 + 3x_2 + 7x_3 \geqslant 1\) \(x_1, x_2, x_3 \geqslant 0\)

B1
B1
M1 A1 A1 A1

(7 marks)

Notes

1M1: Adding \(n\ (\geqslant 4)\) to all entries

1B1: Defining variables

1B1: Objective correct

2M1: At least 3 constraints, using columns, one of correct form

1A1ft: one correct constraint – excluding non-negativity constraint

2A1ft: two correct constraints – excluding non-negativity constraint

3A1: cao including non-negativity constraint