Lesson 12: Mixed Strategies and the Odds Method¶
12.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Define a mixed strategy and explain why randomisation is necessary.
- State the minimax theorem and its significance.
- Derive and apply the \(2\times2\) closed-form solution.
- Apply the odds (arithmetic) method as a rapid shortcut.
- Verify a mixed-strategy solution by the equalising-expectation property.
12.2 Why Randomise?¶
When no saddle point exists (L11, Problem 2), any predictable pure strategy is exploitable. The remedy is to choose probabilistically, so the opponent cannot anticipate the choice.
Definition (Mixed strategy). A mixed strategy for player A is a probability vector
where \(p_i\) is the probability of playing row \(i\). Similarly \(\vec q\) for player B over columns.
A pure strategy is the special case where one \(p_i = 1\) and the rest are 0.
Expected payoff.
12.3 The Minimax Theorem¶
Theorem (von Neumann, 1928). Every finite two-person zero-sum game has a value \(v\), and both players have optimal mixed strategies \(\vec p^{*}\), \(\vec q^{*}\) such that
Significance. In pure strategies, \(\underline v \le \overline v\) with possible strict inequality (L11). Allowing mixed strategies closes the gap always. Every finite zero-sum game is solvable.
The connection to LP. The minimax theorem is equivalent to LP duality (L07) — the row player's problem and the column player's problem are dual LPs, and strong duality is exactly \(\underline v = \overline v\). Dantzig recorded that von Neumann saw this connection immediately when Dantzig first described the simplex method to him in 1947.
The equalising property¶
Theorem. If \(\vec p^{*}\) is optimal for A, then for every column \(j\) that B uses with positive probability,
In words: an optimal mixed strategy makes the opponent indifferent among all their active choices.
Why. If some column gave B a strictly better (lower) expected payoff, B would play it with probability 1, and A's strategy would not have been optimal.
12.4 The 2×2 Solution¶
Derivation for player A¶
Let A play row 1 with probability \(p\) and row 2 with \(1-p\).
If B plays column 1: \(\quad E_1 = ap + c(1-p)\) If B plays column 2: \(\quad E_2 = bp + d(1-p)\)
Set them equal (the equalising property):
Player B¶
By the symmetric argument with \(q\) = probability of column 1:
The value¶
Substituting \(p\) into \(E_1\):
Note the numerator is \(\det A\) and the denominator is the sum of the main diagonal minus the sum of the anti-diagonal.
Validity condition. These formulas require \((a+d)-(b+c) \ne 0\) and the resulting \(p, q\) to lie in \([0,1]\). If either fails, a saddle point exists and pure strategies apply — always test for a saddle point first.
12.5 The Odds (Arithmetic) Method — the Fast Shortcut¶
For a 2x2 matrix [a b ; c d] :
1. ROW oddments: take |difference of the OTHER row's entries|
row 1 oddment = |d - c|
row 2 oddment = |a - b|
2. COLUMN oddments:
col 1 oddment = |d - b|
col 2 oddment = |a - c|
3. Probabilities = oddment / (sum of that pair's oddments)
4. Value: substitute into any expectation
This is the same algebra, arranged for speed. It is worth memorising for examinations.
12.6 Solved Problems¶
Problem 1 — Complete 2×2 solution¶
Solve the game of L11, Problem 2:
Solution.
Step 1 — confirm no saddle point. Row minima: \(1,\ 3\) ⟹ maximin \(= 3\). Column maxima: \(5,\ 4\) ⟹ minimax \(= 4\). \(3 \ne 4\) ✓ — mixed strategies required.
Step 2 — the denominator.
Step 3 — player A's strategy.
Step 4 — player B's strategy.
Step 5 — the value.
Verification by the equalising property.
A's expected payoff if B plays column 1:
A's expected payoff if B plays column 2:
Equal — so B is indifferent, exactly as the theory requires ✓.
B's expected loss if A plays row 1:
B's expected loss if A plays row 2:
All four expectations equal \(v = 3.4\) ✓ — the strongest possible check on a mixed-strategy solution, and one students should perform every time.
Confirming the bounds from L11. We predicted \(3 \le v \le 4\); indeed \(3 \le 3.4 \le 4\) ✓.
Interpretation. A should play row 1 about 1 time in 5 and row 2 4 times in 5, choosing randomly each play (e.g. by rolling a die). Doing so guarantees an average gain of 3.4 per play, whatever B does — which is better than the 3 that the best pure strategy guarantees.
Problem 2 — The odds method, applied fast¶
Solve \(\begin{pmatrix}6 & 4\\ 2 & 7\end{pmatrix}\) by the odds method.
Solution.
Step 1 — saddle-point test. Row minima \(4, 2\) ⟹ maximin \(= 4\). Column maxima \(6, 7\) ⟹ minimax \(= 6\). \(4 \ne 6\) ✓ — mixed.
Step 2 — oddments.
Step 3 — probabilities.
Step 4 — the value.
Verification.
Note the pleasing structure of the oddments. Row 1's oddment (5) uses row 2's entries, and vice versa. The mnemonic: "take the difference of the OTHER line, and ignore the sign."
Time comparison. The odds method took about 30 seconds; the algebraic derivation takes 2–3 minutes. In an examination, use odds and verify with one expectation calculation.
Problem 3 — A symmetric (fair) game¶
Solve the matching-pennies-style game \(\begin{pmatrix}4 & -4\\ -4 & 4\end{pmatrix}\) and interpret.
Solution.
Saddle-point test. Row minima \(-4, -4\) ⟹ maximin \(= -4\). Column maxima \(4, 4\) ⟹ minimax \(= 4\). \(-4 \ne 4\) ✓ — mixed.
Denominator. \((4+4)-(-4-4) = 8 + 8 = \mathbf{16}\).
Strategies.
Value.
Verification.
Interpretation and the crucial point about randomisation.
Both players play 50–50 and the game is fair. But the randomisation must be genuine.
Suppose A tried to "randomise" by alternating \(1,2,1,2,\ldots\) Over many plays this is exactly 50–50 in frequency, yet B — observing the pattern — would predict every move and always choose the column giving A \(-4\). A's average payoff would be \(\mathbf{-4}\), not 0.
Practical implication. Use a genuine randomising device — dice, a random-number generator, a shuffled deck. This is not a mathematical nicety: it is why tax authorities randomise audits, why security patrols randomise routes, and why penalty-takers in football are coached to randomise direction rather than follow a felt "pattern."
(The mathematical statement: the equilibrium requires A's mixed strategy to be independent of history. Any serially correlated sequence is exploitable by an opponent who conditions on the past.)
Problem 4 — Deriving the formulas from first principles¶
Derive \(p\), \(q\) and \(v\) for a general \(2\times2\) game without quoting the formulas, using the equalising property.
Solution.
Step 1 — A's expectations against each of B's pure strategies.
Step 2 — apply the equalising property. If these differed, B would always choose the smaller, and A could improve by adjusting \(p\). At the optimum they must be equal:
Step 3 — solve.
and \(1-p = 1 - \dfrac{d-c}{(a+d)-(b+c)} = \dfrac{(a+d)-(b+c)-(d-c)}{(a+d)-(b+c)} = \dfrac{a-b}{(a+d)-(b+c)}\) ✓.
Step 4 — B's strategy by the same argument. B plays column 1 w.p. \(q\); B's expected loss must be equal whichever row A plays:
Step 5 — the value. Substitute \(p\) into \(E(\text{col 1})\):
When the derivation breaks down.
- If \(D = 0\): the formulas are undefined. This happens when \(a+d = b+c\), and one can show a saddle point must then exist — so pure strategies apply.
- If \(p \notin [0,1]\): the "solution" is not a probability. Again a saddle point exists.
Problem 5 — A business application: competitive bidding¶
Two contractors bid for a project. Each may bid Low or High. The matrix gives contractor A's expected profit (₹ lakh). Solve and advise A.
| A \ B | B bids Low | B bids High |
|---|---|---|
| A bids Low | 2 | −1 |
| A bids High | −1 | 1 |
Solution.
Step 1 — saddle-point test. Row minima: \(-1,\ -1\) ⟹ maximin \(= -1\). Column maxima: \(2,\ 1\) ⟹ minimax \(= 1\). \(-1 \ne 1\) ✓ — mixed strategies required.
Step 2 — solve. With \(a = 2\), \(b = -1\), \(c = -1\), \(d = 1\):
Verification.
Advice to contractor A.
-
Bid Low about 40 % of the time and High about 60 % of the time, chosen at random for each tender. Over many tenders this yields an average profit of ₹20 000 per tender.
-
Why not always bid High? High is A's better average row (\((-1+1)/2 = 0\) versus \((2-1)/2 = 0.5\) — actually Low is better on a uniform average). But neither pure strategy is safe:
- Always Low ⟹ B bids High ⟹ A gets −1 (a loss).
- Always High ⟹ B bids Low ⟹ A gets −1 (a loss).
Both pure strategies guarantee a loss of ₹1 lakh once B adapts. Randomising converts a guaranteed loss into a guaranteed gain of ₹20 000 — a swing of ₹1.2 lakh per tender.
-
How to implement. Do not try to alternate or follow a felt pattern (Problem 3's lesson). Use a real randomiser: generate a number in \([0,1)\) for each tender; bid Low if it is below 0.4.
-
Guard against information leakage. The whole value rests on B not knowing A's draw. If bids are prepared by a team, the randomisation must be done as late and as privately as possible.
-
The model's limits, stated honestly. Zero-sum is a strong assumption here — in reality both contractors might profit from a larger market, and repeated interaction allows tacit understandings (which may also be illegal). Treat \(v = ₹20\,000\) as a worst-case guarantee against a fully adversarial rival, not a forecast.
12.7 Practice Problems¶
- Solve \(\begin{pmatrix}3&5\\6&2\end{pmatrix}\). [Ans: \(p=(4/6,2/6)\), \(q=(3/6,3/6)\), \(v = 4\)]
- Solve \(\begin{pmatrix}1&-3\\-2&4\end{pmatrix}\). [Ans: \(D=10\), \(p=(0.6,0.4)\), \(q=(0.7,0.3)\), \(v = -0.2\)]
- Use the odds method on \(\begin{pmatrix}8&2\\3&6\end{pmatrix}\). [Ans: \(p=(3/9,6/9)\)... verify; \(v=42/9\)]
- Show that a symmetric game (\(A = -A^{T}\)) always has \(v = 0\).
- What happens to the formulas if \((a+d) = (b+c)\)?
- Verify the equalising property for Problem 1's solution against both columns.
- Explain why alternating \(1,2,1,2,\ldots\) is not a valid implementation of \(\vec p = (0.5, 0.5)\).
12.8 Summary¶
- A mixed strategy is a probability distribution over pure strategies; randomisation is necessary when no saddle point exists, because any predictable choice is exploitable.
- Minimax theorem (von Neumann): every finite two-person zero-sum game has a value in mixed strategies — the pure-strategy gap \(\underline v < \overline v\) always closes. It is equivalent to LP duality.
- Equalising property: an optimal mixed strategy makes the opponent indifferent among their active pure strategies. This is the computational key.
- \(2\times2\) formulas: \(p = \dfrac{d-c}{D}\), \(q = \dfrac{d-b}{D}\), \(v = \dfrac{ad-bc}{D}\) with \(D = (a+d)-(b+c)\).
- Odds method: each line's oddment is the absolute difference of the other line's entries; probabilities are oddments normalised.
- Always test for a saddle point first — the mixed formulas are invalid if \(D = 0\) or \(p,q\notin[0,1]\).
- Verify by computing all expectations: every one must equal \(v\).
- Randomisation must be genuinely unpredictable, not merely correct in long-run frequency — a serially correlated sequence is fully exploitable.
Next lesson: L13 — Graphical and LP solution of larger games.
Practise now: unit2-games-networks-lab.html → Game Solver: enter a \(2\times2\) game, see the
oddments, probabilities and value computed live, and simulate repeated play to watch the average
converge to \(v\).