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

Exam questions on Dominance and mixed strategies by the Simplex algorithm

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}$.
   Use dominance to reduce the game to a $2\times2$ game and find Rose's optimal strategy.2 marks
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.
   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
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}$.
   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