Topics Covered

On this page

1. 1. Introduction to Game Theory
2. 2. Two-Person Zero-Sum Games
3. 3. Maxmin and Minimax Principles
4. 4. Saddle Point and Pure-Strategy Solution
5. 5. Mixed Strategies and Games Without Saddle Point
6. 6. 2 × 2 Games Without Saddle Point
7. 7. Dominance Property
8. 8. Graphical Method for 2 × n and m × 2 Games
9. 9. Relation to Linear Programming
10. Summary Workflow
11. Key Take-aways

1. Introduction to Game Theory

Key Terminology

• Player — a decision-maker.
• Strategy — a complete plan of action by a player.
• Pure strategy — a single specific action.
• Mixed strategy — a probability distribution over the player's pure strategies.
• Payoff — the gain (or loss) a player receives for a given combination of strategies.
• Payoff matrix — a table showing the payoffs for every combination of strategies.
• Optimum strategy — the strategy yielding the best result given the opponent plays optimally.
• Value of the game (v) — the expected payoff when both players play their optimum strategies.

2. Two-Person Zero-Sum Games

Payoff Matrix Convention

Without loss of generality, the payoff matrix shows the gain of player A (the maximiser). Player B is the minimiser — chooses columns to minimise A's gain.

If A has \(m\) strategies and B has \(n\) strategies, the matrix is \(m \times n\):

	B₁	B₂	…	Bₙ
A₁	a₁₁	a₁₂	…	a₁ₙ
A₂	a₂₁	a₂₂	…	a₂ₙ
⋮	⋮	⋮		⋮
Aₘ	aₘ₁	aₘ₂	…	aₘₙ

\(a_{ij}\) is what A receives (and B loses) when A plays Aᵢ and B plays Bⱼ.

3. Maxmin and Minimax Principles

Maxmin (Player A)

Minimax (Player B)

In every game: \(v_L \le v_U\). If \(v_L = v_U\), the game has a saddle point and a value \(v = v_L = v_U\).

4. Saddle Point and Pure-Strategy Solution

How to Find a Saddle Point

1. Mark the minimum of each row (in the right margin).
2. Mark the maximum of each column (at the bottom).
3. If the largest row-minimum equals the smallest column-maximum, that common entry is the saddle point.

5. Mixed Strategies and Games Without Saddle Point

If a game has no saddle point (\(v_L < v_U\)), neither player can commit to a single pure strategy. Instead they should use mixed strategies: choose each strategy with a certain probability.

Mixed-Strategy Formulation

Let A play strategy Aᵢ with probability \(p_i\) (with \(\sum p_i = 1\)) and B play Bⱼ with probability \(q_j\) (with \(\sum q_j = 1\)). The expected payoff to A is:

A chooses \(p\) to maximise \(E\); B chooses \(q\) to minimise \(E\). Von Neumann's Minimax Theorem guarantees the optimal value exists and is the same for both players.

6. 2 × 2 Games Without Saddle Point

For a 2 × 2 game without a saddle point:

	B₁	B₂
A₁	a	b
A₂	c	d

Let A play A₁ with probability \(p\) and A₂ with probability \(1 - p\); B plays B₁ with probability \(q\) and B₂ with probability \(1 - q\).

Optimum Strategies

(Provided the denominator is non-zero. Sign convention: A is the maximiser.)

7. Dominance Property

Dominance Rules

1. Row dominance: if every entry of row \(i\) is ≥ the corresponding entry of row \(k\), then A will never play row \(k\) (it's dominated by row \(i\)). Delete row \(k\).
2. Column dominance: if every entry of column \(j\) is ≤ the corresponding entry of column \(l\), then B will never play column \(l\) (dominated). Delete column \(l\).
3. Convex (mixed) dominance: if some convex combination of two rows dominates a third, the third can be deleted. Same idea for columns.

Apply dominance repeatedly. The reduced matrix may have a saddle point or become 2 × 2 (solvable by formula) or 2 × n / m × 2 (graphical method).

8. Graphical Method for 2 × n and m × 2 Games

2 × n Game (A has 2 strategies)

A plays A₁ with probability \(p\) and A₂ with probability \(1 - p\). For each column \(j\), A's expected payoff against pure strategy \(B_j\) is:

This is a linear function of \(p\) on \([0, 1]\). Plot all \(n\) lines on the same diagram.

For each \(p\), B will choose the column that minimises A's payoff — the lower envelope of the lines. A wants to maximise this lower envelope. The optimum \(p^*\) is at the highest point of the lower envelope.

Procedure

1. Draw axis: x from 0 to 1 representing \(p\); y = expected payoff.
2. For each column \(j\), draw the line \(E_j(p)\) from (0, \(a_{2j}\)) to (1, \(a_{1j}\)).
3. Sketch the lower envelope (the minimum across all lines).
4. Find the highest point of the envelope — this gives \(p^*\) and \(v\).
5. Two lines pass through that point — those two columns are B's active strategies. Solve the 2×2 sub-game.

m × 2 Game (B has 2 strategies)

Symmetric: plot \(E_i(q)\) as a function of \(q\) for each row, find the upper envelope, and locate its lowest point (B is minimiser).

9. Relation to Linear Programming

Every two-person zero-sum game can be formulated as a linear program. For an \(m \times n\) game with all positive entries (if not, add a constant to make them positive), A's LP is:

B's LP is the dual. By LP duality, both LPs have the same optimum value — the value of the game.

Summary Workflow

1. Identify A as maximiser, B as minimiser. Write payoff matrix for A.
2. Check for saddle point: compute row minima and column maxima.
3. If saddle point exists ⇒ pure strategies; value = saddle entry.
4. If not, apply dominance to reduce.
5. If reduced to 2×2, use the closed-form formula.
6. If 2×n or m×2 after reduction, use graphical method.
7. For larger matrices, set up as LP.

Key Take-aways

• Two-person zero-sum: A's gain = B's loss; payoff matrix is from A's perspective.
• Maxmin ≤ Minimax; equality ⇒ saddle point ⇒ pure-strategy solution.
• 2×2 without saddle point: closed-form formulas for \(p, q, v\).
• Dominance: delete dominated rows / columns to reduce matrix size.
• Graphical method handles 2×n / m×2 games via upper/lower envelopes.
• General m×n games solvable by linear programming.