A2 June 2023 Q8

EdexcelCurrent spec17 marksGame Theory

8. A two-person zero-sum game is represented by the pay-off matrix for player A shown below.

		Player B
		Option X	Option Y	Option Z
Player A	Option Q	\(-3\)	\(2\)	\(5\)
	Option R	\(2\)	\(-1\)	\(0\)
	Option S	\(4\)	\(-2\)	\(-1\)
	Option T	\(-4\)	\(0\)	\(2\)

(a) Verify that there is no stable solution to this game. (2)

(b) Explain why player A should never play option T. You must make your reasoning clear. (2)

Player A intends to make a random choice between options Q, 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.

(c)

(i) Formulate the game as a linear programming problem for player A. You should write the constraints as equations.

(ii) Write down an initial Simplex tableau for this linear programming problem, making your variables clear. (7)

The linear programming problem is solved using the Simplex algorithm. The optimal value of \(p_1\) is \(\dfrac{6}{11}\) and the optimal value of \(p_2\) is 0

(d) Find the best strategy for player B, defining any variables you use. (6)

Mark scheme (a)

Scheme	Marks	AO
Row minima are \(-3, -1, -2, -4\) Column maxima are 4, 2, 5	M1	1.1b
As Row maximin is not equal to Column minimax \((-1 \neq 2)\) the game is not stable	A1	2.4
	(2)

Notes

M1: Clear attempt to find the row maximin and column minimax (either the row minimums or column maximums correct or at least five (of the seven) values stated correctly)

A1: CAO (dependent on all rowmins and colmaxs correct) states \(-1 \neq 2\) (or row (maximin) \(\neq\) col (minimax) as long as \(-1\) is clearly identified as the row maximin and 2 as the column minimax)

Mark scheme (b)

Scheme	Marks	AO
Option Q dominates option T	B1	1.2
Because e.g., \(-3 > -4\), \(2 > 0\) and \(5 > 2\)	B1	2.4
	(2)

Notes

B1: Correct statement – must include the word ‘dominate’ (or exact equivalent)

B1: Correct inequalities – must be clear that all inequalities must hold

Mark scheme (c)

Scheme

Marks

(i) e.g., 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}\)

1.1b

Maximise \(P - V = 0\) where \(V\) is the value of the augmented game to A

3.3

\(V - 5p_2 - 7p_3 + r = 0\)
\(V - 5p_1 - 2p_2 - p_3 + s = 0\)
\(V - 8p_1 - 3p_2 - 2p_3 + t = 0\)

M1
A1

3.3
1.1b

\(p_1 + p_2 + p_3 + u = 1\)

3.3

(ii)

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\)

M1

A1

3.3

1.1b

(7)

Notes

(c)(i)

B1: Correct augmentation – possibly implied by later working

B1: Correct objective defined

M1: At least three equations in \(V, p_1, p_2, p_3\) and at least one dummy variable seen

A1: CAO

B1: Correct probability equation

(ii)

M1: Any two (numerical in nature) row correct

A1: CAO including correct row and column labels for Simplex tableau

Alternative if augmenting by +4

Scheme

Marks

(i) e.g., augment by +4 \(\,\)\(\begin{pmatrix} -3 & 2 & 5 \\ 2 & -1 & 0 \\ 4 & -2 & -1 \end{pmatrix}\) \(\rightarrow\) \(\begin{pmatrix} 1 & 6 & 9 \\ 6 & 3 & 4 \\ 8 & 2 & 3 \end{pmatrix}\)

1.1b

Maximise \(P - V = 0\) where \(V\) is the value of the augmented game to A

3.3

\(V - p_1 - 6p_2 - 8p_3 + r = 0\)
\(V - 6p_1 - 3p_2 - 2p_3 + s = 0\)
\(V - 9p_1 - 4p_2 - 3p_3 + t = 0\)

M1
A1

3.3
1.1b

\(p_1 + p_2 + p_3 + u = 1\)

3.3

(ii)

b.v.	\(V\)	\(p_1\)	\(p_2\)	\(p_3\)	\(r\)	\(s\)	\(t\)	\(u\)	Value
\(r\)	\(1\)	\(-1\)	\(-6\)	\(-8\)	\(1\)	\(0\)	\(0\)	\(0\)	\(0\)
\(s\)	\(1\)	\(-6\)	\(-3\)	\(-2\)	\(0\)	\(1\)	\(0\)	\(0\)	\(0\)
\(t\)	\(1\)	\(-9\)	\(-4\)	\(-3\)	\(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\)

M1

A1

3.3

1.1b

(7)

Mark scheme (d)

Scheme	Marks	AO
\(p_3 = \dfrac{5}{11}\)	B1	1.1b
\(V \leqslant \dfrac{35}{11},\ V \leqslant \dfrac{35}{11},\ V \leqslant \dfrac{58}{11} \Rightarrow V = \dfrac{35}{11}\)	M1	3.1a
Let Player B play option X with probability \(q_1\), option Y with probability \(q_2\) and option Z with probability \(q_3\)	B1	1.1b
\(\begin{aligned}5q_2 + 8q_3 &= \dfrac{35}{11} \\[6pt] 7q_1 + q_2 + 2q_3 &= \dfrac{35}{11} \\[6pt] q_1 + q_2 + q_3 &= 1\end{aligned}\)	dM1 A1ft	3.1a 1.1b
Player B should play option X with probability \(\dfrac{4}{11}\), option Y with probability \(\dfrac{7}{11}\) and never play option Z	A1	3.2a
	(6)
	(17 marks)

Notes

B1: \(p_3\) correctly stated

M1: Attempt to find \(V\) by substituting probabilities into all three equations or corresponding inequalities involving \(V, p_1, p_2, p_3\) (or using the original value of the game) (Note candidates may reject B plays Z here as \(V\) is worse than playing X or Y)

B1: Defining probabilities for Player B

dM1: Dependent on previous M mark - setting up at least three equations in their \(q_1, q_2, q_3\) using their \(V\) (or original value) (may be just \(q\) and \((1 - q)\) if Option Z rejected)

A1ft: Correct three equations (two if Option Z rejected) following through their augmented matrix in (c) – A0 if option R for player A is used (and not rejected later)

A1: Correct options for Player B in context (must say that Player B should never play option Z but this may appear earlier in their working) dependent on previous A mark

Alternative if augmenting by +4

Scheme	Marks	AO
\(p_3 = \dfrac{5}{11}\)	B1	1.1b
\(V \leqslant \dfrac{46}{11},\ V \leqslant \dfrac{46}{11},\ V \leqslant \dfrac{69}{11} \Rightarrow V = \dfrac{46}{11}\)	M1	3.1a
Let Player B play option X with probability \(q_1\), option Y with probability \(q_2\) and option Z with probability \(q_3\)	B1	1.1b
\(\begin{aligned}q_1 + 6q_2 + 9q_3 &= \dfrac{46}{11} \\[6pt] 8q_1 + 2q_2 + 3q_3 &= \dfrac{46}{11} \\[6pt] q_1 + q_2 + q_3 &= 1\end{aligned}\)	dM1 A1ft	3.1a 1.1b
Player B should play option X with probability \(\dfrac{4}{11}\), option Y with probability \(\dfrac{7}{11}\) and never play option Z	A1	3.2a
For notes see main scheme above	(6)

Alternative for (d)

Scheme	Marks	AO
\(p_3 = \dfrac{5}{11}\)	B1
Recognises that Option Y dominates Option Z and reduces matrix to either 3 x 2 or 2 x 2 (if A plays R removed) e.g. \(\begin{array}{ccc} & X & Y \\ Q & -3 & 2 \\ R & 2 & -1 \\ S & 4 & -2 \end{array}\) or \(\begin{array}{ccc} & X & Y \\ Q & 0 & 5 \\ R & 5 & 2 \\ S & 7 & 1 \end{array}\) or \(\begin{array}{ccc} & X & Y \\ Q & 1 & 6 \\ R & 6 & 3 \\ S & 8 & 2 \end{array}\)	M1
Define probabilities for B e.g. play Option X with probability \(q\) and Option Y with probability \((1 - q)\)	B1
e.g. \(-3q + 2(1 - q) \Rightarrow 2 - 5q\) \(\quad\ \ 4q - 2(1 - q) \Rightarrow 6q - 2\)	dM1
e.g. \(2 - 5q = 6q - 2\) \(\quad\ \ q = \dfrac{4}{11}\)	A1ft
Player B should play option X with probability \(\dfrac{4}{11}\), option Y with probability \(\dfrac{7}{11}\) and never play option Z	A1
	(6)

(d) B1: \(p_3\) correctly stated

M1: Uses dominance argument (may be implied) to reduce either the original Matrix or their augmented Matrix to either 3 x 2 or 2 x 2 (if A plays R deleted). The Matrix may be transposed and signs changed.

B1: Defining probabilities for Player B (condone use of \(p\) instead of \(q\))

dM1: Dependent on previous M mark - setting up at least two equations (using A plays Q and S) or expressions in terms of their \(q\)

A1ft: Solves their expressions or equations to obtain \(q\) (may use graphical approach). If solving multiple pairs of expressions, they must clearly choose their solution – A0 if option R for player A is used (and not rejected later)

A1: Correct options for Player B in context (must say that Player B should never play option Z but this may appear earlier in their working) dependent on previous A mark