Skip to content

Lesson 13: Graphical and LP Solution of Games

13.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. Solve a \(2\times n\) game by the graphical method.
  2. Solve an \(m\times2\) game by the graphical method.
  3. Identify the critical (active) pure strategies from the graph.
  4. Formulate an arbitrary \(m\times n\) game as a linear programme.
  5. 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\):

\[ E_j(p) \ =\ a_{1j}\,p \ +\ a_{2j}\,(1-p) \ =\ a_{2j} + \big(a_{1j}-a_{2j}\big)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

\[ \underline{E}(p) \ =\ \min_j E_j(p) \qquad\text{— the \textbf{lower envelope}} \]

A maximises this, so the solution is at the highest point of the lower envelope.

\[ \boxed{\ v = \max_{p\in[0,1]} \ \min_j\ E_j(p)\ } \]

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

\[ E_i(q) \ =\ a_{i1}q + a_{i2}(1-q) \]

A will choose whichever row gives the most, so B faces

\[ \overline{E}(q) \ =\ \max_i E_i(q) \qquad\text{— the \textbf{upper envelope}} \]

B minimises this, so the solution is at the lowest point of the upper envelope.

\[ \boxed{\ v = \min_{q\in[0,1]} \ \max_i\ E_i(q)\ } \]
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\):

\[ \begin{aligned} \max\ & v\\ \text{s.t. } & \sum_{i=1}^{m} a_{ij}p_i \ \ge\ v && j = 1,\ldots,n\\ & \sum_{i=1}^{m} p_i = 1, \qquad p_i \ge 0 \end{aligned} \]

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

\[ \boxed{\ \begin{aligned} \min\ & \sum_{i=1}^{m} x_i \ \left(= \tfrac1v\right)\\ \text{s.t. } & \sum_{i=1}^{m} a_{ij}x_i \ \ge\ 1 && j = 1,\ldots,n\\ & x_i \ge 0 \end{aligned}\ } \]

Recover \(v = 1/\sum_i x_i\) and \(p_i = v\,x_i\).

Player B's LP — the dual

\[ \boxed{\ \begin{aligned} \max\ & \sum_{j=1}^{n} y_j \ \left(= \tfrac1v\right)\\ \text{s.t. } & \sum_{j=1}^{n} a_{ij}y_j \ \le\ 1 && i = 1,\ldots,m\\ & y_j \ge 0 \end{aligned}\ } \]

with \(q_j = v\,y_j\).

\[ \boxed{\ \textbf{A's LP and B's LP are DUALS of each other, and strong duality} \ \Longleftrightarrow\ \textbf{the minimax theorem.}\ } \]

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

\[ A = \begin{pmatrix} 2 & 7 & 11\\ 9 & 5 & 3\end{pmatrix} \]

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

\[ E_1(p) = 2p + 9(1-p) = 9 - 7p \]
\[ E_2(p) = 7p + 5(1-p) = 5 + 2p \]
\[ E_3(p) = 11p + 3(1-p) = 3 + 8p \]

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

\[ 9 - 7p = 3 + 8p \ \Longrightarrow\ 6 = 15p \ \Longrightarrow\ p = \tfrac25 = 0.4 \]
\[ E = 9 - 7(0.4) = 6.2 \]

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

\[ 9 - 7p = 5 + 2p \ \Longrightarrow\ 4 = 9p \ \Longrightarrow\ p = \tfrac49 \]
\[ E = 5 + 2\left(\tfrac49\right) = 5 + \tfrac89 = \tfrac{53}{9} \approx 5.889 \]

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.

\[ \boxed{\ p^{*} = \tfrac49, \qquad v = \tfrac{53}{9} \approx 5.889\ } \]

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

\[ \begin{pmatrix}2 & 7\\ 9 & 5\end{pmatrix}: \qquad D = (2+5)-(7+9) = 7 - 16 = -9 \]
\[ q = \frac{d-b}{D} = \frac{5-7}{-9} = \frac{2}{9}, \qquad 1-q = \frac{7}{9} \]

Verify \(p\) and \(v\) from the sub-game:

\[ p = \frac{d-c}{D} = \frac{5-9}{-9} = \frac49 \ \checkmark, \qquad v = \frac{ad-bc}{D} = \frac{10-63}{-9} = \frac{53}{9} \ \checkmark \]
\[ \boxed{\ \vec p^{*} = \left(\tfrac49,\ \tfrac59\right), \quad \vec q^{*} = \left(\tfrac29,\ \tfrac79,\ 0\right), \quad v = \tfrac{53}{9}\ } \]

Full verification.

\[ \text{vs } B_1:\ 2\left(\tfrac49\right)+9\left(\tfrac59\right) = \tfrac{8+45}{9} = \tfrac{53}{9} \ \checkmark \]
\[ \text{vs } B_2:\ 7\left(\tfrac49\right)+5\left(\tfrac59\right) = \tfrac{28+25}{9} = \tfrac{53}{9} \ \checkmark \]
\[ \text{vs } B_3:\ 11\left(\tfrac49\right)+3\left(\tfrac59\right) = \tfrac{44+15}{9} = \tfrac{59}{9} > \tfrac{53}{9} \ \checkmark \]

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

\[ A = \begin{pmatrix} -7 & 6\\ 7 & -4\\ -4 & -2\end{pmatrix} \]

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

\[ E_1(q) = -7q + 6(1-q) = 6 - 13q \]
\[ E_2(q) = 7q - 4(1-q) = -4 + 11q \]
\[ E_3(q) = -4q - 2(1-q) = -2 - 2q \]
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\).

\[ 6 - 13q = -4 + 11q \ \Longrightarrow\ 10 = 24q \ \Longrightarrow\ q = \tfrac{10}{24} = \tfrac{5}{12} \]
\[ E = 6 - 13\left(\tfrac{5}{12}\right) = 6 - \tfrac{65}{12} = \tfrac{72-65}{12} = \tfrac{7}{12} \]

Check \(A_3\) at \(q = \frac{5}{12}\):

\[ E_3 = -2 - 2\left(\tfrac{5}{12}\right) = -2 - \tfrac56 = -\tfrac{17}{6} \approx -2.833 \]

Since \(-2.833 < \frac{7}{12} \approx 0.583\), \(A_3\) lies BELOW the envelope ✓ — it does not bind, so A never plays it.

\[ \boxed{\ q^{*} = \tfrac{5}{12}, \qquad v = \tfrac{7}{12} \approx 0.583\ } \]

Step 5 — A's strategy. Active rows are \(A_1\) and \(A_2\). Solve the \(2\times2\) sub-game

\[ \begin{pmatrix}-7 & 6\\ 7 & -4\end{pmatrix}: \qquad D = (-7-4)-(6+7) = -11-13 = -24 \]
\[ p = \frac{d-c}{D} = \frac{-4-7}{-24} = \frac{11}{24}, \qquad 1-p = \frac{13}{24} \]
\[ q = \frac{d-b}{D} = \frac{-4-6}{-24} = \frac{10}{24} = \frac{5}{12} \ \checkmark \]
\[ v = \frac{ad-bc}{D} = \frac{28-42}{-24} = \frac{-14}{-24} = \frac{7}{12} \ \checkmark \]
\[ \boxed{\ \vec p^{*} = \left(\tfrac{11}{24},\ \tfrac{13}{24},\ 0\right), \quad \vec q^{*} = \left(\tfrac{5}{12},\ \tfrac{7}{12}\right), \quad v = \tfrac{7}{12}\ } \]

Verification (B's losses against each of A's rows).

\[ A_1:\ -7\left(\tfrac{5}{12}\right)+6\left(\tfrac{7}{12}\right) = \tfrac{-35+42}{12} = \tfrac{7}{12} \ \checkmark \]
\[ A_2:\ 7\left(\tfrac{5}{12}\right)-4\left(\tfrac{7}{12}\right) = \tfrac{35-28}{12} = \tfrac{7}{12} \ \checkmark \]
\[ A_3:\ -4\left(\tfrac{5}{12}\right)-2\left(\tfrac{7}{12}\right) = \tfrac{-20-14}{12} = -\tfrac{34}{12} = -\tfrac{17}{6} < \tfrac{7}{12} \ \checkmark \]

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

\[ A = \begin{pmatrix} 3 & -1 & -3\\ -3 & 3 & -1\\ -4 & -3 & 3\end{pmatrix} \]

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:

\[ A' = \begin{pmatrix} 8 & 4 & 2\\ 2 & 8 & 4\\ 1 & 2 & 8\end{pmatrix} \]

All entries positive ⟹ \(v' > 0\) guaranteed. At the end, \(v = v' - 5\).

Step 3 — A's LP. With \(x_i = p_i/v'\):

\[ \begin{aligned} \min\ & W = x_1 + x_2 + x_3 \ \left(=\tfrac{1}{v'}\right)\\ \text{s.t. } & 8x_1 + 2x_2 + \ \ x_3 \ \ge 1 && \text{(B plays col 1)}\\ & 4x_1 + 8x_2 + 2x_3 \ \ge 1 && \text{(B plays col 2)}\\ & 2x_1 + 4x_2 + 8x_3 \ \ge 1 && \text{(B plays col 3)}\\ & x_1, x_2, x_3 \ge 0 \end{aligned} \]

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

\[ \begin{aligned} \max\ & U = y_1+y_2+y_3\\ \text{s.t. } & 8y_1 + 4y_2 + 2y_3 \le 1\\ & 2y_1 + 8y_2 + 4y_3 \le 1\\ & \ \ y_1 + 2y_2 + 8y_3 \le 1\\ & y_j \ge 0 \end{aligned} \]

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

\[ y_1 = \tfrac{1}{14} = \tfrac{14}{196}, \qquad y_2 = \tfrac{11}{196}, \qquad y_3 = \tfrac{5}{49} = \tfrac{20}{196} \]
\[ U = \sum_j y_j = \frac{14 + 11 + 20}{196} = \frac{45}{196} \]

Step 6 — recover the value.

\[ v' = \frac{1}{U} = \frac{196}{45} = 4.3\overline{5} \]
\[ \boxed{\ v = v' - k = \frac{196}{45} - 5 = \frac{196-225}{45} = -\frac{29}{45} \approx -0.6444\ } \]

Step 7 — the strategies.

\[ \vec p^{*} = \left(\tfrac49,\ \tfrac{11}{45},\ \tfrac{14}{45}\right) \approx (0.4444,\ 0.2444,\ 0.3111) \]
\[ \vec q^{*} = \left(\tfrac{14}{45},\ \tfrac{11}{45},\ \tfrac49\right) \approx (0.3111,\ 0.2444,\ 0.4444) \]

Verification — the decisive check.

A's expected payoff against each of B's columns:

\[ \text{col 1: } 3\left(\tfrac49\right) - 3\left(\tfrac{11}{45}\right) - 4\left(\tfrac{14}{45}\right) = \tfrac{60 - 33 - 56}{45} = -\tfrac{29}{45} \ \checkmark \]
\[ \text{col 2: } -1\left(\tfrac49\right) + 3\left(\tfrac{11}{45}\right) - 3\left(\tfrac{14}{45}\right) = \tfrac{-20 + 33 - 42}{45} = -\tfrac{29}{45} \ \checkmark \]
\[ \text{col 3: } -3\left(\tfrac49\right) - 1\left(\tfrac{11}{45}\right) + 3\left(\tfrac{14}{45}\right) = \tfrac{-60 - 11 + 42}{45} = -\tfrac{29}{45} \ \checkmark \]

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

\[ \boxed{\ v = -\tfrac{29}{45} < 0 \ \Longrightarrow\ \textbf{the game favours B.}\ } \]

The three lessons of this problem.

  1. Set up the LP correctly: A's constraints use the columns of \(A'\); B's use the rows.
  2. Solve B's LP, because its all-\(\le\) form needs no artificial variables.
  3. 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\):

\[ \begin{pmatrix}1 & -3 & 7\\ 2 & 4 & -6\end{pmatrix} \]

Step 3 — graphical solution. With A playing row 1 with probability \(p\):

\[ E_1(p) = 1p + 2(1-p) = 2 - p \]
\[ E_3(p) = -3p + 4(1-p) = 4 - 7p \]
\[ E_4(p) = 7p - 6(1-p) = -6 + 13p \]
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.

\[ -6 + 13p = 4 - 7p \ \Longrightarrow\ 20p = 10 \ \Longrightarrow\ p = \mathbf{0.5} \]
\[ E = -6 + 13(0.5) = \mathbf{0.5} \]

Check \(B_1\) at \(p = 0.5\): \(E_1 = 2 - 0.5 = 1.5 > 0.5\) ✓ — above, so it does not bind.

\[ \boxed{\ p^{*} = 0.5, \qquad v = 0.5\ } \]

Step 4 — B's strategy. Active columns are \(B_3\) and \(B_4\). The \(2\times2\) sub-game is

\[ \begin{pmatrix}-3 & 7\\ 4 & -6\end{pmatrix}: \qquad D = (-3-6)-(7+4) = -9 - 11 = -20 \]
\[ q = \frac{d-b}{D} = \frac{-6-7}{-20} = \frac{13}{20} = 0.65 \]
\[ p = \frac{d-c}{D} = \frac{-6-4}{-20} = \frac{10}{20} = 0.5 \ \checkmark \]
\[ v = \frac{ad-bc}{D} = \frac{18-28}{-20} = \frac{-10}{-20} = 0.5 \ \checkmark \]
\[ \boxed{\ \vec p^{*} = (0.5,\ 0.5), \quad \vec q^{*} = (0,\ 0,\ 0.65,\ 0.35), \quad v = 0.5\ } \]

Verification against all four original columns.

\[ B_1:\ 1(0.5)+2(0.5) = 1.5 \ \ge 0.5 \ \checkmark \]
\[ B_2:\ 3(0.5)+5(0.5) = 4.0 \ \ge 0.5 \ \checkmark \]
\[ B_3:\ -3(0.5)+4(0.5) = 0.5 \ = v \ \checkmark \ \text{(active)} \]
\[ B_4:\ 7(0.5)-6(0.5) = 0.5 \ = v \ \checkmark \ \text{(active)} \]

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' = \begin{pmatrix}5 & 9 & 3\\ 2 & 5 & 10\\ 8 & 1 & 5\end{pmatrix} \]

A's LP (\(x_i = p_i/v'\), constraints from the columns of \(A'\)):

\[ \begin{aligned} \min\ & x_1+x_2+x_3\\ \text{s.t. } & 5x_1 + 2x_2 + 8x_3 \ge 1\\ & 9x_1 + 5x_2 + \ \ x_3 \ge 1\\ & 3x_1 + 10x_2 + 5x_3 \ge 1\\ & x_i \ge 0 \end{aligned} \]

B's LP (the dual, constraints from the rows of \(A'\)):

\[ \begin{aligned} \max\ & y_1+y_2+y_3\\ \text{s.t. } & 5y_1 + 9y_2 + 3y_3 \le 1\\ & 2y_1 + 5y_2 + 10y_3 \le 1\\ & 8y_1 + \ \ y_2 + 5y_3 \le 1\\ & y_j \ge 0 \end{aligned} \]

Step 5 — solve B's LP by simplex (all \(\le\) constraints, so the slacks start the basis):

\[ U = \sum_j y_j = \frac{37}{197}, \qquad v' = \frac{1}{U} = \frac{197}{37} = 5.3243 \]
\[ \boxed{\ v = v' - k = \frac{197}{37} - 5 = \frac{197 - 185}{37} = \frac{12}{37} \approx 0.3243 \ \text{percentage points}\ } \]
\[ \vec p^{*} = \left(\tfrac{47}{111},\ \tfrac{26}{111},\ \tfrac{38}{111}\right) \approx (0.4234,\ 0.2342,\ 0.3423) \]
\[ \vec q^{*} = \left(\tfrac{16}{37},\ \tfrac{9}{37},\ \tfrac{12}{37}\right) \approx (0.4324,\ 0.2432,\ 0.3243) \]

Verification. A's expected gain against each of B's columns:

\[ \text{Morning: } 0\left(\tfrac{47}{111}\right) - 3\left(\tfrac{26}{111}\right) + 3\left(\tfrac{38}{111}\right) = \tfrac{-78+114}{111} = \tfrac{36}{111} = \tfrac{12}{37} \ \checkmark \]
\[ \text{Afternoon: } 4\left(\tfrac{47}{111}\right) + 0 - 4\left(\tfrac{38}{111}\right) = \tfrac{188-152}{111} = \tfrac{36}{111} = \tfrac{12}{37} \ \checkmark \]
\[ \text{Evening: } -2\left(\tfrac{47}{111}\right) + 5\left(\tfrac{26}{111}\right) + 0 = \tfrac{-94+130}{111} = \tfrac{36}{111} = \tfrac{12}{37} \ \checkmark \]

All three equal \(v\) ✓ — every strategy is active, as the absence of dominance predicted.

Advice to airline A.

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

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

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

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

  1. Solve graphically: \(\begin{pmatrix}1&3&11\\8&5&2\end{pmatrix}\).
  2. Solve graphically: \(\begin{pmatrix}2&4\\2&3\\3&2\\-2&6\end{pmatrix}\).
  3. For a \(2\times n\) game, which envelope and which extreme point? [Ans: lower envelope, maximum]
  4. Write A's LP for \(\begin{pmatrix}2&5\\4&1\end{pmatrix}\) after adding \(k=0\).
  5. Why must \(v>0\) before making the substitution \(x_i = p_i/v\)?
  6. Show that A's LP and B's LP are duals.
  7. 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.