D2 June 2006 Q7
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 | 5 | 7 | 2 |
| \(A\) plays 2 | 3 | 8 | 4 |
| \(A\) plays 3 | 6 | 4 | 9 |
(a) Formulate the game as a linear programming problem for player \(A\), writing the constraints as equalities and clearly defining your variables. (5)
(b) Explain why it is necessary to use the simplex algorithm to solve this game theory problem. (1)
(c) Write down an initial simplex tableau making your variables clear. (2)
(d) Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use. (8)
| Scheme | Marks |
|---|---|
| e.g. Maximise \(\text{P} = \text{V}\) | B1 |
| Subject to: \(\text{V} - 5\text{p}_1 - 3\text{p}_2 - 6\text{p}_3 + r = 0\) | M1 |
| \(\text{V} - 7\text{p}_1 - 8\text{p}_2 - 4\text{p}_3 + s = 0\) \(\text{V} - 2\text{p}_1 - 4\text{p}_2 - 9\text{p}_3 + t = 0\) \(\text{p}_1 + \text{p}_2 + \text{p}_3\ (+\,u) = 1\) | A2, 1, 0 |
| where V = value of game to A, \(\text{P}_i\) = probability of A playing row \(i\) \(\text{P}_i \geqslant 0\) and \(r, s, t, u\) are slack variables all \(\geqslant 0\) | B1 |
| (5) |
Notes
B1 Maximise/minimise and consistent function
M1 constraints (condone non-negativity) – at least one correct must be equations
A2 all correct
A1 at least two correct
B1 defining variables
| Scheme | Marks |
|---|---|
| Not reducible and a three variable problem | B1 |
| (1) |
Notes
B1 cao – both
| Scheme | Marks | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
e.g.
| M1 A1 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (2) |
| Scheme | Marks | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| M1 A1 A1 B1ft (4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| M1 A1ft A1 B1ft (4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (8) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| (16 marks) |
Notes
Pivots are boxed (printed in bold in the scheme).
(Corrected from the printed mark scheme: in the first iteration the \(t\) row entry under \(\text{P}_1\) is printed as \(-3\) (it is \(-2 + 5 = 3\)); in the second iteration the \(\text{P}_3\) row entry under \(r\) is printed as \(\tfrac{1}{2}\) (it is \(-\tfrac{1}{2}\)) and the \(t\) row entry under \(s\) is printed as \(\tfrac{5}{2}\) (it is \(\tfrac{3}{2}\)).)