| Exam Board | Edexcel |
|---|---|
| Module | D2 (Decision Mathematics 2) |
| Year | 2006 |
| Session | June |
| Marks | 16 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Dynamic Programming |
| Type | Zero-sum game LP formulation |
| Difficulty | Standard +0.8 This is a standard D2 game theory question requiring LP formulation and simplex algorithm application. While it involves multiple steps (16 marks) and requires careful execution of the simplex method, it follows a well-established procedure taught directly in the syllabus. The conceptual difficulty is moderate—students must know the standard transformation of game theory to LP—but no novel insight is required. The mechanical nature of simplex iterations and the fact this is a textbook application places it above average but not exceptionally difficult. |
| Spec | 7.06f Integer programming: branch-and-bound method7.07a Simplex tableau: initial setup in standard format7.08a Pay-off matrix: zero-sum games7.08e Mixed strategies: optimal strategy using equations or graphical method |
| \(B\) plays 1 | \(B\) plays 2 | \(B\) plays 3 | |
| \(A\) plays 1 | 5 | 7 | 2 |
| \(A\) plays 2 | 3 | 8 | 4 |
| \(A\) plays 3 | 6 | 4 | 9 |
| Answer | Marks |
|---|---|
| \(P_i \geq 0\) and r, s, u are stack variables all \(\geq 0\) | B1 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer: Not reducible and a three variable problem | B1 | 1 |
| Answer | Marks | Guidance |
|---|---|---|
| b.v | V | \(P_1\) |
| r | 1 | –5 |
| s | 1 | –7 |
| t | 1 | –2 |
| u | 0 | 1 |
| P | –1 | 0 |
| b.v | V | \(P_1\) |
| V | 1 | –5 |
| s | 0 | –2 |
| t | 0 | –3 |
| u | 0 | 1 |
| P | 0 | –5 |
| b.v | V | \(P_1\) |
| V | 1 | –11 |
| \(P_3\) | 0 | –1 |
| t | 0 | 0 |
| u | 0 | 2 |
| P | 0 | –11 |
| M1 A1 | M1 | A1 |
## Part (a)
**Answer:** e.g. Maximise $P = V$
Subject to: $V – 5p_1 – 3p_2 – 6p_3 + r = 0$, $V – 7p_1 – 8p_2 – 4p_3 + s = 0$, $V – 2p_1 – 4p_2 – 9p_3 + t = 0$, $p_1 + p_2 + p_3 + (u) = 1$
where $V =$ value of game to A, $P_i =$ probability of A playing row i
$P_i \geq 0$ and r, s, u are stack variables all $\geq 0$ | B1 5 |
B1 Maximise/minimise and consistent function
M1 constraints (condone non-negativity)
– at least one correct must be equations
A2 all correct
A1 at least two correct
B1 defining variables
## Part (b)
**Answer:** Not reducible and a three variable problem | B1 | 1
## Part (c)
**Answer:**
| b.v | V | $P_1$ | $P_2$ | $P_3$ | r | s | t | u | value |
|---|---|---|---|---|---|---|---|---|---|
| r | **1** | **–5** | **–3** | **–6** | 1 | 0 | 0 | 0 | **0** |
| s | 1 | **–7** | **–8** | **–4** | 0 | 1 | 0 | 0 | **0** |
| t | 1 | **–2** | **–4** | **–9** | 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 |
| b.v | V | $P_1$ | $P_2$ | $P_3$ | r | s | t | u | value | Row ops |
|---|---|---|---|---|---|---|---|---|---|---|
| V | 1 | –5 | –3 | –6 | 1 | 0 | 0 | 0 | 0 | $R_1 / 1$ |
| s | 0 | –2 | –5 | 2 | –1 | 1 | 0 | 0 | 0 | $R_2 – R_1$ |
| t | 0 | –3 | –1 | –3 | –1 | 0 | 1 | 0 | 0 | $R_3 – R_1$ |
| u | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | $R_4$ set |
| P | 0 | –5 | –3 | –6 | 1 | 0 | 0 | 0 | 0 | $R_5 + R_1$ |
| b.v | V | $P_1$ | $P_2$ | $P_3$ | r | s | t | u | value | Row ops |
|---|---|---|---|---|---|---|---|---|---|---|
| V | 1 | –11 | –18 | 0 | –2 | 3 | 0 | 0 | 0 | $R_1 + 6R_2$ |
| $P_3$ | 0 | –1 | $-\frac{5}{2}$ | 1 | $\frac{1}{2}$ | $\frac{1}{2}$ | 0 | 0 | 0 | $R_2 / 2$ |
| t | 0 | 0 | $-\frac{17}{2}$ | 0 | $-\frac{5}{2}$ | $\frac{5}{2}$ | 1 | 0 | 0 | $R_3 + 3R_2$ |
| u | 0 | 2 | $\frac{7}{2}$ | 0 | $\frac{1}{2}$ | $-\frac{1}{2}$ | 0 | 1 | 1 | $R_4 – R_2$ |
| P | 0 | –11 | –18 | 0 | –2 | 3 | 0 | 0 | 0 | $R_5 + 6R_2$ |
| M1 A1 | M1 | A1 | B1ft | 4 |
---A two person zero-sum game is represented by the following pay-off matrix for player $A$.
\begin{tabular}{|c|c|c|c|}
\hline
& $B$ plays 1 & $B$ plays 2 & $B$ plays 3 \\
\hline
$A$ plays 1 & 5 & 7 & 2 \\
\hline
$A$ plays 2 & 3 & 8 & 4 \\
\hline
$A$ plays 3 & 6 & 4 & 9 \\
\hline
\end{tabular}
\begin{enumerate}[label=(\alph*)]
\item Formulate the game as a linear programming problem for player $A$, writing the constraints as equalities and clearly defining your variables. [5]
\item Explain why it is necessary to use the simplex algorithm to solve this game theory problem. [1]
\item Write down an initial simplex tableau making your variables clear. [2]
\item Perform two complete iterations of the simplex algorithm, indicating your pivots and stating the row operations that you use. [8]
\end{enumerate}
(Total 16 marks)
\hfill \mbox{\textit{Edexcel D2 2006 Q7 [16]}}