OCR D2 2006 June — Question 3 14 marks

Exam BoardOCR
ModuleD2 (Decision Mathematics 2)
Year2006
SessionJune
Marks14
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicDynamic Programming
TypeZero-sum game optimal mixed strategy
DifficultyStandard +0.3 This is a standard D2 game theory question following a predictable template: dominance reduction, play-safe strategies, LP formulation interpretation, and substitution into given expressions. All parts are routine applications of taught algorithms with no novel problem-solving required. The LP is given (not derived), and the solution is provided for substitution. Slightly easier than average due to its highly structured, step-by-step nature.
Spec7.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
3 Rose and Colin repeatedly play a zero-sum game. The pay-off matrix shows the number of points won by Rose for each combination of strategies.
\multirow{6}{*}{Rose's strategy}Colin's strategy
\(W\)\(X\)\(Y\)\(Z\)
\(A\)-14-32
\(B\)5-256
C3-4-10
\(D\)-56-4-2
  1. What is the greatest number of points that Colin can win when Rose plays strategy \(A\) and which strategy does Colin need to play to achieve this?
  2. Show that strategy \(B\) dominates strategy \(C\) and also that strategy \(Y\) dominates strategy \(Z\). Hence reduce the game to a \(3 \times 3\) pay-off matrix.
  3. Find the play-safe strategy for each player on the reduced game. Is the game stable? Rose makes a random choice between the strategies, choosing strategy \(A\) with probability \(p _ { 1 }\), strategy \(B\) with probability \(p _ { 2 }\) and strategy \(D\) with probability \(p _ { 3 }\). She formulates the following LP problem to be solved using the Simplex algorithm: $$\begin{array} { l l } \text { maximise } & M = m - 5 , \\ \text { subject to } & m \leqslant 4 p _ { 1 } + 10 p _ { 2 } , \\ & m \leqslant 9 p _ { 1 } + 3 p _ { 2 } + 11 p _ { 3 } , \\ & m \leqslant 2 p _ { 1 } + 10 p _ { 2 } + p _ { 3 } , \\ & p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 , \\ \text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 . \end{array}$$ (You are not required to solve this problem.)
  4. Explain how \(9 p _ { 1 } + 3 p _ { 2 } + 11 p _ { 3 }\) was obtained. A computer gives the solution to the LP problem as \(p _ { 1 } = \frac { 7 } { 48 } , p _ { 2 } = \frac { 27 } { 48 } , p _ { 3 } = \frac { 14 } { 48 }\).
  5. Calculate the value of \(M\) at this solution.
AnswerMarks Guidance
(i) 3, \(y\)M1, A1, [2] For 3 (allow -3); For \(Y\) (cao)
(ii) \(5 > 3, -2 > -4, 5 > -1\) and \(6 > 0\)
AnswerMarks Guidance
or using signs of differences +2, +2, +6, +6M1, A1 For an appropriate comparison, or implied; For all four comparisons seen
\(3 > -2, -5 > -6, 1 > 0, 4 > 2\)
AnswerMarks Guidance
or equivalent, or using differencesM1, A1 For an appropriate comparison, or implied; For all four comparisons seen
Reduced matrix:
AnswerMarks
\[\begin{array}{ccccc}
& W & X & Y \\
\hline
A & -1 & 4 & -3 \\
B & 5 & -2 & 5 \\
D & -5 & 6 & -4
\end{array}\]
(Colin's strategy)
AnswerMarks Guidance
(Rose's strategy)B1, [5] For correct reduced matrix, with rows and columns labelled \(A, B, D\) and \(W, X, Y\) (Cao)
(iii) Row minima are -3, -2, -5
AnswerMarks Guidance
Play-safe for Rose is \(B\)M1 Follow through their 3×3 reduced matrix; For identifying row \(B\)
Column maxima are 5, 6, 5
AnswerMarks Guidance
Play-safes for Colin are \(W\) and \(Y\)M1 For identifying columns \(W\) and \(Y\)
Not stableA1, [3] For 'no' or 'not stable'
(iv) 5 is added throughout the matrix to make the entries non-negative.
AnswerMarks Guidance
In this augmented reduced matrix, \(9p_1 + 3p_2 + 11p_3\) is the expected number of points won by Rose when both players play strategy \(X\)M1, A1, [2] For 'add 5' or equivalent; For identifying that this is when Colin plays strategy \(X\)
(v) \(p_1 = \frac{3}{48}, p_2 = \frac{28}{48}, p_3 = \frac{14}{48}\)
\(\Rightarrow m \leq \frac{28}{48}\) (or \(6\frac{5}{48}, 6.2083, 6.21\)) in all three cases
AnswerMarks Guidance
\(\Rightarrow M = \frac{28}{48}\) (or \(\frac{7}{12}, 1\frac{2}{12}, 1.2083, 1.21\))M1, A1, [2] For attempting to evaluate \(m\); Cao (in any appropriate form) 
(i) 3, $y$ | M1, A1, [2] | For 3 (allow -3); For $Y$ (cao)

(ii) $5 > 3, -2 > -4, 5 > -1$ and $6 > 0$
or using signs of differences +2, +2, +6, +6 | M1, A1 | For an appropriate comparison, or implied; For all four comparisons seen

$3 > -2, -5 > -6, 1 > 0, 4 > 2$
or equivalent, or using differences | M1, A1 | For an appropriate comparison, or implied; For all four comparisons seen

Reduced matrix:

$$\begin{array}{c|cccc}
& W & X & Y \\
\hline
A & -1 & 4 & -3 \\
B & 5 & -2 & 5 \\
D & -5 & 6 & -4
\end{array}$$
(Colin's strategy)
(Rose's strategy) | B1, [5] | For correct reduced matrix, with rows and columns labelled $A, B, D$ and $W, X, Y$ (Cao)

(iii) Row minima are -3, -2, -5
Play-safe for Rose is $B$ | M1 | Follow through their 3×3 reduced matrix; For identifying row $B$

Column maxima are 5, 6, 5
Play-safes for Colin are $W$ and $Y$ | M1 | For identifying columns $W$ and $Y$

Not stable | A1, [3] | For 'no' or 'not stable'

(iv) 5 is added throughout the matrix to make the entries non-negative.
In this augmented reduced matrix, $9p_1 + 3p_2 + 11p_3$ is the expected number of points won by Rose when both players play strategy $X$ | M1, A1, [2] | For 'add 5' or equivalent; For identifying that this is when Colin plays strategy $X$

(v) $p_1 = \frac{3}{48}, p_2 = \frac{28}{48}, p_3 = \frac{14}{48}$

$\Rightarrow m \leq \frac{28}{48}$ (or $6\frac{5}{48}, 6.2083, 6.21$) in all three cases

$\Rightarrow M = \frac{28}{48}$ (or $\frac{7}{12}, 1\frac{2}{12}, 1.2083, 1.21$) | M1, A1, [2] | For attempting to evaluate $m$; Cao (in any appropriate form)

---
3 Rose and Colin repeatedly play a zero-sum game. The pay-off matrix shows the number of points won by Rose for each combination of strategies.

\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}
\hline
\multirow{6}{*}{Rose's strategy} & \multicolumn{5}{|c|}{Colin's strategy} \\
\hline
 &  & $W$ & $X$ & $Y$ & $Z$ \\
\hline
 & $A$ & -1 & 4 & -3 & 2 \\
\hline
 & $B$ & 5 & -2 & 5 & 6 \\
\hline
 & C & 3 & -4 & -1 & 0 \\
\hline
 & $D$ & -5 & 6 & -4 & -2 \\
\hline
\end{tabular}
\end{center}

(i) What is the greatest number of points that Colin can win when Rose plays strategy $A$ and which strategy does Colin need to play to achieve this?\\
(ii) Show that strategy $B$ dominates strategy $C$ and also that strategy $Y$ dominates strategy $Z$. Hence reduce the game to a $3 \times 3$ pay-off matrix.\\
(iii) Find the play-safe strategy for each player on the reduced game. Is the game stable?

Rose makes a random choice between the strategies, choosing strategy $A$ with probability $p _ { 1 }$, strategy $B$ with probability $p _ { 2 }$ and strategy $D$ with probability $p _ { 3 }$. She formulates the following LP problem to be solved using the Simplex algorithm:

$$\begin{array} { l l } 
\text { maximise } & M = m - 5 , \\
\text { subject to } & m \leqslant 4 p _ { 1 } + 10 p _ { 2 } , \\
& m \leqslant 9 p _ { 1 } + 3 p _ { 2 } + 11 p _ { 3 } , \\
& m \leqslant 2 p _ { 1 } + 10 p _ { 2 } + p _ { 3 } , \\
& p _ { 1 } + p _ { 2 } + p _ { 3 } \leqslant 1 , \\
\text { and } & p _ { 1 } \geqslant 0 , p _ { 2 } \geqslant 0 , p _ { 3 } \geqslant 0 , m \geqslant 0 .
\end{array}$$

(You are not required to solve this problem.)\\
(iv) Explain how $9 p _ { 1 } + 3 p _ { 2 } + 11 p _ { 3 }$ was obtained.

A computer gives the solution to the LP problem as $p _ { 1 } = \frac { 7 } { 48 } , p _ { 2 } = \frac { 27 } { 48 } , p _ { 3 } = \frac { 14 } { 48 }$.\\
(v) Calculate the value of $M$ at this solution.

\hfill \mbox{\textit{OCR D2 2006 Q3 [14]}}
This paper (4 questions)
View full paper
Q1 14 Q2 15 Q3 14 Q4 14