| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2019 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Standard +0.3 This is a standard D2 game theory question requiring routine application of play-safe strategies (finding row minima and column maxima), checking for saddle points, and converting to LP form using textbook methods. While multi-part, each step follows algorithmic procedures taught directly in the specification with no novel insight required. |
| 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 |
| Stephen plays 1 | Stephen plays 2 | Stephen plays 3 | |
| Eugene plays 1 | 4 | 5 | 0 |
| Eugene plays 2 | -2 | 1 | 1 |
| Eugene plays 3 | -3 | -4 | 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Row minima: \(0, -2, -4\) — max is \(0\) | M1 | Clear attempt to find the Row maximin and Column minimax (either the Row minimums or Column maximums correct or at least four (of the six) values stated correctly) |
| Column maxima: \(4, 5, 3\) — min is \(3\) | A1 | Correct Row maximin and Column minimax (dependent on all row mins and column maxs correct) |
| Play safe for Eugene is \(1\) and for Stephen is \(3\) | A1 | Correct play safe for E (1) and S (3) – not dependent on the previous A mark |
| Row maximin \((0) \neq\) Column minimax \((3)\) so not stable | A1 (4) | CAO – states \(0 \neq 3\) (or row maximin \(\neq\) col minimax) as long as 0 is clearly identified as the row maximin and 3 as the column minimax |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| If Stephen plays safe then Eugene should change from their play safe of option 1 to their option 3 as they will win more against Stephen's play-safe (3 rather than 0) | B1 (1) | CAO – must mention option 3 and either gain 3 or equivalent in words |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Reverses signs in pay-off matrix followed by add 5 to each element. Condone one error. | B1 | Making all terms non-negative (any addition \(\geq 5\) is acceptable) |
| Let \(p_1, p_2, p_3\) be the probability of (S) playing 1, 2 and 3 respectively (where \(p_1, p_2, p_3 \geq 0\)) | B1 | Defining probability variables |
| Let \(V =\) value of the game (to S) | B1 | Defining \(V\) |
| Maximise \((P=)\ V\) | B1 | 'maximise' + function/expression |
| Subject to: \(V - p_1 - 5p_3 + r = 0\) | M1 A1 | At least three (of the four) equations or inequalities in \(V\), \(p_1, p_2, p_3\) (with all \(p_i\) terms in the first three constraint equations having correct signs for the coefficients) – condone no slack variables for this mark. CAO - the three constraints involving \(V\) and \(p_i\) expressed as equations with slack variables |
| \(V - 7p_1 - 4p_2 - 4p_3 + s = 0\) | ||
| \(V - 8p_1 - 9p_2 - 2p_3 + t = 0\) | ||
| \(p_1 + p_2 + p_3 (+u) = 1\) | A1 (7) | Probability sum equation correct (allow presence of a slack variable in this equation) |
| \((r, s, t, u \geq 0)\) |
# Question 4:
## Part (a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Row minima: $0, -2, -4$ — max is $0$ | M1 | Clear attempt to find the Row maximin and Column minimax (either the Row minimums or Column maximums correct or at least four (of the six) values stated correctly) |
| Column maxima: $4, 5, 3$ — min is $3$ | A1 | Correct Row maximin and Column minimax (dependent on all row mins and column maxs correct) |
| Play safe for Eugene is $1$ and for Stephen is $3$ | A1 | Correct play safe for E (1) and S (3) – not dependent on the previous A mark |
| Row maximin $(0) \neq$ Column minimax $(3)$ so not stable | A1 **(4)** | CAO – states $0 \neq 3$ (or row maximin $\neq$ col minimax) as long as 0 is clearly identified as the row maximin and 3 as the column minimax |
## Part (b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| If Stephen plays safe then Eugene should change from their play safe of option 1 to their option 3 as they will win more against Stephen's play-safe (3 rather than 0) | B1 **(1)** | CAO – must mention option 3 and either gain 3 or equivalent in words |
## Part (c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Reverses signs in pay-off matrix followed by add 5 to each element. Condone one error. | B1 | Making all terms non-negative (any addition $\geq 5$ is acceptable) |
| Let $p_1, p_2, p_3$ be the probability of (S) playing 1, 2 and 3 respectively (where $p_1, p_2, p_3 \geq 0$) | B1 | Defining probability variables |
| Let $V =$ value of the game (to S) | B1 | Defining $V$ |
| Maximise $(P=)\ V$ | B1 | 'maximise' + function/expression |
| Subject to: $V - p_1 - 5p_3 + r = 0$ | M1 A1 | At least three (of the four) equations or inequalities in $V$, $p_1, p_2, p_3$ (with all $p_i$ terms in the first three constraint equations having correct signs for the coefficients) – condone no slack variables for this mark. CAO - the three constraints involving $V$ and $p_i$ expressed as equations with slack variables |
| $V - 7p_1 - 4p_2 - 4p_3 + s = 0$ | | |
| $V - 8p_1 - 9p_2 - 2p_3 + t = 0$ | | |
| $p_1 + p_2 + p_3 (+u) = 1$ | A1 **(7)** | Probability sum equation correct (allow presence of a slack variable in this equation) |
| $(r, s, t, u \geq 0)$ | | |
**Total: 12 marks**
---
4. Eugene and Stephen play a zero-sum game. The pay-off matrix shows the number of points that Eugene scores for each combination of strategies.
\begin{center}
\begin{tabular}{|l|l|l|l|}
\hline
& Stephen plays 1 & Stephen plays 2 & Stephen plays 3 \\
\hline
Eugene plays 1 & 4 & 5 & 0 \\
\hline
Eugene plays 2 & -2 & 1 & 1 \\
\hline
Eugene plays 3 & -3 & -4 & 3 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Find the play-safe strategies for each of Eugene and Stephen, and hence show that this zero-sum game does not have a stable solution.
\item Suppose that Eugene knows that Stephen will use his play-safe strategy. Explain why Eugene should change from his play-safe strategy. You should state as part of your answer which strategy Eugene should now play.
\item Formulate the game as a linear programming problem for Stephen. Define your variables clearly. Write the constraints as equations.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D2 2019 Q4 [12]}}