Lesson 11: Game Theory: Two-Person Zero-Sum Games and Pure Strategies¶
11.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Define a two-person zero-sum game and construct its payoff matrix.
- Apply the maximin and minimax criteria.
- Identify a saddle point and the value of the game.
- Apply the dominance principle to reduce a game.
- Recognise when no pure-strategy solution exists.
11.2 What Is a Game?¶
Definition. A game is a decision situation in which two or more rational participants (players) choose among strategies, and each player's payoff depends on the choices of all players.
Key elements.
| Element | Meaning |
|---|---|
| Players | the decision-makers |
| Strategies | the complete plans of action available to each |
| Payoff | the outcome to each player for each strategy combination |
| Payoff matrix | the tabulation of all payoffs |
Definition (Two-person zero-sum game). Exactly two players, and
One player's gain is exactly the other's loss. Examples: dividing a fixed market share, competitive bidding for a single contract, most parlour games.
Convention used throughout. The matrix records player A's (the row player's) payoff. A positive entry means A gains and B loses that amount.
Player A maximises; player B minimises.
What zero-sum excludes. Cooperation, side payments and mutual gain are impossible by construction. Real business rivalry is usually non-zero-sum (both firms can profit from market growth), so zero-sum models are best read as worst-case analyses of purely competitive situations.
11.3 The Maximin and Minimax Criteria¶
Both players are assumed rational and conservative: each protects against the opponent's best reply.
Player A's reasoning — maximin¶
If A plays row \(i\), the worst that can happen is \(\min_j a_{ij}\). A therefore chooses the row whose worst case is best:
\(\underline{v}\) is A's guaranteed minimum gain, whatever B does.
Player B's reasoning — minimax¶
If B plays column \(j\), the worst for B is \(\max_i a_{ij}\) (A's largest gain). B chooses the column minimising this:
\(\overline{v}\) is B's guaranteed maximum loss.
The fundamental inequality¶
Theorem. \(\underline{v} \le \overline{v}\) always.
Proof. For any \(i_0, j_0\): \(\min_j a_{i_0 j} \le a_{i_0j_0} \le \max_i a_{ij_0}\). Taking the maximum over \(i_0\) on the left and the minimum over \(j_0\) on the right preserves the inequality. \(\blacksquare\)
11.4 Saddle Points and the Value of the Game¶
Definition (Saddle point). A cell \((r,s)\) is a saddle point if
— it is simultaneously the smallest in its row and the largest in its column.
Theorem. A saddle point exists iff \(\underline{v} = \overline{v}\), and then
The pair (row \(r\), column \(s\)) is the optimal pure strategy for A and B respectively, and it is an equilibrium: neither player can gain by unilaterally deviating.
Terminology.
| Condition | Name |
|---|---|
| \(v > 0\) | the game favours A |
| \(v < 0\) | the game favours B |
| \(v = 0\) | the game is fair |
| saddle point exists | strictly determined game; pure strategies suffice |
| no saddle point | mixed strategies are required (L12) |
The procedure¶
1. Compute the ROW MINIMA; maximin = the largest of them
2. Compute the COLUMN MAXIMA; minimax = the smallest of them
3. If maximin = minimax -> SADDLE POINT at that cell; v = that value
4. Otherwise -> no pure-strategy solution; use mixed strategies (L12)
11.5 The Dominance Principle¶
Definition (Row dominance). Row \(i\) dominates row \(k\) if
Row \(i\) is at least as good as row \(k\) against every opponent choice, so row \(k\) may be deleted — a rational A would never play it.
Definition (Column dominance). Column \(j\) dominates column \(l\) if
(Note the reversal: B minimises, so a smaller entry is better for B.) Column \(l\) may be deleted.
The direction of the inequality is the single most common error. Remember: A wants big, B wants small. A keeps the row with larger entries; B keeps the column with smaller entries.
Generalised (convex) dominance. A row may also be deleted if it is dominated by a convex combination (an average) of other rows:
Why dominance matters. It reduces the matrix, often to \(2\times2\), where a closed-form solution exists (L12).
11.6 Solved Problems¶
Problem 1 — Finding a saddle point¶
Solve the game with payoff matrix (A's gains):
| A \ B | \(B_1\) | \(B_2\) | \(B_3\) | \(B_4\) |
|---|---|---|---|---|
| \(A_1\) | 9 | 3 | 1 | 8 |
| \(A_2\) | 6 | 5 | 4 | 6 |
| \(A_3\) | 2 | 4 | 3 | 3 |
| \(A_4\) | 5 | 6 | 2 | 2 |
Solution.
Step 1 — row minima.
| Row | Entries | Minimum |
|---|---|---|
| \(A_1\) | 9, 3, 1, 8 | 1 |
| \(A_2\) | 6, 5, 4, 6 | 4 ← maximum |
| \(A_3\) | 2, 4, 3, 3 | 2 |
| \(A_4\) | 5, 6, 2, 2 | 2 |
Step 2 — column maxima.
| Column | Entries | Maximum |
|---|---|---|
| \(B_1\) | 9, 6, 2, 5 | 9 |
| \(B_2\) | 3, 5, 4, 6 | 6 |
| \(B_3\) | 1, 4, 3, 2 | 4 ← minimum |
| \(B_4\) | 8, 6, 3, 2 | 8 |
Step 3 — test.
Verify the saddle-point property. The entry \(a_{23} = 4\) is:
- the smallest in row \(A_2\): \(\min(6,5,4,6) = 4\) ✓
- the largest in column \(B_3\): \(\max(1,4,3,2) = 4\) ✓
Verify the equilibrium. Neither player benefits from deviating alone.
If A deviates (B still plays \(B_3\)): \(A_1\) gives 1, \(A_3\) gives 3, \(A_4\) gives 2 — all less than 4. A loses by deviating ✓.
If B deviates (A still plays \(A_2\)): \(B_1\) gives 6, \(B_2\) gives 5, \(B_4\) gives 6 — all more than 4, and B is paying these. B loses by deviating ✓.
Interpretation. The game favours A (\(v = 4 > 0\)): A can guarantee a gain of 4 units per play regardless of B's actions, and B can hold the loss to exactly 4.
Problem 2 — No saddle point¶
Determine whether the following game has a pure-strategy solution.
| A \ B | \(B_1\) | \(B_2\) |
|---|---|---|
| \(A_1\) | 5 | 1 |
| \(A_2\) | 3 | 4 |
Solution.
Row minima. \(A_1: \min(5,1) = 1\); \(A_2: \min(3,4) = 3\).
Column maxima. \(B_1: \max(5,3) = 5\); \(B_2: \max(1,4) = 4\).
Test.
Why the instability arises — trace the reasoning.
- A reasons: "\(A_2\) guarantees me at least 3."
- B reasons: "Against \(A_2\), I should play \(B_1\) (paying 3, not 4)."
- A reasons: "If B plays \(B_1\), I should switch to \(A_1\) and get 5!"
- B reasons: "If A plays \(A_1\), I should switch to \(B_2\) and pay only 1."
- A reasons: "If B plays \(B_2\), I should switch back to \(A_2\) and get 4."
- …and the cycle repeats forever.
The value lies strictly between the bounds: \(3 \le v \le 4\). L12 shows the exact solution is \(v = 3.4\), with A playing \(A_1\) with probability 0.2 and \(A_2\) with probability 0.8.
The economic meaning of randomising. If A always played \(A_2\), B would learn and exploit it. Unpredictability is itself valuable — the same reason a bowler varies deliveries or a firm varies its promotional timing.
Problem 3 — Reduction by dominance to a saddle point¶
Reduce and solve.
| A \ B | \(B_1\) | \(B_2\) | \(B_3\) | \(B_4\) | \(B_5\) |
|---|---|---|---|---|---|
| \(A_1\) | 6 | 3 | 1 | 0 | 3 |
| \(A_2\) | 3 | 2 | 4 | 2 | 4 |
| \(A_3\) | 1 | 2 | 3 | 2 | 2 |
| \(A_4\) | 3 | 3 | 1 | 2 | 3 |
Solution.
Step 1 — column dominance (B minimises, so B keeps SMALL entries).
Compare \(B_4\) and \(B_2\): entries \((0,2,2,2)\) versus \((3,2,2,3)\). Since \(0\le3\), \(2\le2\), \(2\le2\), \(2\le3\) — \(B_4\) dominates \(B_2\) (every entry is \(\le\)).
Compare \(B_4\) and \(B_5\): \((0,2,2,2)\) versus \((3,4,2,3)\). Every entry of \(B_4\) is \(\le\) ⟹ delete \(B_5\).
Compare \(B_4\) and \(B_1\): \((0,2,2,2)\) versus \((6,3,1,3)\). Here \(2 > 1\) in row 3, so no dominance — keep \(B_1\).
After column reduction:
| A \ B | \(B_1\) | \(B_3\) | \(B_4\) |
|---|---|---|---|
| \(A_1\) | 6 | 1 | 0 |
| \(A_2\) | 3 | 4 | 2 |
| \(A_3\) | 1 | 3 | 2 |
| \(A_4\) | 3 | 1 | 2 |
Step 2 — row dominance (A maximises, so A keeps LARGE entries).
Compare \(A_2 = (3,4,2)\) with \(A_3 = (1,3,2)\): \(3\ge1\), \(4\ge3\), \(2\ge2\) ⟹ \(A_2\) dominates \(A_3\).
Compare \(A_2 = (3,4,2)\) with \(A_4 = (3,1,2)\): \(3\ge3\), \(4\ge1\), \(2\ge2\) ⟹ \(A_2\) dominates \(A_4\).
After row reduction:
| A \ B | \(B_1\) | \(B_3\) | \(B_4\) |
|---|---|---|---|
| \(A_1\) | 6 | 1 | 0 |
| \(A_2\) | 3 | 4 | 2 |
Step 3 — column dominance again. Compare \(B_4 = (0,2)\) with \(B_3 = (1,4)\): both entries smaller ⟹ delete \(B_3\). Compare \(B_4 = (0,2)\) with \(B_1 = (6,3)\): both smaller ⟹ delete \(B_1\).
| A \ B | \(B_4\) |
|---|---|
| \(A_1\) | 0 |
| \(A_2\) | 2 |
Step 4 — solve. A picks the larger: \(A_2\) with payoff 2.
Verify against the ORIGINAL matrix.
Row minima: \(A_1: 0\), \(A_2: \mathbf{2}\), \(A_3: 1\), \(A_4: 1\) ⟹ maximin \(= 2\). Column maxima: \(B_1: 6\), \(B_2: 3\), \(B_3: 4\), \(B_4: \mathbf{2}\), \(B_5: 4\) ⟹ minimax \(= 2\).
Dominance gave the right answer while reducing a \(4\times5\) matrix to \(2\times1\). On larger games this reduction is what makes hand solution feasible at all.
Problem 4 — Convex (generalised) dominance¶
Show that row \(A_3\) can be deleted from the following, even though no single row dominates it.
| A \ B | \(B_1\) | \(B_2\) | \(B_3\) |
|---|---|---|---|
| \(A_1\) | 8 | 2 | 4 |
| \(A_2\) | 2 | 8 | 4 |
| \(A_3\) | 4 | 4 | 3 |
Solution.
No simple dominance.
- \(A_1\) vs \(A_3\): \(8\ge4\) ✓ but \(2 < 4\) ✗ — no dominance.
- \(A_2\) vs \(A_3\): \(2 < 4\) ✗ — no dominance.
Try the average of \(A_1\) and \(A_2\) (i.e. \(\lambda_1 = \lambda_2 = \tfrac12\)):
Compare with \(A_3 = (4, 4, 3)\):
Why this is legitimate. A can achieve the payoff vector \((5,5,4)\) by randomising 50–50 between \(A_1\) and \(A_2\). Since that mixture beats \(A_3\) against every column, a rational A would never place positive probability on \(A_3\).
Reduced game.
| A \ B | \(B_1\) | \(B_2\) | \(B_3\) |
|---|---|---|---|
| \(A_1\) | 8 | 2 | 4 |
| \(A_2\) | 2 | 8 | 4 |
Continue with column dominance. \(B_3 = (4,4)\) against \(B_1 = (8,2)\): \(4 \le 8\) ✓ but \(4 > 2\) ✗ — no dominance. Against \(B_2 = (2,8)\): \(4 > 2\) ✗ — no dominance.
So the game reduces to \(2\times3\) and requires the graphical method of L13.
Checking for a saddle point. Row minima: \(A_1: 2\), \(A_2: 2\) ⟹ maximin \(= 2\). Column maxima: \(8, 8, 4\) ⟹ minimax \(= 4\). Since \(2 \ne 4\), mixed strategies are needed.
(By symmetry, A will play \(A_1\) and \(A_2\) with probability \(\frac12\) each, guaranteeing \(\min(5,5,4) = 4\) — and B will play \(B_3\), giving \(v = 4\).)
Problem 5 — A business application of the maximin criterion¶
Two firms compete for a market. Firm A chooses an advertising level (Low, Medium, High); firm B does the same. The matrix gives A's market-share gain (percentage points).
| A \ B | Low | Medium | High |
|---|---|---|---|
| Low | 0 | −3 | −6 |
| Medium | 4 | 1 | −2 |
| High | 7 | 3 | −1 |
Analyse and advise firm A.
Solution.
Step 1 — saddle-point test.
Row minima: Low \(= -6\); Medium \(= -2\); High \(= -1\) ← maximum.
Column maxima: Low \(= 7\); Medium \(= 3\); High \(= -1\) ← minimum.
Step 2 — check the dominance structure. Notice that for firm A:
- High dominates Medium: \(7\ge4\), \(3\ge1\), \(-1\ge-2\) ✓
- High dominates Low: \(7\ge0\), \(3\ge-3\), \(-1\ge-6\) ✓
High is a strictly dominant strategy for A — best regardless of what B does.
By the symmetry of the situation, High is dominant for B as well (B's column maxima are minimised by High).
Step 3 — the strategic interpretation.
- Both firms are compelled to advertise High, because it is individually dominant.
- But compare the outcomes: at (Low, Low) the payoff is 0 — no share change, and both firms save the cost of heavy advertising. At (High, High) the payoff is \(-1\) plus both firms have incurred the full advertising expense.
- The equilibrium is worse for both than the cooperative outcome — yet neither can move to it unilaterally, because deviating to Low against a High opponent costs \(-6\).
Advice to firm A.
-
In the zero-sum framing, play High. It is dominant, and it limits the loss to 1 point.
-
But question the framing. The zero-sum model captures only share, not profit. If both firms spend heavily on advertising, total industry profit falls — this is genuinely a non-zero-sum situation, and the model is understating the cost of the arms race.
-
The real strategic options lie outside the matrix. Change the game rather than play it better:
- Product differentiation, so the firms are no longer competing for the same share;
- Industry advertising standards or a joint category-building campaign (subject to competition law);
- Signalling restraint — repeated interaction can sustain cooperation, which a one-shot model cannot capture.
-
The \(-1\) deserves scrutiny. A loses 1 point at equilibrium, meaning B has a structural advantage — perhaps better brand recognition. A should investigate why the payoffs are asymmetric, since fixing that changes every entry in the table.
11.7 Practice Problems¶
- Find the saddle point: \(\begin{pmatrix}1&7&3\\5&6&4\\7&2&0\end{pmatrix}\). [Ans: \((2,3)\), \(v = 4\)]
- Does \(\begin{pmatrix}2&4\\6&3\end{pmatrix}\) have a saddle point? [Ans: no — maximin 3, minimax 4]
- Reduce by dominance: \(\begin{pmatrix}4&2&3\\5&6&7\\1&0&2\end{pmatrix}\). [Ans: row 2 dominates rows 1 and 3; \(v = 5\)]
- State the direction of column dominance and explain why.
- Prove \(\underline{v}\le\overline{v}\).
- A game has \(v = 0\). What is it called, and what does it mean? [Ans: fair]
- Show that a \(2\times2\) game with entries \(a > b\), \(c < d\), \(a > c\), \(b < d\) has no saddle point.
11.8 Summary¶
- A two-person zero-sum game has one player's gain exactly equal to the other's loss; the matrix records the row player's payoff. A maximises, B minimises.
- Maximin \(\underline{v} = \max_i\min_j a_{ij}\) is A's guarantee; minimax \(\overline{v} = \min_j\max_i a_{ij}\) is B's. Always \(\underline{v}\le\overline{v}\).
- A saddle point exists iff \(\underline{v} = \overline{v}\), and then \(v\) is the value of the game and the pure strategies form an equilibrium — neither player gains by deviating alone.
- \(v>0\) favours A, \(v<0\) favours B, \(v=0\) is fair.
- Dominance: A deletes rows with uniformly smaller entries; B deletes columns with uniformly larger entries. Convex dominance allows a mixture of rows to dominate another.
- No saddle point ⟹ mixed strategies are required (L12); the players must randomise, because any predictable pure strategy is exploitable.
- The most valuable use of a game model is often diagnostic — recognising a prisoner's-dilemma structure, or that the zero-sum framing itself is wrong.
Next lesson: L12 — Mixed strategies and the odds method.
Practise now: unit2-games-networks-lab.html → Game Solver: enter any payoff matrix and see row
minima, column maxima, saddle-point detection and step-by-step dominance reduction.