Dominance and mixed strategiesAQA A-Level Further Maths: Revision notes

A strategy is dominated if another strategy is at least as good in every case, so a sensible player never uses it.

• Rows (Rowan, maximiser): row $A$ is dominated by row $B$ if every entry of $B$ is greater than or equal to the matching entry of $A$.
• Columns (Colin, minimiser): column $A$ is dominated by column $B$ if every entry of $B$ is less than or equal to the matching entry of $A$ (Colin prefers smaller pay-offs).

Remove dominated rows and columns to get a smaller game. Repeat, because removing a row can make a column dominated and vice versa. Example: for $\begin{pmatrix} 3 & 2 & 4 \\ 1 & 5 & 2 \\ 4 & 3 & 5 \end{pmatrix}$, row 3 ($4,3,5$) dominates row 1 ($3,2,4$), and column 1 ($3,1,4$) dominates column 3 ($4,2,5$), so remove row 1 and column 3 to leave $\begin{pmatrix} 1 & 5 \\ 4 & 3 \end{pmatrix}$.

If a game has no stable solution, a player who always makes the same choice can be exploited. A mixed strategy chooses each strategy with a stated probability, chosen at random each time.

• Rowan plays row 1 with probability $p$ and row 2 with probability $1-p$.
• His expected pay-off against each of Colin's columns is a linear expression in $p$.
• The optimal mixed strategy maximises the smallest of these expected pay-offs. For a $2\times2$ game, this happens where the two expected pay-offs are equal.

The resulting expected pay-off is the value of the game, and it is the same whichever column Colin uses (when he plays only the columns in his optimal mix).

For $\begin{pmatrix} 5 & 1 \\ 2 & 4 \end{pmatrix}$ there is no stable solution: maximin $=2$ and minimax $=4$. Rowan plays row 1 with probability $p$.

• Against column 1: $5p+2(1-p)=3p+2$.
• Against column 2: $p+4(1-p)=4-3p$.
• Equate: $6p=2$, so $p=\frac13$. Value $=3$.

For Colin, play column 1 with probability $q$: against row 1 the pay-off is $5q+(1-q)=4q+1$, against row 2 it is $2q+4(1-q)=4-2q$. Equate: $q=\frac12$, value $3$ again.

Interpretation: over many plays, Rowan should choose row 1 about one time in three, at random, and on average gains $3$ per play.

If Rowan has two strategies and Colin has $n$, write Rowan's expected pay-off against each of Colin's columns as a line in $p$ (for $0\leq p\leq1$) and draw the lines on one set of axes. Colin will choose the column that gives Rowan the least, so Rowan's guaranteed pay-off is the lower boundary of the lines. His optimal $p$ is at the highest point of this lower boundary, and the height there is the value of the game.

• The two lines that cross at this point give Colin's optimal columns; any line above that point is a column Colin never plays.
• Example: $\begin{pmatrix} 2 & 5 & 1 \\ 4 & 1 & 6 \end{pmatrix}$ gives lines $4-2p$, $1+4p$, $6-5p$. The first two meet at $p=\frac12$ with value $3$, and the third is $3.5$ there, so Colin never plays column 3.

If Rowan has $m$ strategies and Colin has two, use $q$ for Colin and find the lowest point of the upper boundary of the lines.