Lesson 13: Graphical and LP Solution of Games¶
13.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Solve a \(2\times n\) game by the graphical method.
- Solve an \(m\times2\) game by the graphical method.
- Identify the critical (active) pure strategies from the graph.
- Formulate an arbitrary \(m\times n\) game as a linear programme.
- Extract both players' optimal strategies from the LP solution.
13.2 The Graphical Method for 2× n Games¶
Applicable when player A has exactly 2 strategies (after dominance reduction, L11).
The idea¶
Let A play row 1 with probability \(p\) and row 2 with \(1-p\). Against B's column \(j\), A's expected payoff is a linear function of \(p\):
Plot all \(n\) of these lines over \(p\in[0,1]\).
B will choose whichever column gives A the least, so A actually receives
A maximises this, so the solution is at the highest point of the lower envelope.
The procedure¶
1. Draw two vertical axes at p = 0 and p = 1
2. For each column j:
plot the point a_2j on the p=0 axis
plot the point a_1j on the p=1 axis
join them with a straight line
3. Shade the LOWER envelope (the lowest line at each p)
4. Find its HIGHEST point -- this is (p*, v)
5. The two lines meeting at that point identify B's ACTIVE columns
6. Solve the resulting 2x2 game exactly (L12) for the precise p*, q*, v
Step 6 matters. The graph identifies which strategies are active; the algebra then gives exact values.
13.3 The Graphical Method for m×2 Games¶
Applicable when player B has exactly 2 strategies.
Let B play column 1 with probability \(q\). Against A's row \(i\), B's expected loss is
A will choose whichever row gives the most, so B faces
B minimises this, so the solution is at the lowest point of the upper envelope.
| Game shape | Envelope | Optimise |
|---|---|---|
| \(2\times n\) (A has 2) | lower | maximum of it |
| \(m\times2\) (B has 2) | upper | minimum of it |
The mnemonic. A is the maximiser and gets the worst column, so: lower envelope, highest point. B is the minimiser and suffers the best row, so: upper envelope, lowest point.
13.4 LP Formulation of a General Game¶
For \(m\times n\) games with \(m,n > 2\), no graphical shortcut exists — but LP solves them exactly.
Player A's LP¶
Assume \(v > 0\) (add a constant \(k\) to every entry if necessary; this raises \(v\) by \(k\) and leaves the optimal strategies unchanged — the same argument as L10's Hungarian theorem).
A seeks \(\vec p\) maximising the guaranteed payoff \(v\):
Linearise by substitution. Put \(x_i = p_i / v\) (valid since \(v>0\)). Then \(\sum_i x_i = 1/v\), and maximising \(v\) is minimising \(1/v\):
Recover \(v = 1/\sum_i x_i\) and \(p_i = v\,x_i\).
Player B's LP — the dual¶
with \(q_j = v\,y_j\).
A practical bonus. Solving A's LP by simplex gives B's optimal strategy for free, in the \(z_j - c_j\) row of the final tableau (L07) — one computation solves the game for both players.
13.5 Solved Problems¶
Problem 1 — A 2×3 game, graphically¶
Solve
Solution.
Step 1 — saddle-point test. Row minima \(2,\ 3\) ⟹ maximin \(= 3\). Column maxima \(9,\ 7,\ 11\) ⟹ minimax \(= 7\). \(3 \ne 7\) ✓ — mixed.
Step 2 — the three payoff lines. With A playing row 1 with probability \(p\):
Step 3 — endpoint values.
| Column | At \(p=0\) | At \(p=1\) |
|---|---|---|
| \(B_1\) | 9 | 2 |
| \(B_2\) | 5 | 7 |
| \(B_3\) | 3 | 11 |
payoff
11 | * B3
9 |*B1
7 | \ * B2
5 | \ * B2
3 | * B3 \____
2 | \____ * B1
+--------|--------|--------
p=0 p=4/9 p=1
^
highest point of the
LOWER ENVELOPE
Step 4 — identify the lower envelope.
At \(p = 0\): the lines take values \(9, 5, 3\) ⟹ \(B_3\) is lowest. At \(p = 1\): values \(2, 7, 11\) ⟹ \(B_1\) is lowest.
So the lower envelope starts on \(B_3\) (rising) and ends on \(B_1\) (falling). Its maximum is where \(B_3\) and \(B_1\) cross — unless \(B_2\) dips below at that point.
Step 5 — find the intersection of \(B_1\) and \(B_3\).
Check \(B_2\) at \(p = 0.4\): \(E_2 = 5 + 2(0.4) = 5.8 < 6.2\).
\(B_2\) lies BELOW — so the envelope is not at \(B_1\cap B_3\). The true maximum is elsewhere.
Step 6 — find the correct pair. Since \(B_2\) intrudes, the envelope's peak is where \(B_2\) meets whichever of \(B_1, B_3\) bounds it. Try \(B_1 \cap B_2\):
Check \(B_3\) at \(p = \frac49\): \(E_3 = 3 + 8\left(\frac49\right) = 3 + \frac{32}{9} = \frac{59}{9} \approx 6.556 > \frac{53}{9}\) ✓ — above, so it does not bind.
Step 7 — B's strategy. The active columns are \(B_1\) and \(B_2\), so B never plays \(B_3\). Solve the \(2\times2\) sub-game
Verify \(p\) and \(v\) from the sub-game:
Full verification.
The last line is the key check. \(B_3\) gives A more than \(v\), so B correctly avoids it entirely.
The lesson of Step 5. Do not assume the outermost lines are the binding pair — always verify that no other line dips below the candidate intersection.
Problem 2 — An m×2 game, graphically¶
Solve
Solution.
Step 1 — saddle-point test. Row minima \(-7,\ -4,\ -4\) ⟹ maximin \(= -4\). Column maxima \(7,\ 6\) ⟹ minimax \(= 6\). \(-4 \ne 6\) ✓ — mixed.
Step 2 — B has 2 strategies, so plot B's expected LOSS lines as functions of \(q\) (probability of column 1):
| Row | At \(q=0\) | At \(q=1\) |
|---|---|---|
| \(A_1\) | 6 | −7 |
| \(A_2\) | −4 | 7 |
| \(A_3\) | −2 | −4 |
loss
7 | * A2
6 |* A1
| \ /
0 |------\-------------/-----------
-2 |* A3 \ /
-4 | * A2 \ / * A3
-7 | \/ * A1
+------|------|------|-----
q=0 q=5/12 q=1
^
lowest point of the
UPPER ENVELOPE
Step 3 — identify the upper envelope.
At \(q = 0\): values \(6, -4, -2\) ⟹ \(A_1\) highest. At \(q = 1\): values \(-7, 7, -4\) ⟹ \(A_2\) highest.
So the envelope starts on \(A_1\) (falling) and ends on \(A_2\) (rising), with its minimum where they cross.
Step 4 — the intersection of \(A_1\) and \(A_2\).
Check \(A_3\) at \(q = \frac{5}{12}\):
Since \(-2.833 < \frac{7}{12} \approx 0.583\), \(A_3\) lies BELOW the envelope ✓ — it does not bind, so A never plays it.
Step 5 — A's strategy. Active rows are \(A_1\) and \(A_2\). Solve the \(2\times2\) sub-game
Verification (B's losses against each of A's rows).
\(A_3\) gives A less than \(v\), so A correctly avoids it ✓. The game favours A slightly (\(v = 0.583 > 0\)).
Problem 3 — LP formulation of a 3×3 game¶
Formulate the following as an LP and solve.
Solution.
Step 1 — check for a saddle point. Row minima \(-3, -3, -4\) ⟹ maximin \(= -3\). Column maxima \(3, 3, 3\) ⟹ minimax \(= 3\). Different ⟹ mixed. No dominance reduces it (check: no row is uniformly \(\ge\) another; no column uniformly \(\le\) another).
Step 2 — ensure \(v > 0\). The smallest entry is \(-4\), so add \(k = 5\) to every entry:
All entries positive ⟹ \(v' > 0\) guaranteed. At the end, \(v = v' - 5\).
Step 3 — A's LP. With \(x_i = p_i/v'\):
Note how the constraint coefficients are the COLUMNS of \(A'\), since each constraint says "A's expected payoff against column \(j\) is at least \(v'\)."
Step 4 — B's LP (the dual). With \(y_j = q_j/v'\):
Here the coefficients are the rows of \(A'\).
Step 5 — solve B's LP by simplex. It has three \(\le\) constraints with positive right-hand sides, so the slacks give an immediate starting basis — no artificial variables needed. This is why B's LP is the one to solve by hand, even when you want A's strategy.
Running simplex gives
Step 6 — recover the value.
Step 7 — the strategies.
Verification — the decisive check.
A's expected payoff against each of B's columns:
All three equal \(v\) ✓ — exactly the equalising property (L12), and confirming that all three of B's strategies are active.
B's expected loss against each of A's rows likewise equals \(-\frac{29}{45}\) in all three cases ✓.
The three lessons of this problem.
- Set up the LP correctly: A's constraints use the columns of \(A'\); B's use the rows.
- Solve B's LP, because its all-\(\le\) form needs no artificial variables.
- Recover \(v = 1/U - k\), and read A's strategy from the \(z_j - c_j\) entries of the slack columns (L07) — one simplex run solves the game for both players.
Problem 4 — Reducing before solving¶
Solve \(\begin{pmatrix}1 & 3 & -3 & 7\\ 2 & 5 & 4 & -6\end{pmatrix}\).
Solution.
Step 1 — saddle-point test. Row minima \(-3,\ -6\) ⟹ maximin \(= -3\). Column maxima \(2, 5, 4, 7\) ⟹ minimax \(= 2\). \(-3 \ne 2\) ✓ — mixed.
Step 2 — column dominance (B keeps SMALL entries).
Compare \(B_1 = (1,2)\) with \(B_2 = (3,5)\): \(1\le3\) and \(2\le5\) ⟹ \(B_1\) dominates \(B_2\); delete \(B_2\).
Compare \(B_1 = (1,2)\) with \(B_3 = (-3,4)\): \(1 > -3\) ✗ — no dominance. Compare \(B_1\) with \(B_4 = (7,-6)\): \(1\le7\) ✓ but \(2 > -6\) ✗ — no dominance.
Reduced to \(2\times3\):
Step 3 — graphical solution. With A playing row 1 with probability \(p\):
| Column | \(p=0\) | \(p=1\) |
|---|---|---|
| \(B_1\) | 2 | 1 |
| \(B_3\) | 4 | −3 |
| \(B_4\) | −6 | 7 |
Lower envelope. At \(p=0\): values \(2, 4, -6\) ⟹ \(B_4\) lowest. At \(p=1\): \(1, -3, 7\) ⟹ \(B_3\) lowest. Envelope rises on \(B_4\), falls on \(B_3\); peak at their crossing.
Check \(B_1\) at \(p = 0.5\): \(E_1 = 2 - 0.5 = 1.5 > 0.5\) ✓ — above, so it does not bind.
Step 4 — B's strategy. Active columns are \(B_3\) and \(B_4\). The \(2\times2\) sub-game is
Verification against all four original columns.
Exactly the two active columns give \(v\); the two inactive ones give more. This is the complementary-slackness pattern of L07, appearing here in game-theoretic form ✓.
Note the efficiency gain. Dominance reduced \(2\times4\) to \(2\times3\), the graph reduced it to \(2\times2\), and the algebra finished it. This three-stage pipeline — dominance, graph, algebra — is the standard hand method for any game with 2 strategies on one side.
Problem 5 — A complete competitive-strategy analysis¶
Two airlines choose a departure time (Morning, Afternoon, Evening) on a competitive route. The matrix gives airline A's market-share gain (percentage points). Solve and advise.
| A \ B | Morning | Afternoon | Evening |
|---|---|---|---|
| Morning | 0 | 4 | −2 |
| Afternoon | −3 | 0 | 5 |
| Evening | 3 | −4 | 0 |
Solution.
Step 1 — structural observation. The matrix is skew-symmetric: \(a_{ij} = -a_{ji}\) for all \(i,j\) (check: \(a_{12} = 4\), \(a_{21} = -3\)... not quite — \(4 \ne 3\)). So it is nearly but not exactly a symmetric game.
Step 2 — saddle-point test. Row minima \(-2,\ -3,\ -4\) ⟹ maximin \(= -2\). Column maxima \(3,\ 4,\ 5\) ⟹ minimax \(= 3\). \(-2 \ne 3\) ✓ — mixed strategies required.
Step 3 — dominance. Check rows: none is uniformly \(\ge\) another (Morning has \(0,4,-2\); Afternoon \(-3,0,5\); Evening \(3,-4,0\) — each wins somewhere). Check columns: none is uniformly \(\le\) another. No reduction possible.
Step 4 — formulate as an LP. Add \(k = 5\) to make all entries positive:
A's LP (\(x_i = p_i/v'\), constraints from the columns of \(A'\)):
B's LP (the dual, constraints from the rows of \(A'\)):
Step 5 — solve B's LP by simplex (all \(\le\) constraints, so the slacks start the basis):
Verification. A's expected gain against each of B's columns:
All three equal \(v\) ✓ — every strategy is active, as the absence of dominance predicted.
Advice to airline A.
-
Randomise across all three departure times, roughly 42 % Morning, 23 % Afternoon, 34 % Evening — for example by varying the schedule between seasons or across the route network, so B cannot anticipate.
-
The game slightly favours A (\(v = +0.32\) percentage points per period). This is a small edge: A gains about a third of a share point on average, and only by randomising correctly. The important finding is how small it is — timing alone is nearly a wash, so A should also compete on dimensions the matrix does not contain: price, frequency, loyalty programme, aircraft comfort.
-
The cyclic structure. Note the pattern: Morning beats Afternoon (+4), Afternoon beats Evening (+5), Evening beats Morning (+3) — a rock–paper–scissors cycle. Such structures always require mixing and always have values near zero. Recognising the cycle immediately tells you that no pure strategy can work, before any computation.
-
Model limitations, stated honestly.
- Zero-sum is questionable. If both airlines schedule well, total demand may grow — a non-zero-sum effect the model excludes.
- Only three time slots is a coarse discretisation of a continuous decision.
- Repeated interaction allows learning and tacit coordination that a one-shot model cannot represent.
-
The defensible conclusion. "Timing is close to a zero-sum wash. Randomise to avoid being exploited, and direct competitive investment elsewhere." That recommendation is worth more than the third decimal place of \(v\).
13.6 Practice Problems¶
- Solve graphically: \(\begin{pmatrix}1&3&11\\8&5&2\end{pmatrix}\).
- Solve graphically: \(\begin{pmatrix}2&4\\2&3\\3&2\\-2&6\end{pmatrix}\).
- For a \(2\times n\) game, which envelope and which extreme point? [Ans: lower envelope, maximum]
- Write A's LP for \(\begin{pmatrix}2&5\\4&1\end{pmatrix}\) after adding \(k=0\).
- Why must \(v>0\) before making the substitution \(x_i = p_i/v\)?
- Show that A's LP and B's LP are duals.
- In Problem 4, why does column \(B_2\) give A more than \(v\)?
13.7 Summary¶
- \(2\times n\) games: plot A's expected payoff against each column as a line in \(p\); take the lower envelope and its highest point. \(m\times2\) games: plot B's expected loss against each row as a line in \(q\); take the upper envelope and its lowest point.
- The graph identifies the active pure strategies; the exact values come from solving the resulting \(2\times2\) sub-game algebraically (L12).
- Always check that no other line dips below (or rises above) the candidate intersection — the outermost lines are not always the binding pair.
- Any \(m\times n\) game becomes a pair of dual LPs: A minimises \(\sum x_i = 1/v\) subject to constraints built from the columns; B maximises \(\sum y_j\) subject to constraints from the rows. Add a constant \(k\) first to ensure \(v > 0\).
- The minimax theorem is LP strong duality, so solving one LP yields both players' strategies.
- Standard hand pipeline: dominance → graph → \(2\times2\) algebra; verify by checking that active strategies give exactly \(v\) and inactive ones give strictly more (or less).
- Cyclic (rock–paper–scissors) payoff structures always force mixing and have values near zero — recognise them by inspection.
Next lesson: L14 — Sequencing: \(n\) jobs through 2 machines (Johnson's rule).
Practise now: unit2-games-networks-lab.html → Game Solver: switch to graphical mode, drag the
lines, and watch the envelope and optimal \(p\) update live.