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

A strategy is dominated if another strategy is at least as good whatever the opponent does, so it would never be chosen in an optimal strategy.

• Rows (Rose, maximising): row $i$ is dominated by row $k$ if every entry of row $i$ is less than or equal to the matching entry of row $k$.
• Columns (Colin, minimising Rose's pay-off): column $j$ is dominated by column $l$ if every entry of column $j$ is greater than or equal to the matching entry of column $l$. Dominated rows and columns can be deleted, and the game reduced, before looking for a solution. Dominated strategies are played with probability $0$. Example: $\begin{pmatrix} 5 & 2 & 8 \\ 3 & 6 & 4 \\ 2 & 1 & 3 \end{pmatrix}$. Row 3 is dominated by row 1 (and by row 2). Column 3 is dominated by column 1 ($8\ge5$, $4\ge3$). This leaves $\begin{pmatrix} 5 & 2 \\ 3 & 6 \end{pmatrix}$.

After deleting dominated strategies, check for a stable solution (maximin $=$ minimax) and otherwise solve the smaller game, for instance the $2\times2$ case by equating expected pay-offs. Deleting can be repeated: a deletion may create new dominance. State every deleted strategy with its reason, and give probability $0$ to each when you quote the final strategy. For $\begin{pmatrix} 5 & 2 \\ 3 & 6 \end{pmatrix}$: row 1 with probability $p$ gives $3+2p$ and $6-4p$, so $p=\frac12$ and the value is $4$. Colin plays column 1 with probability $q$: $2+3q=6-3q$ gives $q=\frac23$. So Rose plays $\left(\frac12,\frac12,0\right)$ and Colin plays $\left(\frac23,\frac13,0\right)$.

Larger games can be solved with the Simplex algorithm. For the player who chooses the columns (Colin):

1. Add a constant $k$ to every entry so that all entries are positive. The value of the game is then positive, $V>0$, and the optimal strategies are unchanged. Remember to subtract $k$ at the end.
2. Let Colin play column $j$ with probability $q_j$. Rose's expected gain against each row must be at most $V$: $\sum_j a_{ij}q_j\le V$.
3. Divide by $V$ and write $y_j=\frac{q_j}{V}$. The constraints become $\sum_j a_{ij}y_j\le1$ and, since $\sum q_j=1$, $\sum y_j=\frac1V$.
4. Colin wants $V$ as small as possible, so maximise $P=\sum y_j$ subject to the constraints and $y_j\ge0$. Example, with $\begin{pmatrix} 5 & 2 \\ 3 & 6 \end{pmatrix}$: maximise $P=y_1+y_2$ subject to $5y_1+2y_2\le1$ and $3y_1+6y_2\le1$. To set the problem up for Rose, write the game from Colin's point of view (negate and transpose) so that Rose becomes the column player, then add $k$.

Add slack variables $r$, $s$, ... and form the initial tableau, with the profit row $P-y_1-y_2=0$. Repeat:

• the pivot column has the most negative entry in the profit row;
• the pivot row has the smallest non-negative ratio (value $\div$ positive entry in the pivot column);
• divide the pivot row by the pivot, then use row operations to make the rest of the pivot column $0$. Stop when the profit row has no negative entries. Example: after two iterations $y_1=\frac16$, $y_2=\frac1{12}$ and $P=\frac14$. The slack columns of the profit row both show $\frac18$.

From the optimal tableau:

1. $V=\frac1P$ (the value of the adjusted game).
2. $q_j=V\,y_j$ for each column, with $q_j=0$ if $y_j$ is not basic.
3. Value of the original game $=V-k$.
4. Rose's strategy can be read from the profit row: the entries under the slack variables, each multiplied by $V$, give her probabilities. Example: $P=\frac14$, so $V=4$; $q_1=4\times\frac16=\frac23$, $q_2=4\times\frac1{12}=\frac13$; and the profit-row entries $\frac18$ and $\frac18$ give Rose $\frac12$ and $\frac12$. No constant was added to this matrix, so the value is $4$.