Zero-sum games, play-safe strategies and saddle pointsEdexcel A-Level Further Maths: Revision notes

In a two-person zero-sum game one player's gain is exactly the other's loss, so the total pay-off is always zero. All the information is held in a pay-off matrix, written from the row player's point of view (Rose) unless you are told otherwise. Rose chooses a row, Colin chooses a column, and the entry is Rose's gain. A negative entry is a loss for Rose. Colin's pay-off is the negative of the entry. Example: $\begin{pmatrix} 2 & -1 \\ -3 & 4 \end{pmatrix}$. If Rose plays row 2 and Colin plays column 1, Rose loses $3$ and Colin gains $3$.

A play-safe strategy guards against the worst case, assuming the opponent plays the best reply.

• Rose (rows): find the minimum of each row, then choose the row with the largest of these. This is her maximin strategy.
• Colin (columns): find the maximum of each column (the most he could lose), then choose the column with the smallest of these. This is his minimax strategy. Example: for $\begin{pmatrix} 4 & -2 & 1 \\ 3 & 2 & 5 \\ -1 & 0 & 6 \end{pmatrix}$ the row minima are $-2,\ 2,\ -1$, so maximin $=2$ (row 2); the column maxima are $4,\ 2,\ 6$, so minimax $=2$ (column 2).

A game has a stable solution if and only if maximin $=$ minimax. The common value is the value of the game. The entry where the play-safe row and column meet is a saddle point: it is the least entry in its row and the greatest entry in its column. At a stable solution neither player can do better by changing strategy alone: if Rose leaves her play-safe row Colin's reply costs her, and if Colin leaves his play-safe column Rose gains. In the example above the saddle point is row 2, column 2 and the value of the game is $2$. A game can have more than one saddle point, all with the same value. You are not asked to prove the theorem.

The maximin is never greater than the minimax. If maximin $<$ minimax there is no stable solution: Rose can only guarantee the maximin, Colin can only hold her to the minimax, and neither value is achieved by a pair of pure strategies. Example: $\begin{pmatrix} 2 & -1 \\ -3 & 4 \end{pmatrix}$ has row minima $-1,-3$ (maximin $-1$) and column maxima $2,4$ (minimax $2$). If Colin plays safe (column 1), Rose should play row 1 for $+2$; but then Colin should switch to column 2 for a $-1$ result, and the cycle continues. A play-safe choice is predictable, so players need to mix their strategies at random (the next topic).

1. Write the pay-off matrix from the correct player's view.
2. List row minima and take the largest (maximin); list column maxima and take the smallest (minimax).
3. Compare them: if equal, state the saddle point, the optimal strategies and the value; if not, say there is no stable solution.
4. State the conclusion in context, naming the strategies and signing the pay-off for the right player. If you are given the game from Colin's point of view, remember the roles swap: Colin's play-safe strategy then maximises his minimum entry.