| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2010 |
| Session | June |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Standard +0.3 This is a standard textbook exercise in D2 requiring recall of the LP formulation method for zero-sum games. Students follow a memorized procedure: define probabilities and value variable, write one constraint per opponent strategy, add probability sum constraint. No problem-solving or novel insight required, just mechanical application of a formula, making it slightly easier than average. |
| Spec | 7.08f Mixed strategies via LP: reformulate as linear programming problem |
| 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 |
| Answer | Marks |
|---|---|
| M1 | Adding \(n\ (\geq 4)\) to all entries |
| Define variables: let \(p_1, p_2, p_3\) be the probability that A plays rows 1, 2 and 3 respectively | B1 |
| Maximise \(P = V\) | B1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(V - p_1 - 8p_2 - 2p_3 \leq 0\) | M1, A1 | |
| \(V - 10p_1 - 4p_2 - 5p_3 \leq 0\) | A1 | |
| \(V - 6p_1 - 3p_2 - 7p_3 \leq 0\) | A1 | |
| \(p_1 + p_2 + p_3 \leq 1\) | A1 | |
| \(p_1, p_2, p_3 \geq 0\) | (7) |
| Answer | Marks |
|---|---|
| Let \(x_i = \frac{p_i}{V}\), Minimise \(P = x_1 + x_2 + x_3\) | B1, B1 |
| Answer | Marks | Guidance |
|---|---|---|
| \(x_1 + 8x_2 + 2x_3 \geq 1\) | M1, A1 | |
| \(10x_1 + 4x_2 + 5x_3 \geq 1\) | A1 | |
| \(6x_1 + 3x_2 + 7x_3 \geq 1\) | A1 | |
| \(x_1, x_2, x_3 \geq 0\) | A1 | (7) |
# Question 7:
$$\begin{bmatrix}-4&5&1\\3&-1&-2\\-3&0&2\end{bmatrix} \to \text{add 5 to all entries} \to \begin{bmatrix}1&10&6\\8&4&3\\2&5&7\end{bmatrix}$$
| M1 | Adding $n\ (\geq 4)$ to all entries
Define variables: let $p_1, p_2, p_3$ be the probability that A plays rows 1, 2 and 3 respectively | B1 |
Maximise $P = V$ | B1 |
Subject to:
$V - p_1 - 8p_2 - 2p_3 \leq 0$ | M1, A1 |
$V - 10p_1 - 4p_2 - 5p_3 \leq 0$ | A1 |
$V - 6p_1 - 3p_2 - 7p_3 \leq 0$ | A1 |
$p_1 + p_2 + p_3 \leq 1$ | A1 |
$p_1, p_2, p_3 \geq 0$ | | (7)
**Or** (alternative formulation):
Let $x_i = \frac{p_i}{V}$, Minimise $P = x_1 + x_2 + x_3$ | B1, B1 |
Subject to:
$x_1 + 8x_2 + 2x_3 \geq 1$ | M1, A1 |
$10x_1 + 4x_2 + 5x_3 \geq 1$ | A1 |
$6x_1 + 3x_2 + 7x_3 \geq 1$ | A1 |
$x_1, x_2, x_3 \geq 0$ | A1 | (7)7. A two person zero-sum game is represented by the following pay-off matrix for player A.
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
& B plays 1 & B plays 2 & B plays 3 \\
\hline
A plays 1 & - 4 & 5 & 1 \\
\hline
A plays 2 & 3 & - 1 & - 2 \\
\hline
A plays 3 & - 3 & 0 & 2 \\
\hline
\end{tabular}
\end{center}
Formulate the game as a linear programming problem for player A. Write the constraints as inequalities and define your variables.
\hfill \mbox{\textit{Edexcel D2 2010 Q7 [7]}}