| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2020 |
| Session | June |
| Marks | 14 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Challenging +1.8 This is a sophisticated Further Maths question requiring understanding of game theory, LP formulation, and the Simplex algorithm. While the individual steps are methodical (dominance reduction, saddle point check, LP constraint interpretation), the conceptual leap to formulate a zero-sum game as an LP and explain why constraints represent player B's optimal responses requires significant mathematical maturity beyond standard A-level. The multi-part structure and need to interpret abstract game-theoretic concepts places this well above average difficulty. |
| Spec | 7.07a Simplex tableau: initial setup in standard format7.08a Pay-off matrix: zero-sum games7.08b Dominance: reduce pay-off matrix7.08e Mixed strategies: optimal strategy using equations or graphical method |
| \multirow{6}{*}{Player A} | Player B | |||
| \multirow[b]{2}{*}{Option Q} | Option X | Option Y | Option Z | |
| 1 | 5 | 3 | ||
| Option R | 4 | -3 | 1 | |
| Option S | 2 | -4 | -2 | |
| Option T | 3 | -2 | 0 | |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Option R (or option T) dominates option S | B1 | Correct statement – must include the word 'dominate' (note that T dominates S too) |
| Because e.g. \(4 > 2\) and \(-3 > -4\) and \(1 > -2\) | B1 | Correct inequalities – must be clear that all inequalities must hold |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| Row minima: \(1, -3, -2\); max is \(1\) | M1 | Attempt at row minima and column maxima – condone one error |
| Column maxima: \(4, 5, 3\); min is \(3\) | A1 | Correct max(row min) and min(col max) |
| Row maximin \((1) \neq\) Column minimax \((3)\) so not stable | A1 | Correct reasoning that game is not stable (accept \(1 \neq 3\) + statement) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(V\) is less than or equal to each of these three expressions since we need to find the maximum value of the worst possible augmented expected pay-off for each value of \(p\) | B1 | Understanding that for each value of \(p\) we are seeking the minimum possible output |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| It is necessary to use an inequality because it enables the Simplex algorithm to pivot on a row that will increase the value of \(P\) | B1 | As a minimum accept an answer that implies that an inequality is required so that we can apply the Simplex algorithm |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(p_2 = \dfrac{4}{11}\) | B1 | cao |
| Substitute \(p\) values to obtain \(V \leq \dfrac{56}{11}, \dfrac{56}{11}, \dfrac{58}{11}\) | M1 | Substitute their \(p\) values into all three expressions for the upper bound of \(V\) |
| Value of the game to player A \(= \dfrac{56}{11} - 3 = \dfrac{23}{11}\) | A1 | cao for the value of the game to player A |
| Answer | Marks | Guidance |
|---|---|---|
| Answer | Mark | Guidance |
| \(q_1 + 5q_2 + 3q_3 = \dfrac{23}{11}\) | M1 | Attempt to set up at least three equations in \(q_1, q_2, q_3\) using the value of the game from (e) |
| \(4q_1 - 3q_2 + q_3 = \dfrac{23}{11}\) | A1ft | Two correct ft "their" \(V\) |
| \(q_1 + q_2 + q_3 = 1\) | A1 | cao (for exactly three equations correct) |
| Player B should play option X with probability \(\dfrac{8}{11}\), option Y with probability \(\dfrac{3}{11}\) and never play option Z | A1 | cao in context |
# Question 6:
## Part (a):
| Answer | Mark | Guidance |
|--------|------|----------|
| Option R (or option T) dominates option S | B1 | Correct statement – must include the word 'dominate' (note that T dominates S too) |
| Because e.g. $4 > 2$ and $-3 > -4$ and $1 > -2$ | B1 | Correct inequalities – must be clear that all inequalities must hold |
## Part (b):
| Answer | Mark | Guidance |
|--------|------|----------|
| Row minima: $1, -3, -2$; max is $1$ | M1 | Attempt at row minima and column maxima – condone one error |
| Column maxima: $4, 5, 3$; min is $3$ | A1 | Correct max(row min) and min(col max) |
| Row maximin $(1) \neq$ Column minimax $(3)$ so not stable | A1 | Correct reasoning that game is not stable (accept $1 \neq 3$ + statement) |
## Part (c):
| Answer | Mark | Guidance |
|--------|------|----------|
| $V$ is less than or equal to each of these three expressions since we need to find the maximum value of the worst possible augmented expected pay-off for each value of $p$ | B1 | Understanding that for each value of $p$ we are seeking the minimum possible output |
## Part (d):
| Answer | Mark | Guidance |
|--------|------|----------|
| It is necessary to use an inequality because it enables the Simplex algorithm to pivot on a row that will increase the value of $P$ | B1 | As a minimum accept an answer that implies that an inequality is required so that we can apply the Simplex algorithm |
## Part (e):
| Answer | Mark | Guidance |
|--------|------|----------|
| $p_2 = \dfrac{4}{11}$ | B1 | cao |
| Substitute $p$ values to obtain $V \leq \dfrac{56}{11}, \dfrac{56}{11}, \dfrac{58}{11}$ | M1 | Substitute their $p$ values into all three expressions for the upper bound of $V$ |
| Value of the game to player A $= \dfrac{56}{11} - 3 = \dfrac{23}{11}$ | A1 | cao for the value of the game to player A |
## Part (f):
| Answer | Mark | Guidance |
|--------|------|----------|
| $q_1 + 5q_2 + 3q_3 = \dfrac{23}{11}$ | M1 | Attempt to set up at least three equations in $q_1, q_2, q_3$ using the value of the game from (e) |
| $4q_1 - 3q_2 + q_3 = \dfrac{23}{11}$ | A1ft | Two correct ft "their" $V$ |
| $q_1 + q_2 + q_3 = 1$ | A1 | cao (for exactly three equations correct) |
| Player B should play option X with probability $\dfrac{8}{11}$, option Y with probability $\dfrac{3}{11}$ and never play option Z | A1 | cao in context |
---6.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multirow{6}{*}{Player A} & \multicolumn{4}{|c|}{Player B} \\
\hline
& \multirow[b]{2}{*}{Option Q} & Option X & Option Y & Option Z \\
\hline
& & 1 & 5 & 3 \\
\hline
& Option R & 4 & -3 & 1 \\
\hline
& Option S & 2 & -4 & -2 \\
\hline
& Option T & 3 & -2 & 0 \\
\hline
\end{tabular}
\end{center}
A two person zero-sum game is represented by the pay-off matrix for player A, shown above.
\begin{enumerate}[label=(\alph*)]
\item Explain, with justification, why this matrix may be reduced to a $3 \times 3$ matrix by removing option S from player A's choices.
\item Verify that there is no stable solution to the reduced game.
Player A intends to make a random choice between options $\mathrm { Q } , \mathrm { R }$ and T , choosing option Q with probability $p _ { 1 }$, option R with probability $p _ { 2 }$ and option T with probability $p _ { 3 }$
Player A wants to find the optimal values of $p _ { 1 } , p _ { 2 }$ and $p _ { 3 }$ using the Simplex algorithm. Player A formulates the following linear programme, writing the constraints as inequalities.
Maximise $P = V$, where $V =$ the value of original game + 3
$$\begin{aligned}
\text { subject to } & V \leqslant 4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \\
& V \leqslant 8 p _ { 1 } + p _ { 3 } \\
& V \leqslant 6 p _ { 1 } + 4 p _ { 2 } + 3 p _ { 3 } \\
& p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 \\
& p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , V \geqslant 0
\end{aligned}$$
\item Explain why $V$ cannot exceed any of the following expressions
$$4 p _ { 1 } + 7 p _ { 2 } + 6 p _ { 3 } \quad 8 p _ { 1 } + p _ { 3 } \quad 6 p _ { 1 } + 4 p _ { 2 } + 3 p _ { 3 }$$
\item Explain why it is necessary to use the constraint $p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1$
The Simplex algorithm is used to solve the linear programming problem.\\
Given that the optimal value of $p _ { 1 } = \frac { 7 } { 11 }$ and the optimal value of $p _ { 3 } = 0$
\item calculate the value of the game to player A .\\
(3)
Player B intends to make a random choice between options $\mathrm { X } , \mathrm { Y }$ and Z , choosing option X with probability $q _ { 1 }$, option Y with probability $q _ { 2 }$ and option Z with probability $q _ { 3 }$
\item Determine the optimal strategy for player B, making your working clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2020 Q6 [14]}}