Minimax Theorem

In a finite zero-sum game the best guaranteed floor equals the best enforced ceiling, so optimal mixed play on both sides meets at one value.

The row floor rises to meet the falling column ceiling, and they touch exactly at the saddle value both sides guarantee

Why Does This Exist?

Zero-sum games define two numbers: the most row can guarantee (maxmin) and the least column can enforce (minmax). In general the guarantee trails the cap: $\max \min \le \min \max$ always (weak duality, one line of algebra). Von Neumann's minimax theorem (1928) says finite zero-sum games close the gap: equality holds, and both sides attain it with mixed strategies. That equality is why "the value of the game" is well-defined at all.

Beyond games, the theorem is the seed of duality. Linear programming duality, KKT conditions, and Lagrangian saddle points all echo it: a max-min and a min-max meeting under convexity. This page states the theorem, proves the easy half, sketches why the hard half holds, and computes the meeting point on $2 \times 2$ matching pennies.

The one idea you need first

A saddle point $(x^*, y^*)$ satisfies $f(x, y^*) \le f(x^*, y^*) \le f(x^*, y)$ for all $x, y$ : maximal in one argument, minimal in the other. Equality of maxmin and minmax is exactly the existence of such a point.

Think of It Like This

Agreeing on a price with a broker in the middle

A seller names the lowest acceptable price across buyers; a buyer names the highest tolerable price across sellers. Always, the best guaranteed sale trails the best enforced purchase: the seller's floor sits under the buyer's ceiling.

Minimax says that with randomization allowed and rules finite, a broker can close the spread to zero: the seller's best randomized offer and the buyer's best randomized bid land on one price neither can improve alone. Without mixing (take-it-or-leave-it bids), the spread persists. Mixing is the broker.

How It Actually Works

For finite $A$ with row mix $x$ and column mix $y$ over simplices (convex compact sets) and bilinear payment $x^T A y$ (convex-concave):

\max_x \min_y x^T A y = \min_y \max_x x^T A y = v

Easy half ( $\le$ ). For any fixed $x, y$ : $\min_{y'} x^T A y' \le x^T A y \le \max_{x'} {x'}^T A y$ . Take $\max_x$ left and $\min_y$ right: maxmin $\le$ minmax. No assumptions needed.

Hard half ( $\ge$ ). Separation of convex sets: row's achievable payoff region against all column replies is convex (mixes convexify it), so a hyperplane separates it from anything above the minmax cap, yielding the attaining $x^*$ . Equivalently, no-regret learning dynamics (both sides minimizing regret) converge in average to the value, which proves existence constructively.

Worked example

Matching pennies $A = [[1,-1],[-1,1]]$ . Row floor for mix $(p, 1-p)$ : $\min(2p - 1, 1 - 2p)$ , maximized at $2p-1 = 1-2p$ , $p = 1/2$ , floor $0$ . Column cap for $(q,1-q)$ : $\max(2q - 1, 1 - 2q)$ , minimized at $q = 1/2$ , cap $0$ . They meet at $v = 0$ . Without mixing: row's best pure floor is $-1$ , column's best pure cap $+1$ : a gap of $2$ that mixing closes exactly.

Code

1def floor(p: float) -> float:2    return min(2 * p - 1, 1 - 2 * p)  # row guarantee mixing (p, 1-p)3
4
5def cap(q: float) -> float:6    return max(2 * q - 1, 1 - 2 * q)  # column enforcement mixing (q, 1-q)7
8
9best_floor = max((floor(p / 100), p / 100) for p in range(101))10best_cap = min((cap(q / 100), q / 100) for q in range(101))11print(best_floor, best_cap)  # -> (0.0, 0.5) (0.0, 0.5)

Best floor $0$ at $p = 1/2$ meets best cap $0$ at $q = 1/2$ : the theorem's equality on one line of output.

Watch Out For

Quoting minimax for non-convex losses

The theorem needs convex-concave structure (or finite mixes convexifying it). Deep GAN objectives are non-convex in parameters, so maxmin can trail minmax strictly and simultaneous gradient dynamics can cycle. If your GAN oscillates, the minimax equality you assumed is the first suspect.

Reading the value as a strategy

The value $v$ is a payoff, not a playbook: many mixes can attain it, and the attaining pair need not be unique. Teams that "play the value" without extracting the attaining strategies have a number, not a policy. Always recover $x^*, y^*$ alongside $v$ .

The Quick Version

Weak duality maxmin $\le$ minmax holds everywhere from one inequality chain.
Von Neumann closes the gap for finite zero-sum games via mixing.
The meeting point is a saddle: maximal in $x$ , minimal in $y$ .
Matching pennies meets at $v = 0$ with $(1/2, 1/2)$ each; pure play leaves a gap of $2$ .
The proof routes through convex separation or no-regret learning dynamics.
Non-convex objectives void the equality, which is why GAN practice diverges from GAN theory.