| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2007 |
| Session | June |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Standard +0.8 This requires understanding zero-sum game theory, converting a pay-off matrix to LP form from the minimizing player's perspective, handling sign conventions correctly, and writing multiple constraints with proper variable definitions. While systematic once learned, it demands conceptual understanding beyond routine calculation and is a multi-step formulation problem rather than simple recall. |
| Spec | 7.08f Mixed strategies via LP: reformulate as linear programming problem |
| R plays 1 | R plays 2 | R plays 3 | |
| A plays 1 | 6 | - 2 | - 3 |
| A plays 2 | - 3 | 1 | 2 |
| A plays 3 | 5 | 4 | - 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Game from R's point of view; Add 7 to all entries | B1, B1 | |
| Resulting matrix: \(R_1: 1,10,2\); \(R_2: 9,6,3\); \(R_3: 10,5,8\) | ||
| Let R play 1 with probability \(P_1\), 2 with probability \(P_2\), 3 with probability \(P_3\); \(V=\) value of game | B1 | |
| Maximise \(P = V\) | B1 | |
| Subject to: \(V - P_1 - 9P_2 - 10P_3 \leq 0\); \(V - 10P_1 - 6P_2 - 5P_3 \leq 0\); \(V - 2P_1 - 3P_2 - 8P_3 \leq 0\) | M1A1ft, A1ft, A1ft | |
| \(P_1 + P_2 + P_3 \leq 1\) (accept \(=\)); \(V, P_1, P_2, P_3 \geq 0\) | A1 | 8 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Marks | Guidance |
| Add 4 to all entries | B1 | |
| Let R play 1 with probability \(P_1\), 2 with probability \(P_2\), 3 with probability \(P_3\); let \(V=\) value of game | B1 | |
| Let \(x_1 = \frac{P_1}{V},\ x_2 = \frac{P_2}{V},\ x_3 = \frac{P_3}{V}\) | B1 | |
| Maximise \(P = x_1 + x_2 + x_3\) | B1 | |
| Subject to: \(10x_1 + 2x_2 + x_3 \leq 1\) | M1A1ft | |
| \(x_1 + 5x_2 + 6x_3 \leq 1\) | A1ft | |
| \(9x_1 + 8x_2 + 3x_3 \leq 1\) | A1 | |
| \(x_1, x_2, x_3 \geq 0\) (accept \(P_i \geq 0\)) | 8 |
# Question 6:
## Alt 1
| Answer | Marks | Guidance |
|--------|-------|----------|
| Game from R's point of view; Add 7 to all entries | B1, B1 | |
| Resulting matrix: $R_1: 1,10,2$; $R_2: 9,6,3$; $R_3: 10,5,8$ | | |
| Let R play 1 with probability $P_1$, 2 with probability $P_2$, 3 with probability $P_3$; $V=$ value of game | B1 | |
| Maximise $P = V$ | B1 | |
| Subject to: $V - P_1 - 9P_2 - 10P_3 \leq 0$; $V - 10P_1 - 6P_2 - 5P_3 \leq 0$; $V - 2P_1 - 3P_2 - 8P_3 \leq 0$ | M1A1ft, A1ft, A1ft | |
| $P_1 + P_2 + P_3 \leq 1$ (accept $=$); $V, P_1, P_2, P_3 \geq 0$ | A1 | 8 |
## Alt 2
| Answer | Marks | Guidance |
|--------|-------|----------|
| Add 4 to all entries | B1 | |
| Let R play 1 with probability $P_1$, 2 with probability $P_2$, 3 with probability $P_3$; let $V=$ value of game | B1 | |
| Let $x_1 = \frac{P_1}{V},\ x_2 = \frac{P_2}{V},\ x_3 = \frac{P_3}{V}$ | B1 | |
| Maximise $P = x_1 + x_2 + x_3$ | B1 | |
| Subject to: $10x_1 + 2x_2 + x_3 \leq 1$ | M1A1ft | |
| $x_1 + 5x_2 + 6x_3 \leq 1$ | A1ft | |
| $9x_1 + 8x_2 + 3x_3 \leq 1$ | A1 | |
| $x_1, x_2, x_3 \geq 0$ (accept $P_i \geq 0$) | | 8 |
---6. Anna (A) and Roland (R) play a two-person zero-sum game which is represented by the following pay-off matrix for Anna.
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\hline
& R plays 1 & R plays 2 & R plays 3 \\
\hline
A plays 1 & 6 & - 2 & - 3 \\
\hline
A plays 2 & - 3 & 1 & 2 \\
\hline
A plays 3 & 5 & 4 & - 1 \\
\hline
\end{tabular}
\end{center}
Formulate the game as a linear programming problem for player $\mathbf { R }$. Write the constraints as inequalities. Define your variables clearly.\\
(Total 8 marks)\\
\hfill \mbox{\textit{Edexcel D2 2007 Q6 [8]}}