| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2018 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Moderate -0.8 This is a standard textbook exercise in D2 game theory requiring routine application of well-defined algorithms: finding play-safe strategies (row minima/column maxima), checking for saddle points, applying dominance rules, and converting to LP form using the standard template. All steps are mechanical with no novel problem-solving required, making it easier than average A-level maths. |
| Spec | 7.08a Pay-off matrix: zero-sum games7.08b Dominance: reduce pay-off matrix7.08c Pure strategies: play-safe strategies and stable solutions7.08f Mixed strategies via LP: reformulate as linear programming problem |
| B plays 1 | B plays 2 | B plays 3 | B plays 4 | |
| A plays 1 | -3 | 2 | 5 | -1 |
| A plays 2 | -5 | 3 | 1 | -1 |
| A plays 3 | -2 | 5 | 4 | 2 |
| A plays 4 | 2 | -3 | -1 | 4 |
| - 3 | 2 | 5 |
| - 2 | 5 | 4 |
| 2 | - 3 | - 1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| A's play-safe strategy: find row minima: A1:\(-3\), A2:\(-5\), A3:\(-2\), A4:\(-3\); maximin \(= -2\), so A plays 3 | M1 | Method of finding row minima and maximising |
| B's play-safe strategy: find column maxima: B1:\(2\), B2:\(5\), B3:\(5\), B4:\(4\); minimax \(= 2\), so B plays 1 | A1 | |
| Both strategies correctly stated | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| No stable solution because maximin \((-2) \neq\) minimax \((2)\) | B1 | Must state reason with values |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Column B4 is dominated by column B1 (every entry in B1 \(\leq\) every entry in B4), so B4 is removed | B1 | |
| Row A2 is dominated by row A1 or A3, so A2 is removed | B1 | Must correctly identify which row/column is dominated with reason |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Let \(p_1, p_2, p_3\) be the probabilities that A plays 1, 2, 3 respectively | B1 | Variables defined |
| \(p_1 + p_2 + p_3 = 1\), \(p_1, p_2, p_3 \geq 0\) | B1 | |
| Maximise \(V\) subject to: | M1 | Correct structure |
| \(-3p_1 - 2p_2 + 2p_3 \geq V\) | A1 | |
| \(2p_1 + 5p_2 - 3p_3 \geq V\) | A1 | |
| \(5p_1 + 4p_2 - p_3 \geq V\) | A1 | |
| All constraints correct with normalisation | A1 |
# Question 2:
## Part (a)
| Answer | Mark | Guidance |
|--------|------|----------|
| A's play-safe strategy: find row minima: A1:$-3$, A2:$-5$, A3:$-2$, A4:$-3$; maximin $= -2$, so A plays 3 | M1 | Method of finding row minima and maximising |
| B's play-safe strategy: find column maxima: B1:$2$, B2:$5$, B3:$5$, B4:$4$; minimax $= 2$, so B plays 1 | A1 | |
| Both strategies correctly stated | A1 | |
## Part (b)
| Answer | Mark | Guidance |
|--------|------|----------|
| No stable solution because maximin $(-2) \neq$ minimax $(2)$ | B1 | Must state reason with values |
## Part (c)
| Answer | Mark | Guidance |
|--------|------|----------|
| Column B4 is dominated by column B1 (every entry in B1 $\leq$ every entry in B4), so B4 is removed | B1 | |
| Row A2 is dominated by row A1 or A3, so A2 is removed | B1 | Must correctly identify which row/column is dominated with reason |
## Part (d)
| Answer | Mark | Guidance |
|--------|------|----------|
| Let $p_1, p_2, p_3$ be the probabilities that A plays 1, 2, 3 respectively | B1 | Variables defined |
| $p_1 + p_2 + p_3 = 1$, $p_1, p_2, p_3 \geq 0$ | B1 | |
| Maximise $V$ subject to: | M1 | Correct structure |
| $-3p_1 - 2p_2 + 2p_3 \geq V$ | A1 | |
| $2p_1 + 5p_2 - 3p_3 \geq V$ | A1 | |
| $5p_1 + 4p_2 - p_3 \geq V$ | A1 | |
| All constraints correct with normalisation | A1 | |
---
2. A two-person zero-sum game is represented by the following pay-off matrix for player A.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
& B plays 1 & B plays 2 & B plays 3 & B plays 4 \\
\hline
A plays 1 & -3 & 2 & 5 & -1 \\
\hline
A plays 2 & -5 & 3 & 1 & -1 \\
\hline
A plays 3 & -2 & 5 & 4 & 2 \\
\hline
A plays 4 & 2 & -3 & -1 & 4 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Identify the play safe strategies for each player.
\item State, giving a reason, whether there is a stable solution to this game.
\item Explain why the game above can be reduced to the following $3 \times 3$ game.
\begin{center}
\begin{tabular}{ | c | c | c | }
\hline
- 3 & 2 & 5 \\
\hline
- 2 & 5 & 4 \\
\hline
2 & - 3 & - 1 \\
\hline
\end{tabular}
\end{center}
\item Formulate the $3 \times 3$ game as a linear programming problem for player A, defining your variables clearly and writing the constraints as inequalities.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2018 Q2 [13]}}