| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2022 |
| Session | June |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Challenging +1.8 This is a multi-part Further Maths question on zero-sum game theory requiring play-safe strategy identification, LP formulation, and working backwards from optimal solution. While systematic, it demands understanding of minimax principles, LP duality, and algebraic manipulation across 5 parts with 13+ marks, placing it well above average difficulty but below proof-heavy or highly novel problems. |
| Spec | 7.08a Pay-off matrix: zero-sum games7.08b Dominance: reduce pay-off matrix7.08c Pure strategies: play-safe strategies and stable solutions7.08d Nash equilibrium: identification and interpretation7.08e Mixed strategies: optimal strategy using equations or graphical method7.08f Mixed strategies via LP: reformulate as linear programming problem |
| \multirow{2}{*}{} | Player B | ||||
| Option W | Option X | Option Y | Option Z | ||
| \multirow{3}{*}{Player A} | Option Q | 4 | 3 | -1 | -2 |
| Option R | -3 | 5 | -4 | \(k\) | |
| Option S | -1 | 6 | 3 | -3 | |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Row minima are \(-2\), \(\min(k,-4)\) and \(-3\) | M1 | Attempt to calculate row minima; condone \(k\) or \(-4\) for \(\min(k,-4)\) |
| Play safe for Player A is always option Q, since \(-2\) is greater than \(-4\) and \(-3\); if row minimum for R is \(k\) then \(-4 > k\) so play safe still Q | A1 | Correct argument/conditions |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Column maxima are \(4, 6, 3\) and \(\max(k,-2)\) | B1 | Attempt to calculate column maxima; condone \(k\) or \(-2\) for \(\max(k,-2)\) |
| Play safe is option Z, \(k < 3\) or \(k \leq 2\) | B1 | CAO; ignore lower limit figure if given |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Option Y dominates option X | B1 | Must include word 'dominate'; also e.g. option Z dominates option X |
| Because \(-1 < 3\), \(-4 < 5\) and \(3 < 6\) | B1 | Correct inequalities — must be clear all three hold |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Augmented matrix: \(\begin{pmatrix} 8 & 3 & 2 \\ 1 & 0 & k+4 \\ 3 & 7 & 1 \end{pmatrix}\) | B1 | Correct augmentation; possibly implied by later working; X column may be included |
| \(V - 8p_1 - p_2 - 3p_3 + r = 0\) \(V - 3p_1 - 7p_3 + s = 0\) \(V - 2p_1 - (k+4)p_2 - p_3 + t = 0\) | M1 A1 | M1: at least three equations in \(V, p_1, p_2, p_3\) with at least one dummy variable; A1: CAO |
| \(p_1 + p_2 + p_3 + u = 1\) | B1 | Correct probability equation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Correct row and column labels for Simplex tableau | B1 | |
| Initial Simplex tableau with correct entries: b.v. \(V\), \(p_1\), \(p_2\), \(p_3\), \(r\), \(s\), \(t\), \(u\), Value; rows for \(r,s,t,u,P\) as shown | M1 | Any one numerical row correct |
| CAO for full tableau | A1 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(p_3 = \dfrac{13}{37}\) | B1 | \(p_3\) correctly stated |
| \(V - 8\!\left(\dfrac{7}{37}\right) - \left(\dfrac{17}{37}\right) - 3\!\left(\dfrac{13}{37}\right) + 0 = 0\) or \(V - 3\!\left(\dfrac{7}{37}\right) - 7\!\left(\dfrac{13}{37}\right) + 0 = 0\) | M1 | Attempt to calculate \(V\) using either equation from (d) not involving \(k\) |
| \(V = \dfrac{112}{37}\), then \(\dfrac{112}{37} - 2\!\left(\dfrac{7}{37}\right) - (k+4)\!\left(\dfrac{17}{37}\right) - \left(\dfrac{13}{37}\right) + 0 = 0\) | dM1 | Dependent on previous M; uses equation in \(k\) with their \(V\) to find \(k\) |
| \(k = 1\) | A1 | CAO |
# Question 7(a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Row minima are $-2$, $\min(k,-4)$ and $-3$ | M1 | Attempt to calculate row minima; condone $k$ or $-4$ for $\min(k,-4)$ |
| Play safe for Player A is always option Q, since $-2$ is greater than $-4$ and $-3$; if row minimum for R is $k$ then $-4 > k$ so play safe still Q | A1 | Correct argument/conditions |
---
# Question 7(b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Column maxima are $4, 6, 3$ and $\max(k,-2)$ | B1 | Attempt to calculate column maxima; condone $k$ or $-2$ for $\max(k,-2)$ |
| Play safe is option Z, $k < 3$ or $k \leq 2$ | B1 | CAO; ignore lower limit figure if given |
---
# Question 7(c):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Option Y dominates option X | B1 | Must include word 'dominate'; also e.g. option Z dominates option X |
| Because $-1 < 3$, $-4 < 5$ and $3 < 6$ | B1 | Correct inequalities — must be clear all three hold |
---
# Question 7(d)(i):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Augmented matrix: $\begin{pmatrix} 8 & 3 & 2 \\ 1 & 0 & k+4 \\ 3 & 7 & 1 \end{pmatrix}$ | B1 | Correct augmentation; possibly implied by later working; X column may be included |
| $V - 8p_1 - p_2 - 3p_3 + r = 0$ $V - 3p_1 - 7p_3 + s = 0$ $V - 2p_1 - (k+4)p_2 - p_3 + t = 0$ | M1 A1 | M1: at least three equations in $V, p_1, p_2, p_3$ with at least one dummy variable; A1: CAO |
| $p_1 + p_2 + p_3 + u = 1$ | B1 | Correct probability equation |
---
# Question 7(d)(ii):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Correct row and column labels for Simplex tableau | B1 | |
| Initial Simplex tableau with correct entries: b.v. $V$, $p_1$, $p_2$, $p_3$, $r$, $s$, $t$, $u$, Value; rows for $r,s,t,u,P$ as shown | M1 | Any one numerical row correct |
| CAO for full tableau | A1 | |
---
# Question 7(e):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $p_3 = \dfrac{13}{37}$ | B1 | $p_3$ correctly stated |
| $V - 8\!\left(\dfrac{7}{37}\right) - \left(\dfrac{17}{37}\right) - 3\!\left(\dfrac{13}{37}\right) + 0 = 0$ or $V - 3\!\left(\dfrac{7}{37}\right) - 7\!\left(\dfrac{13}{37}\right) + 0 = 0$ | M1 | Attempt to calculate $V$ using either equation from (d) not involving $k$ |
| $V = \dfrac{112}{37}$, then $\dfrac{112}{37} - 2\!\left(\dfrac{7}{37}\right) - (k+4)\!\left(\dfrac{17}{37}\right) - \left(\dfrac{13}{37}\right) + 0 = 0$ | dM1 | Dependent on previous M; uses equation in $k$ with their $V$ to find $k$ |
| $k = 1$ | A1 | CAO |
7.
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
\multicolumn{2}{|c|}{\multirow{2}{*}{}} & \multicolumn{4}{|c|}{Player B} \\
\hline
& & Option W & Option X & Option Y & Option Z \\
\hline
\multirow{3}{*}{Player A} & Option Q & 4 & 3 & -1 & -2 \\
\hline
& Option R & -3 & 5 & -4 & $k$ \\
\hline
& Option S & -1 & 6 & 3 & -3 \\
\hline
\end{tabular}
\end{center}
A two person zero-sum game is represented by the pay-off matrix for player A shown above. It is given that $k$ is an integer.
\begin{enumerate}[label=(\alph*)]
\item Show that Q is the play-safe option for player A regardless of the value of $k$.
Given that Z is the play-safe option for player B ,
\item determine the range of possible values of $k$. You must make your working clear.
\item Explain why player B should never play option X. You must make your reasoning clear.
Player A intends to make a random choice between options $\mathrm { Q } , \mathrm { R }$ and S , choosing option Q with probability $p _ { 1 }$, option R with probability $p _ { 2 }$ and option S with probability $p _ { 3 }$
Player A wants to find the optimal values of $p _ { 1 } , p _ { 2 }$ and $p _ { 3 }$ using the Simplex algorithm.\\
Given that $k > - 4$, player A formulates the following objective function for the corresponding linear program.
$$\text { Maximise } P = V \text {, where } V = \text { the value of the original game } + 4$$
\item \begin{enumerate}[label=(\roman*)]
\item Formulate the constraints of the linear programming problem for player A. You should write the constraints as equations.
\item Write down an initial Simplex tableau, making your variables clear.
The Simplex algorithm is used to solve the linear programming problem. It is given that in the final Simplex tableau the optimal value of $p _ { 1 } = \frac { 7 } { 37 }$, the optimal value of $p _ { 2 } = \frac { 17 } { 37 }$ and all the slack variables are zero.
\end{enumerate}\item Determine the value of $k$, making your method clear.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2022 Q7 [17]}}