Edexcel FD2 2019 June — Question 4 14 marks

Exam BoardEdexcel
ModuleFD2 (Further Decision 2)
Year2019
SessionJune
Marks14
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicDynamic Programming
TypeZero-sum game LP formulation
DifficultyChallenging +1.2 This is a standard Further Maths game theory question requiring verification of no saddle point, identification of LP formulation errors (missing equality constraint p₁+p₂+p₃=1), setting up a simplex tableau, and calculating game value. While it involves multiple techniques, each step follows textbook procedures with no novel insight required. The LP error-spotting and multi-part structure elevate it slightly above average difficulty.
Spec7.08a Pay-off matrix: zero-sum games7.08e Mixed strategies: optimal strategy using equations or graphical method7.08f Mixed strategies via LP: reformulate as linear programming problem
4.
\multirow{2}{*}{}Player B
Option XOption YOption Z
\multirow{3}{*}{Player A}Option P3-20
Option Q-44-2
Option R12-1
A two person zero-sum game is represented by the pay-off matrix for player A shown above.
  1. Verify that there is no stable solution to this game. Player A intends to make a random choice between options \(\mathrm { P } , \mathrm { Q }\) and R , choosing option P with probability \(p _ { 1 }\), option Q with probability \(p _ { 2 }\) and option R 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 programming problem for the game, writing the constraints as inequalities. $$\begin{aligned} & \text { Maximise } P = V \\ & \text { subject to } V \geqslant 3 p _ { 1 } - 4 p _ { 2 } + p _ { 3 } \\ & \\ & V \geqslant - 2 p _ { 1 } + 4 p _ { 2 } + 2 p _ { 3 } \\ & V \geqslant - 2 p _ { 2 } - 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}$$
  2. Correct the errors made by player A in the linear programming formulation of the game, giving reasons for your answer.
  3. Write down an initial Simplex tableau for the corrected linear programming problem. The Simplex algorithm is used to solve the corrected linear programming problem. The optimal values are \(p _ { 1 } = 0.6 , p _ { 2 } = 0\) and \(p _ { 3 } = 0.4\)
  4. Calculate the value of the game to player A.
  5. Determine the optimal strategy for player B, making your reasoning clear.
Question 4:
Part (a)
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Row minima: \(-2,\ -4,\ -1\); max is \(-1\)1M1
Column maxima: \(3,\ 4,\ 0\); min is \(0\)
Row maximin \((-1)\neq\) Column minimax \((0)\) so not stable1A1
Part (b)
AnswerMarks Guidance
Answer/WorkingMarks Guidance
\(V\) must be non-negative so add at least 4 to each value, e.g. adding 5 gives \(\begin{pmatrix}8&3&5\\1&9&3\\6&7&4\end{pmatrix}\)1B1
\(V\) is minimum A can expect to win, so constraints are \(V\leq\ldots\)2B1
e.g. adding 5: \(V\leq 8p_1+p_2+6p_3\), \(V\leq 3p_1+9p_2+7p_3\), \(V\leq 5p_1+3p_2+4p_3\)3B1
Part (c)
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Initial tableau (adding 5): \(\begin{array}{cccccccccc} \text{b.v.}&V&p_1&p_2&p_3&r&s&t&u&\text{Value}\\ r&1&-8&-1&-6&1&0&0&0&0\\ s&1&-3&-9&-7&0&1&0&0&0\\ t&1&-5&-3&-4&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 \end{array}\) 1B1
Correct pivot selection/operation1M1
Correct updated tableau1A1
Part (d)
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Substitute \(p\) values to obtain \(V\leq 4.6\)1M1
Value of game to player \(A = 4.6-5=-0.4\)1A1
Part (e)
AnswerMarks Guidance
Answer/WorkingMarks Guidance
Player B's choices are options Y and Z only1B1
Either \(2q=0.4\) or \(-2q+1(1-q)=0.4\) where \(q\) = probability B plays Y and \((1-q)\) for Z1M1
\(q=0.2\)1A1
Player B should never play option X; play Y with probability \(0.2\) and Z with probability \(0.8\)2A1ft
Question 4 (Game Theory):
Part (a)
AnswerMarks Guidance
AnswerMarks Guidance
Attempt at row minima and column maxima1M1 Condone one error
Correct reasoning that game is not stable (accept "\(-1 \neq 0\)" + statement)1A1 Dependent on correct row minima and column maxima
Part (b)
AnswerMarks Guidance
AnswerMarks Guidance
Coefficients are incorrect because \(V\) must be non-negative1B1 Must convey both: coefficients incorrect AND \(V\) non-negative; condone 'positive' for 'non-negative'
Inequality signs are wrong way because \(V\) is the minimum (expected winnings \(\geq V\))2B1 Must convey both aspects
All three correct inequalities with slack variables3B1 CAO; only if 2B1 awarded
Part (c)
AnswerMarks Guidance
AnswerMarks Guidance
All row and column labels correct for Simplex tableau1B1
Setting up Simplex model — any two of r, s, t rows correct; or completely correct with one column/row missing1M1 Must follow from changed constraints of form \(V \leq ap_1 + bp_2 + cp_3\), \(a,b,c \geq 0\)
CAO on numerical values1A1
Part (d)
AnswerMarks Guidance
AnswerMarks Guidance
Substitutes \(p\) values into all three expressions for upper bound of \(V\)1M1 Condone use of equals sign; but not '\(V \geq \ldots\)'
\(V \leq 3(0.6)-4(0)+0.4 = 2.2\ \{=\frac{11}{5}\}\); \(V \leq -2(0.6)-4(0)+2(0.4)=-0.4\ \{=-\frac{2}{5}\}\); \(V \leq -2(0)-(0.4)=-0.4\ \{=-\frac{2}{5}\}\)
\(V \leq 8(0.6)+(0)+6(0.4)=7.2\ \{=\frac{36}{5}\}\); \(V \leq 3(0.6)+9(0)+7(0.4)=4.6\ \{=\frac{23}{5}\}\); \(V \leq 5(0.6)+3(0)+4(0.4)=4.6\ \{=\frac{23}{5}\}\)
\(V \leq 7(0.6)+5(0.4)=6.2\ \{=\frac{31}{5}\}\); \(V \leq 2(0.6)+8(0)+6(0.4)=3.6\ \{=\frac{18}{5}\}\); \(V \leq 4(0.6)+2(0)+3(0.4)=3.6\ \{=\frac{18}{5}\}\)
CAO for value of game to player A1A1
Part (e)
AnswerMarks Guidance
AnswerMarks Guidance
CAO — uses model to determine Player B only plays Y and Z1B1
A correct equation for B where value of game to \(B = -1 \times\) their value of game to A1M1
CAO for \(q\) (probability that B plays Y)1A1
Correct optimal strategy in context (not just in terms of \(q\)) following through their \(q\)2A1ft
Alternative for (e):
AnswerMarks Guidance
AnswerMarks Guidance
CAO — uses model to determine Player B only plays Y and Z1B1
Formulates two correct expressions for expected value of game to B and finds intersection: \(2q = -2q + 1(1-q)\ (= 1-3q)\)1M1
As above1A1
As above2A1ft 
# Question 4:

## Part (a)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Row minima: $-2,\ -4,\ -1$; max is $-1$ | 1M1 | |
| Column maxima: $3,\ 4,\ 0$; min is $0$ | | |
| Row maximin $(-1)\neq$ Column minimax $(0)$ so not stable | 1A1 | |

## Part (b)

| Answer/Working | Marks | Guidance |
|---|---|---|
| $V$ must be non-negative so add at least 4 to each value, e.g. adding 5 gives $\begin{pmatrix}8&3&5\\1&9&3\\6&7&4\end{pmatrix}$ | 1B1 | |
| $V$ is minimum A can expect to win, so constraints are $V\leq\ldots$ | 2B1 | |
| e.g. adding 5: $V\leq 8p_1+p_2+6p_3$, $V\leq 3p_1+9p_2+7p_3$, $V\leq 5p_1+3p_2+4p_3$ | 3B1 | |

## Part (c)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Initial tableau (adding 5): $\begin{array}{c|ccccccccc} \text{b.v.}&V&p_1&p_2&p_3&r&s&t&u&\text{Value}\\ r&1&-8&-1&-6&1&0&0&0&0\\ s&1&-3&-9&-7&0&1&0&0&0\\ t&1&-5&-3&-4&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 \end{array}$ | 1B1 | |
| Correct pivot selection/operation | 1M1 | |
| Correct updated tableau | 1A1 | |

## Part (d)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Substitute $p$ values to obtain $V\leq 4.6$ | 1M1 | |
| Value of game to player $A = 4.6-5=-0.4$ | 1A1 | |

## Part (e)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Player B's choices are options Y and Z only | 1B1 | |
| Either $2q=0.4$ or $-2q+1(1-q)=0.4$ where $q$ = probability B plays Y and $(1-q)$ for Z | 1M1 | |
| $q=0.2$ | 1A1 | |
| Player B should never play option X; play Y with probability $0.2$ and Z with probability $0.8$ | 2A1ft | |

# Question 4 (Game Theory):

## Part (a)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Attempt at row minima and column maxima | 1M1 | Condone one error |
| Correct reasoning that game is not stable (accept "$-1 \neq 0$" + statement) | 1A1 | Dependent on correct row minima and column maxima |

## Part (b)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Coefficients are incorrect because $V$ must be non-negative | 1B1 | Must convey both: coefficients incorrect AND $V$ non-negative; condone 'positive' for 'non-negative' |
| Inequality signs are wrong way because $V$ is the minimum (expected winnings $\geq V$) | 2B1 | Must convey both aspects |
| All three correct inequalities with slack variables | 3B1 | CAO; only if 2B1 awarded |

## Part (c)
| Answer | Marks | Guidance |
|--------|-------|----------|
| All row and column labels correct for Simplex tableau | 1B1 | |
| Setting up Simplex model — any two of r, s, t rows correct; or completely correct with one column/row missing | 1M1 | Must follow from changed constraints of form $V \leq ap_1 + bp_2 + cp_3$, $a,b,c \geq 0$ |
| CAO on numerical values | 1A1 | |

## Part (d)
| Answer | Marks | Guidance |
|--------|-------|----------|
| Substitutes $p$ values into all three expressions for upper bound of $V$ | 1M1 | Condone use of equals sign; but not '$V \geq \ldots$' |
| $V \leq 3(0.6)-4(0)+0.4 = 2.2\ \{=\frac{11}{5}\}$; $V \leq -2(0.6)-4(0)+2(0.4)=-0.4\ \{=-\frac{2}{5}\}$; $V \leq -2(0)-(0.4)=-0.4\ \{=-\frac{2}{5}\}$ | | |
| $V \leq 8(0.6)+(0)+6(0.4)=7.2\ \{=\frac{36}{5}\}$; $V \leq 3(0.6)+9(0)+7(0.4)=4.6\ \{=\frac{23}{5}\}$; $V \leq 5(0.6)+3(0)+4(0.4)=4.6\ \{=\frac{23}{5}\}$ | | |
| $V \leq 7(0.6)+5(0.4)=6.2\ \{=\frac{31}{5}\}$; $V \leq 2(0.6)+8(0)+6(0.4)=3.6\ \{=\frac{18}{5}\}$; $V \leq 4(0.6)+2(0)+3(0.4)=3.6\ \{=\frac{18}{5}\}$ | | |
| CAO for value of game to player A | 1A1 | |

## Part (e)
| Answer | Marks | Guidance |
|--------|-------|----------|
| CAO — uses model to determine Player B only plays Y and Z | 1B1 | |
| A correct equation for B where value of game to $B = -1 \times$ their value of game to A | 1M1 | |
| CAO for $q$ (probability that B plays Y) | 1A1 | |
| Correct optimal strategy in context (not just in terms of $q$) following through their $q$ | 2A1ft | |

**Alternative for (e):**
| Answer | Marks | Guidance |
|--------|-------|----------|
| CAO — uses model to determine Player B only plays Y and Z | 1B1 | |
| Formulates two correct expressions for expected value of game to B and finds intersection: $2q = -2q + 1(1-q)\ (= 1-3q)$ | 1M1 | |
| As above | 1A1 | |
| As above | 2A1ft | |

---
4.

\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 P & 3 & -2 & 0 \\
\hline
 & Option Q & -4 & 4 & -2 \\
\hline
 & Option R & 1 & 2 & -1 \\
\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 { P } , \mathrm { Q }$ and R , choosing option P with probability $p _ { 1 }$, option Q with probability $p _ { 2 }$ and option R 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 programming problem for the game, writing the constraints as inequalities.

$$\begin{aligned}
& \text { Maximise } P = V \\
& \text { subject to } V \geqslant 3 p _ { 1 } - 4 p _ { 2 } + p _ { 3 } \\
& \\
& V \geqslant - 2 p _ { 1 } + 4 p _ { 2 } + 2 p _ { 3 } \\
& V \geqslant - 2 p _ { 2 } - 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 Correct the errors made by player A in the linear programming formulation of the game, giving reasons for your answer.
\item Write down an initial Simplex tableau for the corrected linear programming problem.

The Simplex algorithm is used to solve the corrected linear programming problem.

The optimal values are $p _ { 1 } = 0.6 , p _ { 2 } = 0$ and $p _ { 3 } = 0.4$
\item Calculate the value of the game to player A.
\item Determine the optimal strategy for player B, making your reasoning clear.
\end{enumerate}

\hfill \mbox{\textit{Edexcel FD2 2019 Q4 [14]}}
This paper (6 questions)
View full paper
Q1 10 Q2 7 Q3 13 Q4 14 Q5 11 Q6 8