A Separation Proof of Minimax Interchange

Why Separation Produces a Mixed Strategy

A finite-dimensional minimax problem can be represented by a set of payoff vectors. Each coordinate records the payoff against one of the opponent’s pure strategies. A decision maker chooses a vector from the feasible set, while the opponent can select a coordinate or randomize across coordinates. The key question is whether the worst-coordinate payoff can be interchanged with the opponent’s best mixed strategy.

Convexity is central: it means mixtures of feasible payoff vectors remain feasible. Compactness ensures that the relevant extrema exist. Under these conditions, a separating hyperplane supplies a nonnegative normal vector; after normalization, that vector is a probability distribution over the coordinates.

Definition: Let $A$ be a nonempty compact convex subset of $\mathbb{R}^m$. A vector $a=(a_1,\ldots,a_m)\in A$ is a feasible payoff vector, and its worst-coordinate payoff is $\max_{1\le i\le m}a_i$. The opponent’s mixed strategy is a vector $q=(q_1,\ldots,q_m)$ in the probability simplex $\Delta_m=\{q\in\mathbb{R}^m:q_i\ge0,\ \sum_{i=1}^m q_i=1\}$; its payoff against $a$ is $q\cdot a=\sum_{i=1}^m q_i a_i$.

The two orders of optimization are $\min_{a\in A}\max_i a_i$ and $\max_{q\in\Delta_m}\min_{a\in A}q\cdot a$. The first asks for a feasible vector whose largest coordinate is as small as possible. The second asks for a mixed coordinate choice that guarantees as large a payoff as possible against every feasible vector.

The Minimax Interchange Theorem

Theorem: If $A\subset\mathbb{R}^m$ is nonempty, compact, and convex, then $$ \min_{a\in A}\max_{1\le i\le m}a_i = \max_{q\in\Delta_m}\min_{a\in A}q\cdot a. $$ Both extrema are attained.

Write $v=\min_{a\in A}\max_i a_i$. The minimum exists because $a\mapsto\max_i a_i$ is continuous and $A$ is compact. For any $q\in\Delta_m$ and $a\in A$, $q\cdot a\le\max_i a_i$, since a weighted average of coordinates cannot exceed their maximum. Therefore $$ \min_{a\in A}q\cdot a\le\min_{a\in A}\max_i a_i=v. $$ Taking the maximum over $q$ proves one direction of the theorem. The other direction comes from separation.

Separation fact: If $K$ is a nonempty compact convex set and $C$ is a nonempty closed convex set in a finite-dimensional Euclidean space, with $K\cap C=\varnothing$, then there is a nonzero vector $u$ such that $\inf_{x\in K}u\cdot x>\sup_{y\in C}u\cdot y$, provided the supremum on the right is finite.

For completeness, in this setting the separation fact follows from nearest points. The distance between $K$ and $C$ is positive: the function $x\mapsto d(x,C)$ is continuous, is positive for each $x\in K$, and attains a positive minimum on compact $K$. A pair $x_0\in K,y_0\in C$ attaining the distance exists. Indeed, take a sequence of pairs whose distances approach the infimum. The $K$-coordinates are bounded, and the $C$-coordinates are bounded as well because the distances are bounded; subsequences converge, with the $C$-limit still in $C$ by closedness.

Set $u=x_0-y_0$, which is nonzero. Convexity and minimality imply $u\cdot(x-x_0)\ge0$ for every $x\in K$: moving from $x_0$ a small distance toward $x$ cannot decrease the squared distance to $y_0$. The same argument moving $y_0$ toward $y\in C$ gives $u\cdot(y-y_0)\le0$. Consequently, $$ u\cdot x\ge u\cdot x_0 =u\cdot y_0+\|u\|^2 >u\cdot y_0\ge u\cdot y. $$ Thus $u$ strictly separates the sets, as claimed.

Proof by Separating a Lower Orthant

Fix any real $t<v$, and define the closed lower orthant $$ C_t=\{c\in\mathbb{R}^m:c_i\le t\text{ for every }i\}. $$ The sets $A$ and $C_t$ are disjoint. If some $a$ belonged to both, then $\max_i a_i\le t$, contradicting $t<v$. Apply the separation fact to obtain a nonzero $u$ with $$ \inf_{a\in A}u\cdot a>\sup_{c\in C_t}u\cdot c. $$ Every coordinate of $u$ must be nonnegative. If $u_j<0$ for some $j$, one could send $c_j$ to $-\infty$ while keeping the other coordinates fixed within $C_t$, making $u\cdot c$ arbitrarily large. This would contradict the finite upper bound supplied by separation. Since $u\ne0$, $\sum_i u_i>0$. For nonnegative $u$, the maximum of $u\cdot c$ over $C_t$ is $t\sum_i u_i$, attained at $c=(t,\ldots,t)$.

Normalize the separating normal by setting $q_i=u_i/\sum_j u_j$. Then $q\in\Delta_m$, and division by the positive sum gives $$ \min_{a\in A}q\cdot a>t. $$ This proves that for every $t<v$, some mixed strategy guarantees more than $t$. To obtain one strategy that reaches $v$, take $t_k=v-1/k$ for positive integers $k$, and choose $q^{(k)}\in\Delta_m$ with $\min_{a\in A}q^{(k)}\cdot a>t_k$. The simplex is compact, so a subsequence converges to some $q^*\in\Delta_m$.

The function $g(q)=\min_{a\in A}q\cdot a$ is continuous. In fact, compactness makes $M=\max_{a\in A}\|a\|$ finite, and the Cauchy–Schwarz inequality gives $|g(q)-g(r)|\le M\|q-r\|$. Taking the limit along the convergent subsequence yields $g(q^*)\ge v$. The easy inequality already proved gives $g(q^*)\le v$; hence $g(q^*)=v$. Finally, continuity of $g$ and compactness of $\Delta_m$ ensure the maximum over $q$ is attained. The minimum over $a$ was attained by compactness of $A$. This proves the theorem. $\square$

Set a threshold below the value.
For $t<v$, the feasible payoff set cannot meet the region in which every coordinate is at most $t$.

Separate the sets.
The normal must have nonnegative coordinates, since the lower orthant extends without bound in every negative coordinate direction.

Normalize the normal.
Dividing by the sum of its coordinates turns the normal into a probability vector over the $m$ coordinates.

Approach the value.
Use compactness of the simplex to take a limit of mixed strategies that guarantee thresholds increasing to $v$.

Worked Examples

Worked Example: A Convex Hull with a Fixed Coordinate Sum

Let $A$ be the convex hull of $v_1=(2,0,0)$, $v_2=(0,2,3)$, and $v_3=(1,1,0)$. Find both sides of the minimax equality. A convex combination has weights $\alpha,\beta,\gamma\ge0$, with $\alpha+\beta+\gamma=1$, and coordinates $$ a=(2\alpha+\gamma,\ 2\beta+\gamma,\ 3\beta). $$ For every such vector, $a_1+a_2=2$. Thus at least one of $a_1,a_2$ is at least $1$, so $\max_i a_i\ge1$. The equal-weight combination has payoff vector $$ \frac13v_1+\frac13v_2+\frac13v_3=(1,1,1), $$ whose largest coordinate is $1$. Therefore $\min_{a\in A}\max_i a_i=1$.

Now choose $q=(1/2,1/2,0)$. For every $a\in A$, $q\cdot a=(a_1+a_2)/2=1$, so $\min_{a\in A}q\cdot a=1$. The theorem’s equality is verified directly: both sides equal $1$.

Worked Example: Balancing Two Payoff Coordinates

Let $A$ be the line segment joining $v_1=(2,0)$ and $v_2=(0,3)$. A point on this segment is $a(\lambda)=\lambda v_1+(1-\lambda)v_2=(2\lambda,3(1-\lambda))$, for $0\le\lambda\le1$. The largest coordinate is minimized when the two coordinates are equal: $2\lambda=3(1-\lambda)$, so $5\lambda=3$, $\lambda=3/5$, and both coordinates equal $6/5$. To verify that this is the minimum, if the largest coordinate were less than $6/5$, both $2\lambda<6/5$ and $3(1-\lambda)<6/5$ would hold. These imply $\lambda<3/5$ and $\lambda>3/5$, a contradiction. Thus the left side is $6/5$.

For the opponent, write $q=(q_1,1-q_1)$. The minimum payoff over the segment is the smaller of the endpoint payoffs, $2q_1$ and $3(1-q_1)$, because a linear function on a line segment attains its minimum at an endpoint. These two values are equal when $2q_1=3(1-q_1)$, giving $q_1=3/5$ and $q_2=2/5$. At this strategy, each endpoint pays $6/5$, and every point on the segment does too. Hence the right side is also $6/5$.

Worked Example: Three Coordinates and a Balancing Strategy

Let $A$ be the convex hull of $v_1=(2,0,0)$, $v_2=(0,2,0)$, and $v_3=(0,0,3)$. A feasible vector with weights $\alpha,\beta,\gamma$ has coordinates $(2\alpha,2\beta,3\gamma)$, where the nonnegative weights sum to $1$. The mixed weights $(\alpha,\beta,\gamma)=(3/8,3/8,1/4)$ produce $$ a=(2(3/8),2(3/8),3(1/4))=(3/4,3/4,3/4). $$ This establishes an upper bound of $3/4$ on the left side. For the matching lower bound, any $a\in A$ satisfies $$ a_1+a_2+a_3=2\alpha+2\beta+3\gamma =2+\gamma\ge2. $$ Therefore at least one of its three coordinates is at least $2/3$, which is not yet the desired bound. A sharper argument uses the fact that if every coordinate were less than $3/4$, then $\alpha<3/8$, $\beta<3/8$, and $\gamma<1/4$, so $\alpha+\beta+\gamma<1$, a contradiction. Thus the minimum possible largest coordinate is $3/4$.

Take $q=(3/8,3/8,1/4)$. Its payoffs against the three vertices are $q\cdot v_1=3/4$, $q\cdot v_2=3/4$, and $q\cdot v_3=3/4$. A linear function on a convex hull is a convex combination of its values at the vertices, so its minimum over $A$ is $3/4$. Both sides equal $3/4$.

Common Mistakes and Why the Proof Matters

A tempting but invalid shortcut is to argue that a separating hyperplane exists and then treat its normal as a mixed strategy without checking its signs. A probability vector must be nonnegative and sum to one. Here, nonnegativity is not automatic from the word “separating”; it follows specifically from the geometry of the lower orthant. Normalization is valid only after noting that a nonzero nonnegative vector has a strictly positive coordinate sum.

Another pitfall is to infer a constant coordinate sum from examples without checking every vector. For instance, in the first worked example the vector $(1,1,0)$ has coordinate sum $2$, not $3$. The correct invariant is $a_1+a_2=2$, which implies $\max(a_1,a_2)\ge1$. The opponent’s matching strategy is $q=(1/2,1/2,0)$, not the uniform vector: it gives $q\cdot a=1$ for every feasible vector. Indeed, the uniform vector gives only $2/3$ against $(1,1,0)$.

The geometric argument also explains why compactness and convexity have distinct roles. Compactness gives nearest points and guarantees attainment; convexity gives the projection inequalities used to separate the sets. The limiting step matters because the set $A$ can touch the threshold orthant at $t=v$, so strict separation at the value itself is not generally available. Separating at every lower threshold and taking a limit avoids claiming a strict gap where none may exist.

Key takeaway: For a nonempty compact convex payoff set in finite dimensions, the least possible worst coordinate equals the best guaranteed payoff from a mixed coordinate choice. Separation from lower orthants constructs the mixed strategy that proves the reverse minimax inequality.

Check Your Understanding

Use the theorem and proof structure to answer the following questions.

Which assumption ensures that the minimum of $a\mapsto\max_i a_i$ is attained, and which assumption supports the projection argument in the separation proof?
Why must every coordinate of the separating normal be nonnegative when the other set is a lower orthant?
For the segment joining $(4,0)$ and $(0,2)$, find a point minimizing the largest coordinate and an opponent’s mixed strategy achieving the same value.
Explain why separation at every $t<v$ does not by itself give a single mixed strategy attaining $v$, and identify the compactness argument that completes the proof.
For a payoff vector $a$ and a probability vector $q$, prove directly that $q\cdot a\le\max_i a_i$.