Zero-sum games, play-safe strategies and saddle points
Studying this course? Keep your progress in one place.
Key facts
- In a zero-sum game one player's gain is the other's loss. The matrix gives Rose's pay-offs; Colin's is the negative.
- Rose's play-safe (maximin) strategy: the row with the largest row minimum.
- Colin's play-safe (minimax) strategy: the column with the smallest column maximum.
- A stable solution exists if and only if maximin minimax. The common value is the value of the game.
- If maximin minimax there is no stable solution and players need mixed strategies.
The pay-off matrix
Rose chooses a row, Colin chooses a column, and the entry is Rose's gain. Colin's pay-off is its negative.
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.
The pay-off matrix is 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.
- Rose plays row 1
- Rose plays row 2
| Colin plays column 1 | Colin plays column 2 | |
|---|---|---|
| Rose plays row 1 | 2 | −1 |
| Rose plays row 2 | −3 | 4 |
Colin plays column 1
- Rose plays row 1:
- 2
- Rose plays row 2:
- −3
Colin plays column 2
- Rose plays row 1:
- −1
- Rose plays row 2:
- 4
Worked example
In the game , Rose plays row 2 and Colin plays column 1. What happens?
- 1
Find the entry in row 2, column 1: .
- 2
This is Rose's pay-off, so Rose loses 3.
- 3
Colin's pay-off is the negative of this.
The entry for a pair of strategies is . What does this mean?
Play-safe strategies
Guard against the worst case: Rose picks the row with the largest minimum, Colin the column with the smallest maximum.
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.
Write the row minima beside the matrix and the column maxima beneath it.
| Column 1 | Column 2 | Column 3 | Row minimum | |
|---|---|---|---|---|
| Row 1 | 4 | −2 | 1 | −2 |
| Row 2 | 3 | 2 | 5 | 2 |
| Row 3 | −1 | 0 | 6 | −1 |
| Column maximum | 4 | 2 | 6 | – |
Column 1
- Row 1:
- 4
- Row 2:
- 3
- Row 3:
- −1
- Column maximum:
- 4
Column 2
- Row 1:
- −2
- Row 2:
- 2
- Row 3:
- 0
- Column maximum:
- 2
Column 3
- Row 1:
- 1
- Row 2:
- 5
- Row 3:
- 6
- Column maximum:
- 6
Row minimum
- Row 1:
- −2
- Row 2:
- 2
- Row 3:
- −1
- Column maximum:
- –
Worked example
Find the play-safe strategies for .
- 1
Row minima: , , .
- 2
Maximin is the largest: 2, so Rose plays row 2.
- 3
Column maxima: 4, 2, 6.
- 4
Minimax is the smallest: 2, so Colin plays column 2.
Rose has row minima 1, , 0. Which row does she play?
Stable solutions and saddle points
A game is stable if and only if maximin equals minimax. The common value is the value of the game, at a saddle point.
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: 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. A game can have more than one saddle point, all with the same value.
In the example above the saddle point is row 2, column 2 and the value is 2.
- Row minimum
- Column maximum
- Stable solutionmaximin minimax
- Value of the gamethe common value, as Rose's pay-off
For , is there a stable solution?
No stable solution
Maximin is never greater than minimax. If it is smaller, there is no stable solution and play-safe choices are predictable.
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 reached by a pair of pure strategies.
A play-safe choice is predictable, so players need to mix their strategies at random (the next topic).
| Stable | Not stable | |
|---|---|---|
| Condition | maximin = minimax | maximin < minimax |
| Meaning | a saddle point; a value of the game | players mix their strategies |
Stable
- Condition:
- maximin = minimax
- Meaning:
- a saddle point; a value of the game
Not stable
- Condition:
- maximin < minimax
- Meaning:
- players mix their strategies
Worked example
Show that has no stable solution.
- 1
Row minima , so maximin .
- 2
Column maxima 2, 4, so minimax .
- 3
If Colin plays safe (column 1), Rose should play row 1 for .
- 4
But then Colin should switch to column 2 for a result of , and the cycle continues.
Maximin is 1 and minimax is 3. What can you say?
Exam method
Write the matrix, find maximin and minimax, compare, then conclude in context. If the game is given from Colin's view, the roles swap.
Follow the same steps every time.
If you are given the game from Colin's point of view, the roles swap: Colin's play-safe strategy then maximises his minimum entry.
"Show that there is a stable solution" needs both numbers, maximin and minimax, and a statement that they are equal.
- 1
Write the matrix
from the correct player's view
- 2
Find maximin and minimax
row minima, take the largest; column maxima, take the smallest
- 3
Compare
if equal, state the saddle point, strategies and value; if not, say there is no stable solution
- 4
Conclude in context
name the strategies and sign the pay-off for the right player
What must a "show there is a stable solution" answer include?
Try an exam question
Rose's pay-off matrix is . Show that the game has a stable solution, and state each player's play-safe strategy and the value of the game.
[4 marks]
- [1]Row minima are 3, 1, , so maximin is 3 and Rose plays row 1.
- [1]Column maxima are 5, 3, 7, so minimax is 3 and Colin plays column 2.
- [1]Maximin equals minimax, so the game has a stable solution.
- [1]The value of the game is 3, at the saddle point in row 1, column 2.
That's the notes covered.
Carry on to the next subtopic.
Try a question
Which row is Rose's play-safe strategy?
1 mark, marked against the mark scheme
Which row is Rose's play-safe strategy?
1 mark, marked against the mark scheme