Why Pure Strategies Can Leave a Gap
In a finite decision problem, a loss matrix records the loss for every pair of actions chosen by a decision maker and an opposing player representing nature. If both players must choose one action without randomizing, the decision maker may face a worst-case loss strictly larger than the loss nature can guarantee. The resulting gap is not a calculation error: pure strategies may fail to have a saddle point. Allowing randomized strategies can change the game because expected loss is linear in each player’s randomization.
Throughout, rows are the decision maker’s actions, who seeks to minimize loss, and columns are nature’s actions, who seeks to maximize it. This orientation fixes the order of the two values. For a finite matrix \(L=(L_{ij})\), the pure-strategy minimax value is the smallest worst-case row loss; the pure-strategy maximin value is the largest loss nature can guarantee against the best row response.
The pure-strategy inequality follows because, for every row \(i\) and column \(j\), \(\min_k L_{kj}\leq L_{ij}\leq\max_\ell L_{i\ell}\). Taking the maximum over columns in the left expression and the minimum over rows in the right expression gives the claimed order. The inequality need not be equality.
Worked Example: The Matching-Pennies Loss Matrix
Worked Example: The Matching-Pennies Loss Matrix
Consider $$ L=\begin{pmatrix}0&1\\1&0\end{pmatrix}. $$ The row player minimizes loss, and nature chooses a column. Calculate both pure values, then allow randomization.
Pure maximin. In column 1, the smallest entry is \(0\); in column 2, it is also \(0\). Thus \(\underline V_{\mathrm{pure}}=\max(0,0)=0\).
Pure minimax. The largest entry in each row is \(1\), so \(\overline V_{\mathrm{pure}}=\min(1,1)=1\). The pure-strategy gap is \(1-0=1\).
Let \(p\) be the probability of row 1 and \(q\) the probability of column 1. The expected loss is \(p(1-q)+(1-p)q=p+q-2pq\). For fixed \(p\), the losses in columns 1 and 2 are \(1-p\) and \(p\), respectively; nature’s best response therefore gives \(\max(p,1-p)\). The decision maker minimizes this maximum at \(p=1/2\), yielding \(1/2\).
For fixed \(q\), the losses in rows 1 and 2 are \(1-q\) and \(q\). Nature maximizes the smaller of these losses, \(\min(q,1-q)\), by choosing \(q=1/2\), also yielding \(1/2\). Thus the two players’ equal-probability strategies attain the common mixed-strategy value \(1/2\), closing the pure gap.
A Family of Two-by-Two Examples
The same mechanism can be calculated for a whole family of loss matrices. The diagonal entries are \(c\); the off-diagonal entries add positive amounts \(a\) and \(b\). Assume \(c\geq0\) and \(a,b>0\), so all entries are nonnegative losses. These conditions also ensure that the two off-diagonal entries exceed the diagonal.
Proof. The minimum of the entries in column 1 is \(c\), and the minimum in column 2 is also \(c\). Hence \(\underline V_{\mathrm{pure}}=c\). The largest entries in the two rows are \(c+a\) and \(c+b\), so \(\overline V_{\mathrm{pure}}=\min(c+a,c+b)=c+\min(a,b)\). Since \(a,b>0\), this gives a strict pure-strategy gap.
Now let \(q\) be the probability of column 1. If the decision maker chooses row 1, expected loss is \(c+a(1-q)\); if row 2 is chosen, it is \(c+bq\). A randomization over rows gives a weighted average of these two losses, so the smallest achievable loss against this \(q\) is \(\min\{c+a(1-q),c+bq\}\). The first expression decreases with \(q\), and the second increases. They are equal when \(a(1-q)=bq\), or \(q=a/(a+b)\). At that point each is \(c+ab/(a+b)\). If \(q<a/(a+b)\), the second expression is smaller than this value; if \(q>a/(a+b)\), the first expression is smaller. Therefore their minimum is maximized at the intersection, and the mixed maximin value is \(c+ab/(a+b)\).
For the other order, let \(p\) be the probability of row 1. The expected losses if nature chooses columns 1 and 2 are, respectively, \(c+b(1-p)\) and \(c+ap\). Nature’s best response gives their maximum. These two expressions are equal when \(b(1-p)=ap\), or \(p=b/(a+b)\), and their common value is \(c+ab/(a+b)\). If \(p<b/(a+b)\), the first expression exceeds that value; if \(p>b/(a+b)\), the second exceeds it. Thus the maximum is minimized at the intersection, giving the mixed minimax value \(c+ab/(a+b)\) as well. The strategies specified in the theorem attain both values. \(\square\)
Worked Example: Unequal Off-Diagonal Losses
Take $$ L=\begin{pmatrix}0&2\\1&0\end{pmatrix}. $$ Here \(c=0\), \(a=2\), and \(b=1\). The pure maximin is \(\max\{\min(0,1),\min(2,0)\}=\max(0,0)=0\). The pure minimax is \(\min\{\max(0,2),\max(1,0)\}=\min(2,1)=1\), so the pure gap is \(1\).
The theorem gives row probability \(p=b/(a+b)=1/3\) and column probability \(q=a/(a+b)=2/3\). The mixed value is \(ab/(a+b)=2/3\). To verify directly, against \(q=2/3\), row 1 has expected loss \(2(1-2/3)=2/3\) and row 2 has expected loss \(2/3\). Against \(p=1/3\), column 1 gives loss \(1(1-1/3)=2/3\), and column 2 gives loss \(2(1/3)=2/3\). Each player makes the other indifferent between the two pure actions, and the common expected loss is \(2/3\).
Worked Example: A Positive Baseline Loss
Suppose the loss matrix is $$ L=\begin{pmatrix}3&7\\9&3\end{pmatrix}. $$ The pure maximin is \(\max\{\min(3,9),\min(7,3)\}=\max(3,3)=3\). The pure minimax is \(\min\{\max(3,7),\max(9,3)\}=\min(7,9)=7\). The gap is \(7-3=4\).
Here \(c=3\), \(a=4\), and \(b=6\). The mixed probabilities are \(p=6/(4+6)=0.6\) for row 1 and \(q=4/(4+6)=0.4\) for column 1. The mixed value is \(3+(4)(6)/10=5.4\).
Against \(q=0.4\), row 1 has expected loss \(3(0.4)+7(0.6)=5.4\), and row 2 has expected loss \(9(0.4)+3(0.6)=5.4\). Against \(p=0.6\), column 1 gives expected loss \(3(0.6)+9(0.4)=5.4\), and column 2 gives \(7(0.6)+3(0.4)=5.4\). The baseline raises every entry by 3, while the unequal off-diagonal penalties determine the mixing probabilities.
What the Gap Does—and Does Not—Mean
A strict pure-strategy gap means that no pair of pure actions provides the equality of best responses associated with a saddle point. In the family above, each player’s mixture balances the other player’s two pure actions. This makes the opponent indifferent and produces a common value. The calculation is a finite, explicit illustration of why allowing randomization matters in decision problems.
Do not confuse this example with a claim that every loss matrix has a pure-strategy equality. In general, the pure maximin and minimax values can differ, as the examples show. The equality established here is for the mixed-strategy values in finite zero-sum matrix games; the examples verify it directly rather than inferring it from finiteness alone.
A common mistaken argument is: “There are finitely many rows and columns, so some pair of actions must attain both values.” Finiteness guarantees that the pure extrema are attained, but it does not guarantee that they are attained by a mutually compatible pair. In the first example, every pure row has worst-case loss \(1\), while every pure column permits a row loss of \(0\). The correction is to calculate the two pure values separately, then check whether randomization changes the attainable guarantees. Mixing does not mean replacing the loss matrix by an unweighted average: the probabilities must be chosen to balance the relevant expected losses.
Check Your Understanding
Use the row-minimizes, column-maximizes convention throughout.
- For the matrix \(\begin{pmatrix}0&3\\2&0\end{pmatrix}\), calculate the pure maximin and pure minimax values.
- For that same matrix, find the probabilities \(p\) and \(q\) that make the two pure actions indifferent for the opponent, and calculate the mixed value.
- For the family \(\begin{pmatrix}c&c+a\\c+b&c\end{pmatrix}\), explain why the pure gap is strictly positive when \(a,b>0\).
- In the positive-baseline example, verify why a baseline of 3 adds 3 to each mixed expected loss.
- Why does finiteness ensure that pure extrema are attained without ensuring equality of the pure maximin and minimax values?