Dominance and mixed strategies by the Simplex algorithmEdexcel A-Level Further Maths: Subtopic test

1. 1
   Rose and Colin play a zero-sum game, with Rose choosing the rows. Rose's pay-off matrix is $\begin{pmatrix} 3 & 5 & 7 \\ 4 & 2 & 6 \\ 2 & 1 & 5 \end{pmatrix}$.

   (a)

   Which row can be removed because it is dominated?

   [1 mark]

   • ARow 1
   • BRow 2
   • CRow 3
   • DNone of the rows

   (b)

   Which column can be removed because it is dominated?

   [1 mark]

   • AColumn 3
   • BColumn 2
   • CColumn 1
   • DNone of the columns

   (c)

   Use dominance to reduce the game to a $2\times2$ game and find Rose's optimal strategy.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   Rose and Colin play a zero-sum game, with Rose choosing the rows and Colin choosing column $j$ with probability $q_j$. Rose's pay-off matrix is $\begin{pmatrix} -2 & 1 \\ 0 & -1 \\ 1 & -3 \end{pmatrix}$. To use the Simplex algorithm, a constant is added to every entry of the matrix.

   (a)

   What is the smallest integer that can be added to every entry so that all entries are positive?

   [1 mark]

   • A$3$
   • B$-3$
   • C$2$
   • D$4$

   (b)

   After adding $4$ to every entry, Colin's Simplex problem has optimal value $P=\frac27$. What is the value of the original game to Rose?

   [1 mark]

   • A$\frac72$
   • B$-\frac12$
   • C$\frac12$
   • D$\frac27$

   (c)

   After adding $4$ to every entry, formulate Colin's problem as a linear programme for the Simplex algorithm. Define $y_1$ and $y_2$ in terms of $V$, the value of the adjusted game.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Colin is the column player in a zero-sum game. After a constant $3$ has been added to every entry, Rose's pay-off matrix is $\begin{pmatrix} 2 & 6 & 4 \\ 5 & 1 & 2 \end{pmatrix}$. Colin plays column $j$ with probability $q_j$ and the value of the adjusted game is $V$. Writing $y_j=\frac{q_j}{V}$, Colin's problem is: maximise $P=y_1+y_2+y_3$ subject to $2y_1+6y_2+4y_3\le1$, $5y_1+y_2+2y_3\le1$ and $y_1,y_2,y_3\ge0$. Slack variables $r$ and $s$ are added to the first and second constraints. The Simplex algorithm gives the optimal solution $y_1=\frac18$, $y_2=0$, $y_3=\frac{3}{16}$, $P=\frac{5}{16}$.

   (a)

   Set up the initial Simplex tableau. Choosing the $y_1$ column as the pivot column, carry out one iteration and state the pivot element and the value of $P$ after it.

   [3 marks]

   (b)

   Use the optimal solution to find Colin's optimal mixed strategy and the value of the original game to Rose.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   Two phone networks, Zed and Yonder, each choose a pricing plan. The pay-off matrix shows Zed's gain in market share (percentage points), where Zed chooses between three plans (the rows) and Yonder chooses between four (the columns): $\begin{pmatrix} 1 & -2 & 3 & 0 \\ -1 & 3 & 2 & 4 \\ -2 & -3 & 1 & -1 \end{pmatrix}$. Every point gained by Zed is lost by Yonder.

   (a)

   Use dominance arguments to reduce the game to a $2\times2$ game, justifying each deletion, and show that the reduced game has no stable solution.

   [6 marks]

   (b)

   Find the optimal mixed strategy for each network and the value of the game.

   [6 marks]

   Total for question 4: 12 marks

End of questions