Skip to content

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:

  1. Define a two-person zero-sum game and construct its payoff matrix.
  2. Apply the maximin and minimax criteria.
  3. Identify a saddle point and the value of the game.
  4. Apply the dominance principle to reduce a game.
  5. 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

\[ \text{(payoff to A)} + \text{(payoff to B)} = 0 \qquad\text{for every outcome.} \]

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.

\[ A = \begin{pmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & & \vdots\\ a_{m1} & \cdots & a_{mn}\end{pmatrix}, \qquad a_{ij} = \text{A's gain when A plays } i \text{ and B plays } j \]

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:

\[ \boxed{\ \underline{v} \ =\ \max_i\ \min_j\ a_{ij} \qquad \text{(the \textbf{maximin} or \emph{lower value})}\ } \]

\(\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:

\[ \boxed{\ \overline{v} \ =\ \min_j\ \max_i\ a_{ij} \qquad \text{(the \textbf{minimax} or \emph{upper value})}\ } \]

\(\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

\[ a_{rs} = \min_j a_{rj} = \max_i a_{is} \]

— 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

\[ \boxed{\ v \ =\ \underline{v} \ =\ \overline{v} \ =\ a_{rs} \qquad \text{— the \textbf{value of the game}}\ } \]

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

\[ a_{ij} \ \ge\ a_{kj} \qquad \text{for every } j \]

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

\[ a_{ij} \ \le\ a_{il} \qquad \text{for every } i \]

(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:

\[ a_{kj} \ \le\ \sum_{i\ne k}\lambda_i a_{ij} \ \ \forall j, \qquad \lambda_i\ge0,\ \sum\lambda_i = 1 \]

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
\[ \underline{v} = \text{maximin} = \max\{1, 4, 2, 2\} = \mathbf{4} \ \text{ in row } A_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
\[ \overline{v} = \text{minimax} = \min\{9, 6, 4, 8\} = \mathbf{4} \ \text{ in column } B_3 \]

Step 3 — test.

\[ \underline{v} = \overline{v} = 4 \ \Longrightarrow\ \textbf{SADDLE POINT at } (A_2, B_3) \]
\[ \boxed{\ \text{A plays } A_2,\quad \text{B plays } B_3,\quad v = 4\ } \]

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\).

\[ \underline{v} = \max(1, 3) = \mathbf{3} \]

Column maxima. \(B_1: \max(5,3) = 5\); \(B_2: \max(1,4) = 4\).

\[ \overline{v} = \min(5, 4) = \mathbf{4} \]

Test.

\[ \underline{v} = 3 \ne 4 = \overline{v} \]
\[ \boxed{\ \textbf{NO SADDLE POINT — no pure-strategy solution exists.}\ } \]

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.
\[ \boxed{\ \textbf{No stable pure-strategy pair exists. The players must RANDOMISE.}\ } \]

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\)).

\[ \textbf{Delete } B_2 . \]

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\).

\[ \textbf{Delete } 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\).

\[ \textbf{Delete } 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.

\[ \boxed{\ \text{A plays } A_2,\quad \text{B plays } B_4,\quad v = 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\).

\[ \underline{v} = \overline{v} = 2 \ \checkmark \ \textbf{ — saddle point at } (A_2, B_4). \]

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\)):

\[ \tfrac12 A_1 + \tfrac12 A_2 = \left(\tfrac{8+2}{2},\ \tfrac{2+8}{2},\ \tfrac{4+4}{2}\right) = (5,\ 5,\ 4) \]

Compare with \(A_3 = (4, 4, 3)\):

\[ 5 \ge 4 \ \checkmark, \qquad 5\ge4 \ \checkmark, \qquad 4\ge3 \ \checkmark \]
\[ \boxed{\ \textbf{The mixture } \tfrac12A_1+\tfrac12A_2 \textbf{ dominates } A_3 \ \Longrightarrow\ \textbf{delete } A_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.

\[ \underline{v} = \mathbf{-1} \]

Column maxima: Low \(= 7\); Medium \(= 3\); High \(= -1\) ← minimum.

\[ \overline{v} = \mathbf{-1} \]
\[ \underline{v} = \overline{v} = -1 \ \Longrightarrow\ \textbf{SADDLE POINT at (High, High)} \]
\[ \boxed{\ \text{Both firms advertise HIGH; } v = -1 \text{ — firm A LOSES 1 percentage point.}\ } \]

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.

\[ \boxed{\ \textbf{This is a PRISONER'S DILEMMA structure.}\ } \]
  • 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.

  1. In the zero-sum framing, play High. It is dominant, and it limits the loss to 1 point.

  2. 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.

  3. 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.
  4. 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.

\[ \boxed{\ \textbf{The most valuable use of a game model is often to reveal that you are playing the wrong game.}\ } \]

11.7 Practice Problems

  1. Find the saddle point: \(\begin{pmatrix}1&7&3\\5&6&4\\7&2&0\end{pmatrix}\). [Ans: \((2,3)\), \(v = 4\)]
  2. Does \(\begin{pmatrix}2&4\\6&3\end{pmatrix}\) have a saddle point? [Ans: no — maximin 3, minimax 4]
  3. 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\)]
  4. State the direction of column dominance and explain why.
  5. Prove \(\underline{v}\le\overline{v}\).
  6. A game has \(v = 0\). What is it called, and what does it mean? [Ans: fair]
  7. 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.