| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2009 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Standard +0.8 This requires translating a zero-sum game into LP form with proper variable definitions, constraint formulation for each of Sam's strategies, and objective function setup. While the procedure is systematic once learned, it demands understanding of game theory concepts, careful algebraic manipulation of inequalities, and precise mathematical notation—going beyond routine D2 exercises. |
| Spec | 7.08f Mixed strategies via LP: reformulate as linear programming problem |
| 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 |
| Answer | Marks | Guidance |
|---|---|---|
| E.g. Add 6 to make all elements positive \(\begin{bmatrix} 4 & 14 & 5 \\ 13 & 10 & 3 \\ 7 & 1 & 10 \end{bmatrix}\) | B1 | Making all elements positive |
| Let Laura play 1, 2 and 3 with probabilities \(p_1, p_2\) and \(p_3\) respectively; Let \(V =\) value of game \(+ 6\) | B1 | Defining variables |
| Maximise \(P = V\); Subject to: \(V - 4p_1 - 13p_2 - 7p_3 \leq 0\); \(V - 14p_1 - 10p_2 - p_3 \leq 0\); \(V - 5p_1 - 3p_2 - 10p_3 \leq 0\); \(p_1 + p_2 + p_3 \leq 1\); \(p_1, p_2, p_3 \geq 0\) | B1 M1 A3, 2ft, 1ft, 0 (7) | Objective, cao word and function; At least one constraint in terms of their variables, must be going down columns. Accept = here. |
| Alt using \(x_i\) method: Now additionally need: let \(x_i = \frac{p_i}{v}\) for 2B1; minimise \((P) = x_1 + x_2 + x_3 = \frac{1}{v}\); subject to: \(4x_1 + 13x_2 + 7x_3 \geq 1\); \(14x_1 + 10x_2 + x_3 \geq 1\); \(5x_1 + 3x_2 + 10x_3 \geq 1\); \(x_i \geq 0\) |
| E.g. Add 6 to make all elements positive $\begin{bmatrix} 4 & 14 & 5 \\ 13 & 10 & 3 \\ 7 & 1 & 10 \end{bmatrix}$ | B1 | Making all elements positive |
| Let Laura play 1, 2 and 3 with probabilities $p_1, p_2$ and $p_3$ respectively; Let $V =$ value of game $+ 6$ | B1 | Defining variables |
| Maximise $P = V$; Subject to: $V - 4p_1 - 13p_2 - 7p_3 \leq 0$; $V - 14p_1 - 10p_2 - p_3 \leq 0$; $V - 5p_1 - 3p_2 - 10p_3 \leq 0$; $p_1 + p_2 + p_3 \leq 1$; $p_1, p_2, p_3 \geq 0$ | B1 M1 A3, 2ft, 1ft, 0 (7) | Objective, cao word and function; At least one constraint in terms of their variables, must be going down columns. Accept = here. |
| **Alt using $x_i$ method**: Now additionally need: let $x_i = \frac{p_i}{v}$ for 2B1; minimise $(P) = x_1 + x_2 + x_3 = \frac{1}{v}$; subject to: $4x_1 + 13x_2 + 7x_3 \geq 1$; $14x_1 + 10x_2 + x_3 \geq 1$; $5x_1 + 3x_2 + 10x_3 \geq 1$; $x_i \geq 0$ | | |
**Total [7]**8. Laura (L) and Sam (S) play a two-person zero-sum game which is represented by the following pay-off matrix for Laura.
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
& S plays 1 & S plays 2 & S plays 3 \\
\hline
L plays 1 & - 2 & 8 & - 1 \\
\hline
L plays 2 & 7 & 4 & - 3 \\
\hline
L plays 3 & 1 & - 5 & 4 \\
\hline
\end{tabular}
\end{center}
Formulate the game as a linear programming problem for Laura, writing the constraints as inequalities. Define your variables clearly.
\hfill \mbox{\textit{Edexcel D2 2009 Q8 [7]}}