Why Minimax Arguments Need an Audit
In a statistical decision problem, a rule is chosen to control risk across possible parameter values or prior distributions. It is tempting to exchange the order of the decision maker’s optimization and nature’s optimization whenever the expressions look similar. But the two orders need not have the same value, and equality of their values does not by itself produce strategies that attain them. The central discipline is to check the order, the topology, and the attainment claims separately.
Let \(X\) be the decision maker’s strategy set, \(Y\) the opponent’s strategy set, and \(G(x,y)\) a real-valued payoff, interpreted as a loss to be minimized by the player choosing \(x\) and maximized by the player choosing \(y\). The two optimization orders are
In a risk-prior game, \(x\) can represent a decision rule, \(y\) a prior distribution, and \(G(x,y)\) the rule’s risk averaged under that prior. The algebra of the optimization orders is the same regardless of this interpretation.
The Order Inequality and Its Limits
To prove it, fix any \(x\in X\) and \(y\in Y\). By the definitions of infimum and supremum,
The leftmost quantity is therefore no larger than \(\sup_{v\in Y}G(x,v)\) for every \(y\). Taking the supremum over \(y\) preserves that inequality. The resulting left-hand side is no larger than \(\sup_{v\in Y}G(x,v)\) for every \(x\); taking the infimum over \(x\) proves the claim. \(\square\)
The inequality gives a useful first check: when the decision maker minimizes and the opponent maximizes, reversing the order cannot make the value larger. A proof that concludes the reverse inequality from algebra alone has not established interchange; it needs additional structure, such as the hypotheses of a minimax theorem.
Worked Example: Reversing the Order in a Finite Game
Let \(X=Y=\{0,1\}\), and let \(G(x,y)=1\) when \(x=y\), and \(G(x,y)=0\) otherwise. Compute both orders.
For either fixed \(x\), the opponent can choose \(y=x\), giving \(G(x,y)=1\). Thus \(\sup_yG(x,y)=1\) for both \(x\), and
For either fixed \(y\), the decision maker can choose the other action \(x\neq y\), giving payoff 0. Hence \(\inf_xG(x,y)=0\) for both \(y\), so
The values differ: \(0<1\). The sets are finite, so compactness is not enough by itself to justify interchange. The payoff and strategy sets must also meet the relevant structural hypotheses of the theorem being used.
Match Semicontinuity to the Optimization
For a minimization over a compact space, lower semicontinuity is the condition that supports attainment of a minimum. For a maximization over a compact space, the corresponding condition is upper semicontinuity. In an interchange theorem, these conditions apply to the relevant sections of the payoff: the function of the minimizing strategy and the function of the maximizing strategy are not interchangeable roles.
The matching is easy to remember: lower semicontinuity prevents a minimizing value from dropping suddenly at a limit point; upper semicontinuity prevents a maximizing value from rising suddenly there. On a compact space, a real-valued lower semicontinuous function attains its minimum, and a real-valued upper semicontinuous function attains its maximum.
Worked Example: The Wrong Semicontinuity Can Lose an Extremum
Consider the compact interval \([0,1]\). Define \(h(0)=1\) and \(h(x)=0\) for \(x>0\). Its infimum is 0, attained at every \(x>0\): \(h(0)=1\), while \(h(x)=0\) for every \(x>0\). In fact, this definition does attain its infimum at every \(x>0\), so it is not an example of failed minimum attainment. Instead, use the function \(r(0)=1\) and \(r(x)=x\) for \(x>0\). Then \(\inf r=0\), and no point attains 0.
At the endpoint 0, \(\liminf_{x\downarrow0}r(x)=0<r(0)=1\), so \(r\) is not lower semicontinuous there. It is upper semicontinuous at 0, since \(\limsup_{x\downarrow0}r(x)=0\leq1=r(0)\); away from 0 it is continuous. Thus compactness plus upper semicontinuity does not guarantee a minimum.
For the corresponding maximum failure, define \(s(0)=0\) and \(s(x)=1-x\) for \(x>0\). Its supremum is 1, but no point attains 1: \(s(0)=0\), and for \(x>0\), \(s(x)<1\). Since \(\limsup_{x\downarrow0}s(x)=1>s(0)\), \(s\) is not upper semicontinuous at 0. It is lower semicontinuous there. This shows why upper semicontinuity, not lower semicontinuity, is the relevant maximum-attainment condition.
The first function in that example also illustrates a useful audit habit: check the claimed extremum directly against every point of the domain. Here \(h(x)=0\) for every \(x>0\), so the infimum is attained despite the failure of lower semicontinuity at 0. A discontinuity alone is not evidence that an extremum is lost.
Check Compactness in the Actual Strategy Space
A minimax proof must establish compactness of the set to which its theorem applies, in the topology specified by the argument. A set can be bounded without being compact: for example, \((0,1)\) is bounded but not compact in the usual Euclidean topology. In infinite-dimensional spaces, even closed and bounded sets need not be compact. In statistical problems, compactness of a parameter space also does not automatically give compactness of the decision-rule space or of a space of probability kernels.
Compactness may be needed for different reasons: to attain an outer minimum or maximum, or as a hypothesis of an interchange theorem. Those are distinct claims. Verify the set, the topology, and the role compactness plays rather than citing “compactness” without specifying them.
Worked Example: Equal Values Without an Attained Saddle Point
Let \(X=(0,1)\), let \(Y=\{0\}\), and set \(G(x,0)=x\). The opponent has only one strategy, so
The two values are equal. But there is no \(x^*\in X\) with \(G(x^*,0)=0\), because every \(x^*\in(0,1)\) is strictly positive. Consequently there is no saddle point: a saddle point would in particular have to attain the minimizing value. The failure is consistent with the fact that \(X\) is not compact.
This example distinguishes a statement about values from a statement about strategies. Equality of infimum-supremum values does not assert that the infimum or supremum is attained, and does not supply a pair of strategies attaining them.
Interchange Theorems and Saddle Points
A standard sufficient result makes the required structure explicit. One version of Sion’s minimax theorem is as follows. Let \(X\) be a nonempty compact convex subset of a Hausdorff topological vector space, and \(Y\) a nonempty convex subset of a topological vector space. Suppose \(G:X\times Y\to\mathbb{R}\) is such that, for each fixed \(y\), \(G(\cdot,y)\) is lower semicontinuous and convex on \(X\), and, for each fixed \(x\), \(G(x,\cdot)\) is upper semicontinuous and concave on \(Y\). Then
This theorem gives equality of the two values under its stated assumptions. Its hypotheses must be checked with the roles correctly assigned: convexity and lower semicontinuity in the minimizing variable, concavity and upper semicontinuity in the maximizing variable, and compactness of \(X\) in the topology in use. Do not silently replace one condition with its analogue in the other variable. Also, the theorem’s equality of values should not be rewritten as an attained saddle-point claim unless attainment has been separately established.
A saddle point is stronger than equality of minimax values. Its inequalities directly establish both optimality claims, as the next result shows.
Proof. For any \(y\in Y\), the saddle inequalities give \(G(x^*,y)\leq G(x^*,y^*)\), with equality at \(y=y^*\). Therefore \(\sup_yG(x^*,y)=G(x^*,y^*)\), and \(x^*\) attains the infimum over \(x\) because \(G(x^*,y^*)\leq G(x,y^*)\leq\sup_yG(x,y)\) for each \(x\). More directly, the general order inequality and the bounds below pin down both values:
The general order inequality says the first expression is no larger than the second. Since the first is at least \(G(x^*,y^*)\) and the second is at most that value, both equal it. The saddle inequalities also show the relevant extrema are attained at \(y^*\) and \(x^*\). \(\square\)
Worked Example: Verifying a Saddle Point After Checking the Hypotheses
Take \(X=Y=[-1,1]\) and \(G(x,y)=x^2-y^2\). For fixed \(y\), the function is convex and continuous in \(x\); for fixed \(x\), it is concave and continuous in \(y\). Both strategy sets are nonempty, compact, and convex, so the stated conditions for Sion’s theorem hold.
For fixed \(x\), \(x^2-y^2\) is largest when \(y=0\), giving \(\sup_yG(x,y)=x^2\). Minimizing this over \(x\in[-1,1]\) gives 0 at \(x=0\). For fixed \(y\), the minimum over \(x\) is \(-y^2\), attained at \(x=0\). Maximizing \(-y^2\) over \(y\in[-1,1]\) gives 0 at \(y=0\). Thus both orders equal 0.
The pair \((0,0)\) is also a saddle point, verified directly:
Here the saddle conclusion is justified by checking the inequalities, not merely by observing equality of the two values.
Common Errors to Catch
- Reversing the order inequality. For minimization followed by maximization, the general direction is \(\sup_y\inf_xG\leq\inf_x\sup_yG\). Interchange requires a theorem; it is not a notational rearrangement.
- Using semicontinuity in the wrong variable. Lower semicontinuity supports minimum attainment; upper semicontinuity supports maximum attainment. In an interchange theorem, check these conditions against the player’s optimization direction.
- Invoking compactness without specifying the space. Identify the strategy set and its topology. Boundedness, compactness of a different set, or compactness in an unrelated topology does not verify the hypothesis.
- Inferring a saddle point from equal values. Equality concerns the values, which may be infima or suprema not attained by any strategy. A saddle point requires an actual pair satisfying both inequalities.
The practical audit is short but strict: write the two orders, verify the general inequality’s direction, name the theorem used for equality, and check every hypothesis in the correct variable and topology. If the conclusion mentions a saddle point, verify attainment and the saddle inequalities themselves.
Check Your Understanding
For each question, distinguish a claim about optimization values from a claim about attaining strategies.
- For a payoff minimized over \(x\) and maximized over \(y\), which of \(\sup_y\inf_xG(x,y)\) and \(\inf_x\sup_yG(x,y)\) is always no larger?
- What semicontinuity condition is matched to a minimum on a compact space? What condition is matched to a maximum?
- Why does boundedness of a strategy set in an infinite-dimensional space not, by itself, verify compactness?
- State the two inequalities that a pair must satisfy to be a saddle point.
- Can equality of minimax values hold when no minimizing strategy exists? Give the feature of the worked example that makes this possible.