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. Each player's play-safe strategy guarantees a minimum return, and when maximin equals minimax the game has a saddle point, which is a pure-strategy Nash equilibrium. Where they differ, no pure saddle point exists and the equilibrium is a mixed one.
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.
- Convert a constant-sum game to zero-sum form before solving it.
- Find both play-safe strategies.
- Test for a saddle point, a pure-strategy Nash equilibrium, 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.
The matrix is written from the row player's point of view, so an entry is a gain to the row player and the same loss to the column player, who is therefore hunting for small entries. The row player takes the row whose worst entry is best, the maximin, and the column player the column whose largest entry is smallest, the minimax. The game is stable exactly when those two agree.
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.
A game does not have to arrive in that form. If a cell gives both players' pay-offs and those two numbers add to the same constant k in each cell, the game is constant-sum, and one subtraction converts it: take k off each of the row player's entries, and the column player's pay-off becomes minus the row player's. Subtracting a fixed number from the whole matrix leaves every comparison between entries as it was, so both players make the same choices afterwards as before. Where the totals differ from cell to cell there is nothing to subtract and the conversion is not available.
Take a game whose two pay-offs add to 10 in each cell, the row player collecting 7 and 6 in the first row, 5 and 3 in the second. Subtract 10 and the row player's matrix becomes rows (−3, −4) and (−5, −7), against which the column player holds 3, 4, 5 and 7, the negatives of those entries. Work on the converted matrix from there on, and add the 10 back at the end, since the value of the game moved down with the entries.
Describe the drawing
On the left, a two by two game whose cells give both players' pay-offs as pairs, seven and three, six and four, five and five, three and seven, each adding to ten. An arrow marked subtract ten leads to the right, where the same game is written as a single matrix from the row player's side, minus three and minus four above minus five and minus seven. The column player's original entries are exactly the negatives of these, which is what zero-sum means.
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 saddle point in pure strategies: whichever single pair is played, one player can improve by switching. A mixed-strategy equilibrium still exists.
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.
A saddle point is a pure-strategy Nash equilibrium. If maximin and minimax differ, there is no pure saddle point, but a finite zero-sum game still has a mixed-strategy equilibrium, which is what the next topic finds.
The pair of choices at a saddle point is also called a Nash equilibrium, meaning a choice of strategies from which neither player gains by changing alone. For a two-person zero-sum game the two names pick out the same thing, so a question asking for a Nash equilibrium wants the saddle point and the reason it is stable, found by the comparison above.
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 has a pure-strategy saddle point; if it does not, say that a mixed strategy is required.
- A question naming a Nash equilibrium is asking for the stable solution, so find it the same way and say that neither player gains by moving alone.
- If the pay-offs in each cell add to a constant, subtract that constant from the row player's entries first, and add it back to the value at the end.
- 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 the row player maximises the row minima and the column player minimises the column maxima.
The game has a pure-strategy saddle point exactly when maximin equals minimax, and that common number is the value; when they differ, the equilibrium is a mixed one.
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.
- Convert a constant-sum game to zero-sum form before solving it.
- Find both play-safe strategies.
- Test for a saddle point, a pure-strategy Nash equilibrium, 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.