Maths › Decision Mathematics 2 › Game theory: play safe and stable solutions
Game theory: play safe and stable solutions
A two-player zero-sum game is set out as a single matrix of pay-offs. Ask what each player can guarantee themselves, and the two answers either meet, settling the game, or they do not.
Builds on Dynamic programming and Probability and Venn diagrams.
IN THIS TOPIC
- Read a pay-off matrix from the row player's point of view.
- Find both play-safe strategies.
- Test for a stable solution and state the value of the game.
- Reduce a matrix using dominance arguments.
COMMON MISCONCEPTION
In a zero-sum game the column player wants the largest entries, since a large pay-off is good.
What each player can guarantee
The matrix is always written from the row player's point of view, so a positive entry is a gain to the row player and the same loss to the column player. One player's gain is the other's loss, so the column player is hunting for small entries, not large ones.
The row player's play safe choice looks at the worst outcome in each row and takes the row whose worst is best, the maximin. The column player looks at the largest entry in each column and takes the column whose largest is smallest, the minimax. Each is guarding against the other playing perfectly.
WORKED EXAMPLE
Finding the play-safe pair
For the game with rows (3, 5, 2) and (6, 1, 4), find both play-safe strategies.
Row minima are 2 and 1, so the row player's maximin is 2, playing R1.
Column maxima are 6, 5 and 4, so the column player's minimax is 4, playing C3.
The two differ, so the game has no stable solution: whichever pair is played, one player can improve by switching.
Stable solutions and dominance
A game has a stable solution, or saddle point, exactly when the row maximin equals the column minimax. Neither player can then do better by moving alone, that common number is the value of the game, and the pair of choices where it occurs is the solution. When the two differ, no single pair is stable and mixed strategies are needed.
Look for dominance before any of that. A row is strictly dominated when another row is strictly better for the row player in every column, and a column when another is strictly better, meaning strictly smaller, for the column player in every row. A strictly dominated option would never be chosen, so delete it outright. When the other option is merely at least as good everywhere, and better somewhere, the dominance is weak: deletion is still the standard move at this level, but say which comparison you are using, since a weakly dominated option can tie. Repeat, and a large matrix often collapses to a two by two.
GUIDED PRACTICE
Reducing by dominance
For the same game, rows (3, 5, 2) and (6, 1, 4), show that one column can be deleted and state what is left.
Show the working
Compare C1 with C3: the entries are 3 and 6 against 2 and 4.
The column player wants small numbers, and 2 < 3 with 4 < 6, so C3 dominates C1.
C1 would never be chosen, so delete it.
What remains is the two by two game with rows (5, 2) and (1, 4), which still has no saddle point and needs a mixed strategy.
ASSESSMENT FOCUS
- Say that the matrix is written from the row player's point of view, and that the column player wants small entries.
- Write the row minima beside the matrix and the column maxima below it.
- Compare maximin with minimax explicitly and state whether the game is stable.
- Justify every dominance deletion by naming the option that dominates and the comparison in each row or column.
- If the question gives the matrix from the column player's view, transpose and change signs before starting.
CHECK YOURSELF
A game has row minima 4 and 2, and column maxima 7, 4 and 9. Is it stable, and what is the value?
Show a hint
Compare the best of each.
Show the answer
Maximin is 4 and minimax is 4, so they agree: the game is stable with value 4, occurring where the first row meets the second column.
The matrix is from the row player's view, so they maximise the row minima and the column player minimises the column maxima.
The game is stable exactly when maximin equals minimax, and that common number is the value.
Delete any strictly dominated row or column before doing anything else.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the game theory: play safe and stable solutions questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Read a pay-off matrix from the row player's point of view.
- Find both play-safe strategies.
- Test for a stable solution and state the value of the game.
- Reduce a matrix using dominance arguments.
Open the full revision checklist to see every objective in the course in one place.