Game theory

Why it matters

Pricing against a rival, bidding for a contract, or choosing an advertising plan when a competitor reacts are decisions where the outcome depends on someone else's choice. Game theory gives the best strategy when the opponent is intelligent and opposed to you. In the OR syllabus the focus is the two-person zero-sum game, which can be solved exactly by saddle points, dominance, mixed-strategy formulas, a graph, or linear programming.

Key ideas

Two-person zero-sum game. Two players, each with a finite set of strategies. The payoff matrix gives the gain of the row player A for every pair of choices; B's gain is the negative of it, so whatever A wins B loses. A wants to maximise the payoff, B to minimise it. Both know the matrix and choose simultaneously.

Maximin–minimax principle (pure strategies).

• For each row take the minimum; A picks the row with the largest minimum — the maximin value (lower value of the game).
• For each column take the maximum; B picks the column with the smallest maximum — the minimax value (upper value).
• Always maximin ≤ value ≤ minimax.
• If maximin = minimax, the cell is a saddle point: it is the smallest in its row and the largest in its column. The game is strictly determined, the players use pure strategies, and the value V is that entry. A game is fair if V = 0.

Mixed strategies. With no saddle point, each player randomises: A plays row i with probability pᵢ, B plays column j with probability qⱼ. The fundamental theorem (von Neumann) guarantees that optimal mixed strategies exist and both guarantee the same value V.

Dominance. Delete a row that is ≤ another row element by element (A never plays it); delete a column that is ≥ another column element by element (B never plays it). A row (column) is also dominated if it is worse than an average of other rows (columns). Reduce before solving.

Solution methods without a saddle point.

• 2 × 2: closed-form formulas below.
• 2 × n or m × 2: graphical method — plot A's expected payoff against p for each of B's columns, take the lower envelope and find its highest point; the two lines meeting there give the 2 × 2 sub-game.
• m × n in general: linear programming (the game and its LP are duals of each other).

Non-zero-sum games and Nash equilibrium. When payoffs do not sum to zero (e.g. two firms both gaining from cooperation), a Nash equilibrium is a pair of strategies in which neither player gains by changing alone. The prisoner's dilemma shows that an equilibrium can be worse for both than cooperation. A saddle point is the zero-sum special case of a Nash equilibrium.

Formulas

• Lower value: v_L = max over i of (min over j of aᵢⱼ)
• Upper value: v_U = min over j of (max over i of aᵢⱼ)
• Saddle point exists when v_L = v_U = V
• 2 × 2 game [a₁₁ a₁₂; a₂₁ a₂₂] without saddle point, with D = (a₁₁ + a₂₂) − (a₁₂ + a₂₁):
  • p₁ = (a₂₂ − a₂₁) / D, p₂ = 1 − p₁ (A's row probabilities)
  • q₁ = (a₂₂ − a₁₂) / D, q₂ = 1 − q₁ (B's column probabilities)
  • V = (a₁₁·a₂₂ − a₁₂·a₂₁) / D
• Expected payoff of A's mix against column j: Eⱼ = Σᵢ pᵢ·aᵢⱼ

Symbols: aᵢⱼ = payoff to A when A plays row i and B plays column j (₹ or units of gain); pᵢ, qⱼ = probabilities of choosing row i and column j; V = value of the game (expected payoff to A under optimal play).

Worked examples

Example 1 (saddle point). Payoff matrix to A (₹ lakh), rows A1–A4, columns B1–B5: A1 [−2, 0, 0, 5, 3]; A2 [3, 2, 1, 2, 2]; A3 [−4, −3, 0, −2, 6]; A4 [5, 3, −4, 2, −6].

1. Row minima: −2, 1, −4, −6 → maximin = 1 (row A2).
2. Column maxima: 5, 3, 1, 5, 6 → minimax = 1 (column B3).
3. Maximin = minimax = 1, so (A2, B3) is a saddle point: 1 is the smallest in row A2 and the largest in column B3.
4. A plays A2, B plays B3, V = ₹1 lakh to A. The game favours A and is not fair.

Example 2 (GATE-type: dominance, then 2 × 2 mixed strategy). Payoff to A: row A1 [5, 1, 6], row A2 [3, 4, 5], columns B1, B2, B3.

1. Saddle check: row minima 1, 3 → maximin 3; column maxima 5, 4, 6 → minimax 4. No saddle point; 3 ≤ V ≤ 4.
2. Dominance: column B3 (6, 5) ≥ column B1 (5, 3) element by element, so B never plays B3. Reduced game: [5, 1; 3, 4].
3. D = (5 + 4) − (1 + 3) = 5.
4. p₁ = (4 − 3)/5 = 0.2, p₂ = 0.8; q₁ = (4 − 1)/5 = 0.6, q₂ = 0.4, q₃ = 0.
5. V = (5 × 4 − 1 × 3)/5 = 17/5 = 3.4, which lies between 3 and 4 ✓.
6. Check A's mix against each column: B1: 0.2 × 5 + 0.8 × 3 = 3.4; B2: 0.2 × 1 + 0.8 × 4 = 3.4; B3: 0.2 × 6 + 0.8 × 5 = 5.2 ≥ 3.4 ✓.
7. A: (0.2, 0.8); B: (0.6, 0.4, 0); V = 3.4.

Common mistakes

• Taking row maxima and column minima (the reverse) when finding maximin and minimax.
• Deleting the wrong row or column in dominance: for A delete the smaller row, for B delete the larger column.
• Applying the 2 × 2 formula when a saddle point exists — the formula then gives probabilities outside 0–1 or a wrong value.
• Forgetting that the value must lie between the lower and upper values — a quick check on every answer.
• Mixing up which probabilities belong to which player in the formula.
• Treating a non-zero-sum game with zero-sum tools, or assuming a Nash equilibrium is the best joint outcome.

For GATE PI

• Identify a saddle point and the value of a pure-strategy game (very quick NAT).
• Reduce a 2 × 3 or 3 × 3 game by dominance and solve the 2 × 2 with the formulas.
• Graphical solution of a 2 × n game; expected payoff of a given mixed strategy.
• Practise the saddle-point check first on every game — it saves time.

Quick check

1. Matrix [4, 2; 6, 3]. Is there a saddle point? What is V?
2. In [2, 5; 6, 1], what is the value of the game?
3. What does V = 0 mean?
4. Column B2 has entries (7, 8) and column B1 (4, 3). Which can B delete?

Answers: 1. Yes, at (row 2, column 2); V = 3. 2. D = 3 − 11 = −8, V = (2 − 30)/(−8) = 3.5. 3. The game is fair. 4. B2 (it is larger in every row).