Sion’s Minimax Theorem

Why Minimax Interchange Matters

In a zero-sum game, one player chooses a strategy to minimize a payoff while an opponent chooses a strategy to maximize it. The order of those choices matters: a player who moves first must allow for the other player’s best response. Sion’s minimax theorem identifies conditions under which the two possible orders nevertheless give the same value.

The theorem extends the minimax principle for finite matrix games to convex strategy sets and payoffs that need not be linear. Its hypotheses are substantive: the strategy sets must have the right geometric properties, and the payoff must bend in opposite directions for the two players. The conclusion is equality of optimization values; it does not, by itself, promise that optimal strategies are attained.

Statement of Sion’s Minimax Theorem

Definition: A real-valued function $g$ on a convex set $C$ is convex if $g(\lambda u+(1-\lambda)v)\leq \lambda g(u)+(1-\lambda)g(v)$ for all $u,v\in C$ and $0\leq\lambda\leq1$. It is concave if the reverse inequality holds. A function is lower semicontinuous if $\{u:g(u)>a\}$ is open for every real $a$, and upper semicontinuous if $\{u:g(u)<a\}$ is open for every real $a$.

Let $X$ be the minimizing player’s strategy set and $Y$ the maximizing player’s strategy set. Both are convex subsets of real topological vector spaces, and assume $X$ is compact. For the compact-strategy-sets version emphasized here, $Y$ is compact as well. Compactness of $Y$ is not needed in the stated version of the theorem.

Theorem (Sion’s Minimax Theorem): Let $f:X\times Y\to\mathbb{R}$. Suppose that, for each fixed $y\in Y$, $f(\,\cdot\,,y)$ is lower semicontinuous and convex on $X$, and, for each fixed $x\in X$, $f(x,\,\cdot\,)$ is upper semicontinuous and concave on $Y$. Then $$ \inf_{x\in X}\sup_{y\in Y} f(x,y) = \sup_{y\in Y}\inf_{x\in X} f(x,y). $$ The equality is understood in the extended real numbers if an optimization value is infinite.

The orientation is important. The variable being minimized has a convex payoff section; the variable being maximized has a concave payoff section. For example, with $x$ minimizing and $y$ maximizing, convexity in $x$ and concavity in $y$ are the relevant conditions—not the reverse. The semicontinuity assumptions are also oriented: lower semicontinuity in $x$, upper semicontinuity in $y$.

The left side lets the minimizing player choose $x$ first and then accounts for the maximizing player’s best response. The right side lets the maximizing player choose $y$ first and accounts for the minimizing player’s best response. Sion’s theorem says these two worst-case values agree under its hypotheses.

Three Worked Applications

Worked Example: A Bilinear Payoff on Intervals

Let $X=[-1,1]$, $Y=[-2,3]$, and $f(x,y)=xy$, with $x$ minimizing and $y$ maximizing. The sets are compact and convex. For fixed $y$, the function $xy$ is affine, hence convex and continuous in $x$; for fixed $x$, it is affine, hence concave and continuous in $y$. Sion’s theorem applies.

First compute the maximizing response for each $x$. If $x\geq0$, then $xy$ increases with $y$, so its maximum is $3x$. If $x<0$, it decreases with $y$, so its maximum is $-2x$. Therefore

\sup_{y\in[-2,3]}xy= \begin{cases} -2x,&x<0,\\ 0,&x=0,\\ 3x,&x>0. \end{cases}

This quantity is nonnegative for every $x$ and equals zero at $x=0$. Thus $\inf_x\sup_y xy=0$.

In the other order, if $y\geq0$, minimizing $xy$ over $x\in[-1,1]$ gives $-y$, at $x=-1$. If $y<0$, the minimum is $y$, at $x=1$. Hence $\inf_x xy=-|y|$, whose supremum over $y\in[-2,3]$ is zero, attained at $y=0$. The two values agree, as the theorem predicts.

Worked Example: A Nonlinear Convex-Concave Payoff

Take $X=Y=[-1,1]$ and $f(x,y)=x^2+2xy-y^2$. For fixed $y$, the second derivative in $x$ is $2$, so the section is convex. For fixed $x$, the second derivative in $y$ is $-2$, so the section is concave. The sections are continuous, and both strategy sets are compact and convex.

For fixed $x$, the derivative with respect to $y$ is $2x-2y$, which vanishes at $y=x$. Since $x\in[-1,1]$, this maximizer lies in $Y$. Substitution gives

\sup_{y\in[-1,1]} f(x,y) =f(x,x)=x^2+2x^2-x^2=2x^2.

The minimum of $2x^2$ over $X$ is zero, attained at $x=0$. In the reverse order, for fixed $y$, the derivative with respect to $x$ is $2x+2y$, which vanishes at $x=-y\in X$. Thus

\inf_{x\in[-1,1]} f(x,y) =f(-y,y)=y^2-2y^2-y^2=-2y^2.

The maximum of $-2y^2$ over $Y$ is zero, attained at $y=0$. Both optimization orders therefore give zero. In fact, $(0,0)$ is a saddle point: $f(0,y)=-y^2\leq0=f(0,0)\leq f(x,0)=x^2$.

Worked Example: Mixed Strategies in a Finite Game

Consider the payoff matrix

A= \begin{pmatrix} 0&4\\ 2&1 \end{pmatrix},

where the row player minimizes and the column player maximizes. Let $p$ be the probability of choosing row 1 and $q$ the probability of choosing column 1. The mixed-strategy sets are intervals $[0,1]$, and expected payoff is affine in each probability. It is therefore convex in the minimizing variable and concave in the maximizing variable, so Sion’s theorem applies.

Against a column strategy with probability $q$ on column 1, the payoffs of the two pure rows are $4(1-q)=4-4q$ and $2q+1(1-q)=1+q$. A minimizing mixture makes these equal:

4-4q=1+q \quad\Longrightarrow\quad q=\frac35, \qquad 4-4q=1+q=\frac85.

The expected payoff of a row mixture with probability $p$ on row 1 is $2(1-p)$ against column 1 and $4p+1(1-p)=1+3p$ against column 2. The maximizing mixture makes these equal:

2(1-p)=1+3p \quad\Longrightarrow\quad p=\frac15, \qquad 2(1-p)=1+3p=\frac85.

At $p=1/5$ and $q=3/5$, every pure response by either player yields expected payoff $8/5$. The minimum of the maximum payoff and the maximum of the minimum payoff are both $8/5$. This example connects the continuous convex-set statement to the finite matrix-game setting.

What Equality Does—and Does Not—Guarantee

The theorem concerns equality of two values. A saddle point is a stronger conclusion about particular strategies. For the minimizing player’s strategy $x^*$ and the maximizing player’s strategy $y^*$, the saddle inequalities are

f(x^*,y)\leq f(x^*,y^*)\leq f(x,y^*) \qquad\text{for every }x\in X,\ y\in Y.

If these inequalities hold, then $y^*$ is a best response to $x^*$, and $x^*$ is a best response to $y^*$. The common payoff is the minimax value. However, equality of the infimum and supremum values alone does not assert that either outer optimization is attained. Additional conditions ensuring attainment are needed to conclude that a saddle point exists.

Result: If the minimax equality holds and there are $x^*\in X$ and $y^*\in Y$ such that $x^*$ attains $\inf_x\sup_y f(x,y)$ and $y^*$ attains $\sup_y\inf_x f(x,y)$, then $(x^*,y^*)$ is a saddle point.

To verify the result, write the common value as $V$. For every $y\in Y$, $f(x^*,y)\leq\sup_{u\in Y}f(x^*,u)=V$. For every $x\in X$, $f(x,y^*)\geq\inf_{u\in X}f(u,y^*)=V$. Taking $y=y^*$ in the first inequality and $x=x^*$ in the second shows $f(x^*,y^*)=V$. The two inequalities are therefore precisely the saddle inequalities. $\square$

There is also a general inequality that requires no convexity or compactness. For every real-valued payoff on nonempty strategy sets,

\sup_{y\in Y}\inf_{x\in X} f(x,y) \leq \inf_{x\in X}\sup_{y\in Y} f(x,y).

Indeed, for any fixed $x$ and $y$, $\inf_{u\in X}f(u,y)\leq f(x,y)\leq\sup_{v\in Y}f(x,v)$. Thus the left-hand quantity is at most $\sup_{v\in Y}f(x,v)$ for every $x$; taking the infimum over $x$ proves the inequality. Sion’s theorem supplies conditions that close this possible gap.

Common Mistakes and Practical Use

Reversing the curvature conditions. For a minimizing variable $x$, the payoff must be convex in $x$; for a maximizing variable $y$, it must be concave in $y$. Reversing these conditions does not satisfy the theorem.
Checking continuity but ignoring convexity. Continuity supports the semicontinuity conditions, but does not replace convexity and concavity. A continuous payoff can still fall outside Sion’s theorem.
Claiming a saddle point from equality alone. The theorem equates infimum-supremum values. Attainment of the relevant extrema must also be established before asserting the existence of optimal strategies.
Forgetting which strategy set must be compact. In this orientation, Sion’s theorem needs the minimizing set $X$ to be compact; the maximizing set need only be convex. Assuming compactness of both is a convenient sufficient condition, but not the most general one.

In statistical decision problems, this theorem is useful when a risk or payoff can be expressed over convex strategy sets and has the required curvature. It provides a rigorous route from one order of worst-case optimization to the other. Checking the theorem’s hypotheses is part of the argument: the equality is not justified merely because the two sides look like natural alternatives.

Check Your Understanding

Use the minimizing-variable and maximizing-variable orientation throughout.

Which semicontinuity and curvature conditions must $f$ satisfy in its $x$-section when $x$ is minimized?
In the theorem as stated, which strategy set must be compact? What additional convenience is gained if $Y$ is compact too?
Why does the inequality $\sup_y\inf_x f(x,y)\leq\inf_x\sup_y f(x,y)$ hold even when Sion’s hypotheses fail?
What extra fact, beyond minimax equality, is used to conclude that a pair of strategies is a saddle point?
For the payoff $f(x,y)=x^2+2xy-y^2$, identify which variable has a convex section and which has a concave section.

What You'll Learn