| Exam Board | Edexcel |
|---|---|
| Module | FD2 (Further Decision 2) |
| Year | 2024 |
| Session | June |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Challenging +1.2 This is a standard Further Maths D2 question on zero-sum game theory requiring LP formulation and Simplex method application. Part (a) is routine checking for saddle points, part (b) requires standard LP setup from game theory (a well-practiced technique), and part (c) involves reading off the solution from a given final tableau. While it requires knowledge of specialized D2 content and multiple steps, it follows textbook procedures without requiring novel insight or complex problem-solving. |
| Spec | 7.08a Pay-off matrix: zero-sum games7.08c Pure strategies: play-safe strategies and stable solutions7.08f Mixed strategies via LP: reformulate as linear programming problem |
| \multirow{2}{*}{} | Player B | |||
| Option X | Option Y | Option Z | ||
| \multirow{3}{*}{Player A} | Option R | 3 | 2 | -3 |
| Option S | 4 | -2 | 1 | |
| Option T | -1 | 3 | 6 | |
| b.v. | \(V\) | \(p _ { 1 }\) | \(p _ { 2 }\) | \(p _ { 3 }\) | r | \(s\) | \(t\) | \(u\) | Value |
| \(p _ { 3 }\) | 0 | 0 | 0 | 1 | \(\frac { 1 } { 10 }\) | \(- \frac { 3 } { 80 }\) | \(- \frac { 1 } { 16 }\) | \(\frac { 33 } { 80 }\) | \(\frac { 33 } { 80 }\) |
| \(p _ { 2 }\) | 0 | 0 | 1 | 0 | \(- \frac { 1 } { 10 }\) | \(\frac { 13 } { 80 }\) | \(- \frac { 1 } { 16 }\) | \(\frac { 17 } { 80 }\) | \(\frac { 17 } { 80 }\) |
| V | 1 | 0 | 0 | 0 | \(\frac { 1 } { 2 }\) | \(\frac { 5 } { 16 }\) | \(\frac { 3 } { 16 }\) | \(\frac { 73 } { 16 }\) | \(\frac { 73 } { 16 }\) |
| \(p _ { 1 }\) | 0 | 1 | 0 | 0 | 0 | \(- \frac { 1 } { 8 }\) | \(\frac { 1 } { 8 }\) | \(\frac { 3 } { 8 }\) | \(\frac { 3 } { 8 }\) |
| \(P\) | 0 | 0 | 0 | 0 | \(\frac { 1 } { 2 }\) | \(\frac { 5 } { 16 }\) | \(\frac { 3 } { 16 }\) | \(\frac { 73 } { 16 }\) | \(\frac { 73 } { 16 }\) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| Row minima: \(-3, -2, -1\) (max is \(-1\)); Column maxima: \(4, 3, 6\) (min is \(3\)) | M1 | Attempt row minima and column maxima; condone one error |
| Row maximin \((-1) \neq\) Column minimax \((3)\), so not stable | A1 | Correct reasoning; dependent on correct row maximin and column minimax |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(\begin{pmatrix}3&2&-3\\4&-2&1\\-1&3&6\end{pmatrix} \rightarrow \begin{pmatrix}6&5&0\\7&1&4\\2&6&9\end{pmatrix}\) | B1 | Correct augmentation; possibly implied by later tableau work |
| \(V - 6p_1 - 7p_2 - 2p_3 + r = 0\) \(V - 5p_1 - p_2 - 6p_3 + s = 0\) \(V - 4p_2 - 9p_3 + t = 0\) \(p_1 + p_2 + p_3 + u = 1\) \((P - V = 0)\) | M1 | At least three equations in \(V, p_1, p_2, p_3\) with at least one dummy variable |
| All four equations correct | A1 | Possibly implied by correct tableau |
| Any two numerical rows of tableau correct (ignore b.v. column labelling) | M1 | |
| Correct initial tableau: \(r,s,t\) rows with values \(-6,-7,-2\); \(-5,-1,-6\); \(0,-4,-9\); \(u\) row \(1,1,1,1\); \(P\) row \(-1,0,0,0\) | A1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| A should play R with probability \(\frac{3}{8}\), S with probability \(\frac{17}{80}\), T with probability \(\frac{33}{80}\) | B1 | Correct optimal strategy in context; dependent on both M marks in (b) |
| Value of game to player A is \(\frac{73}{16} - 3\) | M1 | For \(\pm\left(\frac{73}{16} \pm 3\right)\) |
| Value of game to player B is \(-\frac{25}{16}\) | A1 | CAO |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Mark | Guidance |
| \(6q_1 + 5q_2 = 4.5625\), \(7q_1 + q_2 + 4q_3 = 4.5625\), \(2q_1 + 6q_2 + 9q_3 = 4.5625\), \(q_1+q_2+q_3=1\) or equivalent set using RHS \(1.5625\) | M1 | Attempt at least three equations in \(q_1,q_2,q_3\) using value of game from (c) |
| CAO for any three of the four correct equations | A1 | |
| B plays X with probability \(\frac{1}{2}\), Y with probability \(\frac{5}{16}\), Z with probability \(\frac{3}{16}\) | A1 | CAO in context; must have at least three correct equations |
## Question 7:
**(a)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| Row minima: $-3, -2, -1$ (max is $-1$); Column maxima: $4, 3, 6$ (min is $3$) | M1 | Attempt row minima and column maxima; condone one error |
| Row maximin $(-1) \neq$ Column minimax $(3)$, so not stable | A1 | Correct reasoning; dependent on correct row maximin and column minimax |
**(b)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| $\begin{pmatrix}3&2&-3\\4&-2&1\\-1&3&6\end{pmatrix} \rightarrow \begin{pmatrix}6&5&0\\7&1&4\\2&6&9\end{pmatrix}$ | B1 | Correct augmentation; possibly implied by later tableau work |
| $V - 6p_1 - 7p_2 - 2p_3 + r = 0$ $V - 5p_1 - p_2 - 6p_3 + s = 0$ $V - 4p_2 - 9p_3 + t = 0$ $p_1 + p_2 + p_3 + u = 1$ $(P - V = 0)$ | M1 | At least three equations in $V, p_1, p_2, p_3$ with at least one dummy variable |
| All four equations correct | A1 | Possibly implied by correct tableau |
| Any two numerical rows of tableau correct (ignore b.v. column labelling) | M1 | |
| Correct initial tableau: $r,s,t$ rows with values $-6,-7,-2$; $-5,-1,-6$; $0,-4,-9$; $u$ row $1,1,1,1$; $P$ row $-1,0,0,0$ | A1 | CAO |
**(c)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| A should play R with probability $\frac{3}{8}$, S with probability $\frac{17}{80}$, T with probability $\frac{33}{80}$ | B1 | Correct optimal strategy in context; dependent on both M marks in (b) |
| Value of game to player A is $\frac{73}{16} - 3$ | M1 | For $\pm\left(\frac{73}{16} \pm 3\right)$ |
| Value of game to player B is $-\frac{25}{16}$ | A1 | CAO |
**(d)**
| Answer/Working | Mark | Guidance |
|---|---|---|
| $6q_1 + 5q_2 = 4.5625$, $7q_1 + q_2 + 4q_3 = 4.5625$, $2q_1 + 6q_2 + 9q_3 = 4.5625$, $q_1+q_2+q_3=1$ or equivalent set using RHS $1.5625$ | M1 | Attempt at least three equations in $q_1,q_2,q_3$ using value of game from (c) |
| CAO for any three of the four correct equations | A1 | |
| B plays X with probability $\frac{1}{2}$, Y with probability $\frac{5}{16}$, Z with probability $\frac{3}{16}$ | A1 | CAO in context; must have at least three correct equations |
---7.
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
\multicolumn{2}{|c|}{\multirow{2}{*}{}} & \multicolumn{3}{|c|}{Player B} \\
\hline
& & Option X & Option Y & Option Z \\
\hline
\multirow{3}{*}{Player A} & Option R & 3 & 2 & -3 \\
\hline
& Option S & 4 & -2 & 1 \\
\hline
& Option T & -1 & 3 & 6 \\
\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 Verify that there is no stable solution to this game.
Player A intends to make a random choice between options $\mathrm { R } , \mathrm { S }$ and T , choosing option R with probability $p _ { 1 }$, option S 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 objective function for the corresponding linear programme.
$$\text { Maximise } P = V \quad \text { where } V = \text { the value of the game } + 3$$
\item Determine an initial Simplex tableau, making your variables and working clear.
After several iterations of the Simplex algorithm, a possible final tableau is
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}
\hline
b.v. & $V$ & $p _ { 1 }$ & $p _ { 2 }$ & $p _ { 3 }$ & r & $s$ & $t$ & $u$ & Value \\
\hline
$p _ { 3 }$ & 0 & 0 & 0 & 1 & $\frac { 1 } { 10 }$ & $- \frac { 3 } { 80 }$ & $- \frac { 1 } { 16 }$ & $\frac { 33 } { 80 }$ & $\frac { 33 } { 80 }$ \\
\hline
$p _ { 2 }$ & 0 & 0 & 1 & 0 & $- \frac { 1 } { 10 }$ & $\frac { 13 } { 80 }$ & $- \frac { 1 } { 16 }$ & $\frac { 17 } { 80 }$ & $\frac { 17 } { 80 }$ \\
\hline
V & 1 & 0 & 0 & 0 & $\frac { 1 } { 2 }$ & $\frac { 5 } { 16 }$ & $\frac { 3 } { 16 }$ & $\frac { 73 } { 16 }$ & $\frac { 73 } { 16 }$ \\
\hline
$p _ { 1 }$ & 0 & 1 & 0 & 0 & 0 & $- \frac { 1 } { 8 }$ & $\frac { 1 } { 8 }$ & $\frac { 3 } { 8 }$ & $\frac { 3 } { 8 }$ \\
\hline
$P$ & 0 & 0 & 0 & 0 & $\frac { 1 } { 2 }$ & $\frac { 5 } { 16 }$ & $\frac { 3 } { 16 }$ & $\frac { 73 } { 16 }$ & $\frac { 73 } { 16 }$ \\
\hline
\end{tabular}
\end{center}
\item \begin{enumerate}[label=(\roman*)]
\item State the best strategy for player A.
\item Calculate the value of the game for player B.
Player B intends to make a random choice between options $\mathrm { X } , \mathrm { Y }$ and Z .
\end{enumerate}\item Determine the best strategy for player B, making your method and working clear.\\
(3)
\end{enumerate}
\hfill \mbox{\textit{Edexcel FD2 2024 Q7 [13]}}