Edexcel D2 2019 June — Question 4 12 marks

Exam BoardEdexcel
ModuleD2 (Decision Mathematics 2)
Year2019
SessionJune
Marks12
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicDynamic Programming
TypeZero-sum game LP formulation
DifficultyStandard +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.
Spec7.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

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.
Stephen plays 1Stephen plays 2Stephen plays 3
Eugene plays 1450
Eugene plays 2-211
Eugene plays 3-3-43
  1. 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.
  2. 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.
  3. Formulate the game as a linear programming problem for Stephen. Define your variables clearly. Write the constraints as equations.

Question 4:
Part (a):
AnswerMarks Guidance
Answer/WorkingMark 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 stableA1 (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):
AnswerMarks Guidance
Answer/WorkingMark 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):
AnswerMarks Guidance
Answer/WorkingMark 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
# 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]}}