Zero-Sum Games (AQA A-Level Further Maths): Revision Notes
Zero-Sum Games
Introduction to zero-sum games
In game theory, a zero-sum game is a special type of competitive scenario involving two players or teams. The defining characteristic is that one player's gain is exactly balanced by the other player's loss. This means the total amount won and lost across both players always adds up to zero.
For example, if you and a friend play a game where the winner receives $5 from the loser, this is a zero-sum game. When you win $5, your friend loses $5, so the net change is $5 + (-$5) = $0.
Definition: In a zero-sum game, the sum of the gains made by the players on each play is zero.
Zero-sum games are useful for modelling competitive situations where there's a fixed resource being contested, such as card games, certain business competitions, or military conflicts.
Understanding payoff matrices
To analyse zero-sum games, we use a payoff matrix. This is a table that shows the outcome (or payoff) for each possible combination of strategies that the two players might choose.
Let's consider a card game where two players, A and B, each play either a king (K), queen (Q), or jack (J). Depending on the cards played, one player pays the other an agreed amount.
In the complete payoff table above, each cell contains an ordered pair (x, y) where x represents player A's gain and y represents player B's gain. Notice that these values always sum to zero, confirming this is a zero-sum game.
For zero-sum games, we can simplify the matrix by showing only one player's payoffs. It's conventional to show the gains of the row player (the player whose strategies are listed in the rows).
Definition: A payoff matrix records the gains of the row player for each possible combination of strategies. The row player is the player listed on the left side of the table.
After simplification, the payoff matrix for player A becomes:
| B | |||
|---|---|---|---|
| K | Q | J | |
| A | K | 5 | -4 |
| Q | 3 | 1 | |
| J | 2 | 3 |
In this simplified matrix, positive numbers represent gains for player A (and equivalent losses for player B), while negative numbers represent losses for player A (and equivalent gains for player B).
Play-safe strategies
Each player wants to choose a strategy that guarantees them the best possible outcome, regardless of what their opponent does. This is called a play-safe strategy.
Finding player A's play-safe strategy (maximin)
Player A (the row player) should consider the worst-case scenario for each of their strategies. This means finding the minimum value in each row:
For player A:
- If she plays a king, the worst outcome is losing 4p (when B plays a queen)
- If she plays a queen, the worst outcome is winning 1p (her minimum gain is 1p)
- If she plays a jack, the worst outcome is losing 1p
To play safe, player A should choose the strategy with the best worst-case outcome. This means choosing the maximum of these minimum values, giving her a guaranteed gain of at least 1p.
Definition: A play-safe strategy gives the best guaranteed outcome regardless of what the other player does.
Player A's play-safe strategy is to play a queen, which gives the best guaranteed outcome (winning 1p). This is called a maximin strategy because it maximises her minimum gain.
Memory aid: Row player = Rows = Maximin (MAX-imise the MIN-imum)
Finding player B's play-safe strategy (minimax)
Player B (the column player) needs to analyse the matrix from his perspective. Remember that the payoff matrix shows player A's gains, so player B wants to minimise these values.
For each of player B's strategies (columns), we find the maximum value (which represents player B's worst-case scenario):
For player B:
- If he plays a king, the worst outcome is that he loses 5p (when A plays a king)
- If he plays a queen, the worst outcome is that he loses 3p (when A plays a jack)
- If he plays a jack, the worst outcome is that he loses 4p (when A plays a queen)
Player B's play-safe strategy is to choose the minimum of these maximum values, which means playing a queen (losing at most 3p).
Definition: Player B uses a minimax strategy because he minimises his maximum loss.
Memory aid: Column player = Columns = Minimax (MIN-imise the MAX-imum)
Stable solutions and saddle points
When both players use their play-safe strategies, we need to check whether the game has a stable solution.
In the example above:
- Player A's play-safe strategy is to play Q (maximin = 1)
- Player B's play-safe strategy is to play Q (minimax = 3)
- Maximum of row minima = 1
- Minimum of column maxima = 3
- Since 1 ≠ 3, the solution is not stable
This means if player A knows that player B intends to play a queen, she could change her strategy to playing a jack instead, winning 3p instead of 1p. This shows the solution is unstable.
Definition: A game has a stable solution if neither player can gain by changing from their play-safe strategy.
Key rule: A game has a stable solution if:
When this condition is met, the game has what's called a saddle point.
Example of a stable solution
Consider this modified payoff matrix:
| B | ||||
|---|---|---|---|---|
| K | Q | J | Row minimum | |
| A | K | 4 | 2 | -4 |
| Q | 3 | 4 | 2 | |
| J | 2 | -2 | 1 | |
| Column maximum | 4 | 4 | 2 |
Finding the play-safe strategies:
- Maximum of row minima = 2 (player A plays Q)
- Minimum of column maxima = 2 (player B plays J)
- Since max of row minima = min of column maxima = 2, the game has a stable solution
Neither player can improve by changing strategy. If player A plays Q and player B plays J, player A wins 2p. If either player changes their strategy, they either stay the same or do worse.
Definition: The value of the game is the payoff to the row player when both players use their best strategy.
In this stable solution, the value of the game is 2p to player A (or -2p to player B).
Definition: A pure-strategy game occurs when both players use their play-safe strategy every time. A stable solution means the game can be played as a pure-strategy game.
The stable solution can also be called a saddle point because the value sits at the intersection where it's the lowest value in its row and the highest value in its column, like the centre of a horse's saddle.
Simplifying games using dominance
Some strategies should never be used by rational players because they're always worse than alternative strategies. We can eliminate these dominated strategies to simplify the payoff matrix.
Row dominance
Definition: Row i dominates row j if, for every column, the value in row i ≥ value in row j.
This means strategy i is always at least as good as strategy j for the row player, so strategy j should never be used.
Column dominance
Definition: Column i dominates column j if, for every row, the value in column i ≤ value in column j.
This means strategy i is always at least as good as strategy j for the column player (remember, smaller values are better for the column player since they represent smaller losses).
Memory aid for dominance:
- Row dominance: bigger is better (≥)
- Column dominance: smaller is better (≤)
Key exam tip
When checking dominance, always remember:
- For rows: look for the strategy with higher (or equal) values across all columns
- For columns: look for the strategy with lower (or equal) values across all rows
- You can eliminate rows and columns iteratively - after removing one, check again for new dominance relationships
Worked examples
Worked Example 1: Finding a Stable Solution
Consider this payoff matrix for players A and B:
| B | ||||
|---|---|---|---|---|
| A | 8 | 6 | 9 | |
| 4 | 3 | -2 | ||
| 10 | -1 | 1 |
Show that the game has a stable solution and find the value of the game.
Solution:
Step 1: Find the row minima and identify the maximum of row minima.
| B | |||||
|---|---|---|---|---|---|
| Row min | |||||
| A | 8 | 6 | 9 | 6 | |
| 4 | 3 | -2 | 2 | ||
| 10 | -1 | 1 | 5 |
Maximum of row minima = 6
Therefore, A's play-safe strategy is .
Step 2: Find the column maxima and identify the minimum of column maxima.
| B | |||||
|---|---|---|---|---|---|
| Row min | |||||
| A | 8 | 6 | 9 | 6 | |
| 4 | 3 | -2 | 2 | ||
| 10 | -1 | 1 | 5 | ||
| Column max | 10 | 6 | 9 | 6 |
Minimum of column maxima = 6
Therefore, B's play-safe strategy is either or (both give the same result).
Step 3: Check for stability.
Maximum of row minima = 6 Minimum of column maxima = 6
Since these are equal, the game has a stable solution.
The value of the game is 6 (to player A).
Both players should use their play-safe strategies: A plays , and B plays either or .
Worked Example 2: Using Dominance to Simplify a Game
Let's work through this systematic approach to simplifying a game using dominance.
Given payoff matrix:
| B | ||||
|---|---|---|---|---|
| A | 2 | 1 | 3 | |
| 3 | -1 | -8 |
Step 1: Check for row dominance.
Looking at the rows, we can see that for every column:
- gives values: 2, 1, 3, 5
- gives values: 3, -1, -8, 4
Row does not dominate (since 3 > 2, but -1 < 1, -8 < 3, and 4 < 5). Row does not dominate either (since 2 < 3).
So we cannot eliminate any rows yet. Let's check columns.
Step 2: Check for column dominance.
For the column player (B), smaller values are better. Column dominates column because:
- In row : 3 < 5 ✓
- In row : -8 < 4 ✓
Therefore, we can eliminate column .
After eliminating column 4:
| B | |||
|---|---|---|---|
| A | 2 | 1 | |
| 3 | -1 |
Step 3: Check again for dominance.
Now checking rows: Row dominates row because:
- Column : 2 < 3 (not dominating)
- Column : 1 > -1 ✓
- Column : 3 > -8 ✓
Actually, doesn't dominate since not all values are greater or equal. Since 2 < 3, this doesn't work.
Checking if dominates :
- Column : 3 > 2 ✓
- Column : -1 < 1 ✗
No row dominance.
Without loss of generality, the step-by-step process shown in the image indicates:
- First, row 3 dominates row 1, so delete row 1
- Then column 3 dominates column 4, so delete column 4
- Then row 1 dominates row 2, so delete row 2
- Finally, column 2 dominates column 1
This eventually reduces to a single cell, showing:
- A's play-safe strategy is
- B's play-safe strategy is
Step 4: Find row minima and column maxima to check stability.
After full simplification, we find:
- Max of row minima = 3
- Min of column maxima = 5
- Since 3 ≠ 5, the solution is not stable
Worked Example 3: Complete Dominance Analysis
Use dominance to simplify this payoff matrix as far as possible:
| B | |||
|---|---|---|---|
| A | 5 | 3 | |
| -2 | 7 |
Solution:
Step 1: Check for row dominance.
- Row : 5, 3, 3
- Row : -2, 7, -1
Neither row dominates the other (5 > -2, but 3 < 7).
Step 2: Check for column dominance.
For column player B (smaller is better):
- Compare and : In row : 5 > 3; In row : -2 < 7. So doesn't dominate .
- Compare and : In row : 5 > 3; In row : -2 < -1. So doesn't dominate .
- Compare and : In row : 3 = 3; In row : 7 > -1. So column dominates column .
Eliminate column :
| B | ||
|---|---|---|
| A | 5 | |
| -2 |
Step 3: Check for row dominance in reduced matrix.
- Row : 5, 3
- Row : -2, -1
Row dominates row because 5 > -2 and 3 > -1.
Eliminate row :
| B | ||
|---|---|---|
| A | 5 |
Step 4: Check for column dominance in reduced matrix.
For player B: 5 > 3, so column dominates column .
Eliminate column :
| B | |
|---|---|
| A |
Conclusion: There is a stable solution.
- Player A always plays strategy
- Player B always plays strategy
- The value of the game is 3
Exam tips and common mistakes
Common Mistakes to Avoid:
-
Don't confuse row and column dominance: Remember that for the row player, larger values are better, so a dominating row must have all values ≥ the dominated row. For the column player, smaller values are better, so a dominating column must have all values ≤ the dominated column.
-
Check stability carefully: Always verify that the maximum of row minima equals the minimum of column maxima before concluding a game has a stable solution.
-
Eliminate iteratively: After removing a dominated strategy, always check again for new dominance relationships. A strategy that wasn't dominated before might become dominated after eliminating other strategies.
-
Show your working: In exam questions, always show:
- Row minima and the maximum of these
- Column maxima and the minimum of these
- Clear statement of play-safe strategies
- Explicit check for stability
- The value of the game (if stable)
-
Value of the game: Remember that the stated value of a game is always from the row player's perspective. If asked for the column player's value, it will be the negative of the row player's value.
Remember!
Key Points to Remember:
-
A zero-sum game means one player's gain equals the other's loss - the total always sums to zero.
-
The payoff matrix shows the row player's gains. Positive values mean the row player wins; negative values mean they lose.
-
Play-safe strategies are found by:
- Row player uses maximin - maximise the minimum gain
- Column player uses minimax - minimise the maximum loss
-
A game has a stable solution (saddle point) when: This is the value of the game.
-
Use dominance to simplify games:
- Eliminate rows with consistently worse values for player A
- Eliminate columns with consistently higher values for player B
- Always check for new dominance after each elimination