| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2023 |
| Session | June |
| Marks | 17 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | The Simplex Algorithm |
| Type | Game theory to LP |
| Difficulty | Challenging +1.8 This is a substantial Further Maths question requiring multiple sophisticated techniques: checking for saddle points, applying dominance arguments, formulating a game theory problem as an LP with slack variables, setting up a Simplex tableau, and working backwards from optimal solution to find opponent's strategy. While the individual steps are methodical, the multi-stage nature, the need to convert between game theory and LP frameworks, and the reverse-engineering in part (d) make this significantly harder than standard A-level questions. |
| 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 |
| \cline { 2 - 4 } \multicolumn{1}{c|}{} | Option X | Option Y | Option Z |
| Option Q | - 3 | 2 | 5 |
| Option R | 2 | - 1 | 0 |
| Option S | 4 | - 2 | - 1 |
| Option T | - 4 | 0 | 2 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Row minima are \(-3, -1, -2, -4\); Column maxima are \(4, 2, 5\) | M1 | Clear attempt to find row maximin and column minimax; either row minimums or column maximums correct, or at least five of seven values stated correctly |
| As Row maximin \((-1)\) is not equal to Column minimax \((2)\), i.e. \(-1 \neq 2\), the game is not stable | A1 | CAO dependent on all rowmins and colmaxs correct; states \(-1 \neq 2\); \(-1\) clearly identified as row maximin and \(2\) as column minimax |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Option Q dominates option T | B1 | Correct statement — must include word 'dominate' or exact equivalent |
| Because e.g. \(-3 > -4\), \(2 > 0\) and \(5 > 2\) | B1 | Correct inequalities — must be clear that all inequalities must hold |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Augment by \(+3\): \(\begin{pmatrix}-3&2&5\\2&-1&0\\4&-2&-1\end{pmatrix} \rightarrow \begin{pmatrix}0&5&8\\5&2&3\\7&1&2\end{pmatrix}\) | B1 | Correct augmentation — possibly implied by later working |
| Maximise \(P - V = 0\) where \(V\) is the value of the augmented game to A | B1 | Correct objective defined |
| \(V - 5p_2 - 7p_3 + r = 0\) | M1 | At least three equations in \(V, p_1, p_2, p_3\) and at least one dummy variable seen |
| \(V - 5p_1 - 2p_2 - p_3 + s = 0\) | ||
| \(V - 8p_1 - 3p_2 - 2p_3 + t = 0\) | A1 | CAO |
| \(p_1 + p_2 + p_3 + u = 1\) | B1 | Correct probability equation |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Initial Simplex tableau with correct rows: | M1 | Any two numerically correct rows |
| b.v. \ | \(V\) \ | \(p_1\) \ |
| \(r\) \ | \(1\) \ | \(0\) \ |
| \(s\) \ | \(1\) \ | \(-5\) \ |
| \(t\) \ | \(1\) \ | \(-8\) \ |
| \(u\) \ | \(0\) \ | \(1\) \ |
| \(P\) \ | \(-1\) \ | \(0\) \ |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(p_3 = \dfrac{5}{11}\) | B1 | \(p_3\) correctly stated |
| \(V \leqslant \dfrac{35}{11},\ V \leqslant \dfrac{35}{11},\ V \leqslant \dfrac{58}{11} \Rightarrow V = \dfrac{35}{11}\) | M1 | Attempt to find \(V\) by substituting probabilities into all three equations/inequalities involving \(V, p_1, p_2, p_3\) |
| Let Player B play option X with probability \(q_1\), option Y with probability \(q_2\) and option Z with probability \(q_3\) | B1 | Defining probabilities for Player B |
| \(5q_2 + 8q_3 = \dfrac{35}{11}\) | dM1 | Dependent on previous M mark; setting up at least three equations in \(q_1, q_2, q_3\) using their \(V\) |
| \(7q_1 + q_2 + 2q_3 = \dfrac{35}{11}\) | ||
| \(q_1 + q_2 + q_3 = 1\) | A1ft | Correct three equations (two if Option Z rejected) following through from augmented matrix |
| Player B should play option X with probability \(\dfrac{4}{11}\), option Y with probability \(\dfrac{7}{11}\) and never play option Z | A1 | Correct options for Player B in context; must state Player B should never play option Z; dependent on previous A mark |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(p_3 = \dfrac{5}{11}\) | B1 | \(p_3\) correctly stated |
| Recognises Option Y dominates Option Z; reduces to \(3\times2\) or \(2\times2\) matrix | M1 | Uses dominance argument; matrix may be transposed and signs changed |
| Define probability for B: play Option X with probability \(q\), Option Y with probability \((1-q)\) | B1 | Defining probabilities for Player B (condone use of \(p\) instead of \(q\)) |
| e.g. \(-3q + 2(1-q) \Rightarrow 2 - 5q\) and \(4q - 2(1-q) \Rightarrow 6q - 2\) | dM1 | Dependent on previous M; setting up at least two equations/expressions in \(q\) |
| \(2 - 5q = 6q - 2 \Rightarrow q = \dfrac{4}{11}\) | A1ft | Solves to obtain \(q\) |
| Player B should play option X with probability \(\dfrac{4}{11}\), option Y with probability \(\dfrac{7}{11}\) and never play option Z | A1 | Correct options in context; must state never play option Z |
# Question 8:
## Part 8(a):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Row minima are $-3, -1, -2, -4$; Column maxima are $4, 2, 5$ | M1 | Clear attempt to find row maximin and column minimax; either row minimums or column maximums correct, or at least five of seven values stated correctly |
| As Row maximin $(-1)$ is not equal to Column minimax $(2)$, i.e. $-1 \neq 2$, the game is not stable | A1 | CAO dependent on all rowmins and colmaxs correct; states $-1 \neq 2$; $-1$ clearly identified as row maximin and $2$ as column minimax |
## Part 8(b):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Option Q dominates option T | B1 | Correct statement — must include word 'dominate' or exact equivalent |
| Because e.g. $-3 > -4$, $2 > 0$ and $5 > 2$ | B1 | Correct inequalities — must be clear that all inequalities must hold |
## Part 8(c)(i):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Augment by $+3$: $\begin{pmatrix}-3&2&5\\2&-1&0\\4&-2&-1\end{pmatrix} \rightarrow \begin{pmatrix}0&5&8\\5&2&3\\7&1&2\end{pmatrix}$ | B1 | Correct augmentation — possibly implied by later working |
| Maximise $P - V = 0$ where $V$ is the value of the augmented game to A | B1 | Correct objective defined |
| $V - 5p_2 - 7p_3 + r = 0$ | M1 | At least three equations in $V, p_1, p_2, p_3$ and at least one dummy variable seen |
| $V - 5p_1 - 2p_2 - p_3 + s = 0$ | | |
| $V - 8p_1 - 3p_2 - 2p_3 + t = 0$ | A1 | CAO |
| $p_1 + p_2 + p_3 + u = 1$ | B1 | Correct probability equation |
## Part 8(c)(ii):
| Answer/Working | Mark | Guidance |
|---|---|---|
| Initial Simplex tableau with correct rows: | M1 | Any two numerically correct rows |
| b.v. \| $V$ \| $p_1$ \| $p_2$ \| $p_3$ \| $r$ \| $s$ \| $t$ \| $u$ \| Value | | |
| $r$ \| $1$ \| $0$ \| $-5$ \| $-7$ \| $1$ \| $0$ \| $0$ \| $0$ \| $0$ | | |
| $s$ \| $1$ \| $-5$ \| $-2$ \| $-1$ \| $0$ \| $1$ \| $0$ \| $0$ \| $0$ | | |
| $t$ \| $1$ \| $-8$ \| $-3$ \| $-2$ \| $0$ \| $0$ \| $1$ \| $0$ \| $0$ | | |
| $u$ \| $0$ \| $1$ \| $1$ \| $1$ \| $0$ \| $0$ \| $0$ \| $1$ \| $1$ | | |
| $P$ \| $-1$ \| $0$ \| $0$ \| $0$ \| $0$ \| $0$ \| $0$ \| $0$ \| $0$ | A1 | CAO including correct row and column labels |
## Part 8(d):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $p_3 = \dfrac{5}{11}$ | B1 | $p_3$ correctly stated |
| $V \leqslant \dfrac{35}{11},\ V \leqslant \dfrac{35}{11},\ V \leqslant \dfrac{58}{11} \Rightarrow V = \dfrac{35}{11}$ | M1 | Attempt to find $V$ by substituting probabilities into all three equations/inequalities involving $V, p_1, p_2, p_3$ |
| Let Player B play option X with probability $q_1$, option Y with probability $q_2$ and option Z with probability $q_3$ | B1 | Defining probabilities for Player B |
| $5q_2 + 8q_3 = \dfrac{35}{11}$ | dM1 | Dependent on previous M mark; setting up at least three equations in $q_1, q_2, q_3$ using their $V$ |
| $7q_1 + q_2 + 2q_3 = \dfrac{35}{11}$ | | |
| $q_1 + q_2 + q_3 = 1$ | A1ft | Correct three equations (two if Option Z rejected) following through from augmented matrix |
| Player B should play option X with probability $\dfrac{4}{11}$, option Y with probability $\dfrac{7}{11}$ and never play option Z | A1 | Correct options for Player B in context; must state Player B should never play option Z; dependent on previous A mark |
### Alternative for 8(d):
| Answer/Working | Mark | Guidance |
|---|---|---|
| $p_3 = \dfrac{5}{11}$ | B1 | $p_3$ correctly stated |
| Recognises Option Y dominates Option Z; reduces to $3\times2$ or $2\times2$ matrix | M1 | Uses dominance argument; matrix may be transposed and signs changed |
| Define probability for B: play Option X with probability $q$, Option Y with probability $(1-q)$ | B1 | Defining probabilities for Player B (condone use of $p$ instead of $q$) |
| e.g. $-3q + 2(1-q) \Rightarrow 2 - 5q$ and $4q - 2(1-q) \Rightarrow 6q - 2$ | dM1 | Dependent on previous M; setting up at least two equations/expressions in $q$ |
| $2 - 5q = 6q - 2 \Rightarrow q = \dfrac{4}{11}$ | A1ft | Solves to obtain $q$ |
| Player B should play option X with probability $\dfrac{4}{11}$, option Y with probability $\dfrac{7}{11}$ and never play option Z | A1 | Correct options in context; must state never play option Z |
The image appears to be essentially blank/white, containing only the Pearson Education Limited company registration footer at the bottom. There is no mark scheme content visible on this page to extract.
If you have additional pages from the mark scheme, please share those and I'll be happy to extract and format the content for you.
8. A two-person zero-sum game is represented by the pay-off matrix for player A shown below.
\section*{Player B}
Player A
\begin{center}
\begin{tabular}{ | c | c | c | c | }
\cline { 2 - 4 }
\multicolumn{1}{c|}{} & Option X & Option Y & Option Z \\
\hline
Option Q & - 3 & 2 & 5 \\
\hline
Option R & 2 & - 1 & 0 \\
\hline
Option S & 4 & - 2 & - 1 \\
\hline
Option T & - 4 & 0 & 2 \\
\hline
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Verify that there is no stable solution to this game.
\item Explain why player A should never play option T. 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 calculate the optimal values of $p _ { 1 } , p _ { 2 }$ and $p _ { 3 }$ using the Simplex algorithm.
\item \begin{enumerate}[label=(\roman*)]
\item Formulate the game as a linear programming problem for player A. You should write the constraints as equations.
\item Write down an initial Simplex tableau for this linear programming problem, making your variables clear.
The linear programming problem is solved using the Simplex algorithm. The optimal value of $p _ { 1 }$ is $\frac { 6 } { 11 }$ and the optimal value of $p _ { 2 }$ is 0
\end{enumerate}\item Find the best strategy for player B, defining any variables you use.
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2023 Q8 [17]}}