Maths › Decision Mathematics 2 › Game theory: play safe and stable solutions
Game theory: play safe and stable solutions
Two players, opposite interests, and one matrix of pay-offs. Ask what each 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 and test for a stable solution.
- Reduce a matrix using dominance arguments.
WHAT YOU PROBABLY THINK
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. Since one player's gain is the other's loss, the column player wants the entries small, which is what the opening claim reverses.
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. Then neither player can do better by moving alone, that common number is the value of the game, and the pair of choices at which it occurs is the solution. When they differ, no single pair is stable, and mixed strategies are needed.
Before any of that, look for dominance. A row is dominated if another row is at least as good for the row player in every column, and a column is dominated if another is at least as good, meaning smaller, for the column player in every row. A dominated option would never be chosen, so it can be deleted outright, and repeating that often reduces a large matrix to a two by two.
YOUR TURN
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.
THE EXAM BIT
- 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.
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
M
a
x
i
m
i
n
i
s
4
a
n
d
m
i
n
i
m
a
x
i
s
4
,
s
o
t
h
e
y
a
g
r
e
e
:
t
h
e
g
a
m
e
i
s
s
t
a
b
l
e
w
i
t
h
v
a
l
u
e
4
,
o
c
c
u
r
r
i
n
g
w
h
e
r
e
t
h
e
f
i
r
s
t
r
o
w
m
e
e
t
s
t
h
e
s
e
c
o
n
d
c
o
l
u
m
n
.
The matrix is from the row player's view: they maximise the row minima, the column player minimises the column maxima.
The game is stable exactly when maximin equals minimax; delete any dominated row or column first.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Read a pay-off matrix from the row player's point of view.
- Find both play-safe strategies and test for a stable solution.
- Reduce a matrix using dominance arguments.
Open the full revision checklist to see every objective in the course in one place.
No animated video for this topic yet; these notes stand alone.