The Minimax Theorem
Claim
Let \(A \in \mathbb{R}^{m \times n}\) be the payoff matrix (Neumann 1928; Dantzig 1963) of a finite two-player zero-sum game. Let \(\Delta_k = \{p \in \mathbb{R}^k_{\ge 0} : \mathbf{1}^\top p = 1\}\) denote the simplex of mixed strategies. Then
\[ \max_{x \in \Delta_m} \min_{y \in \Delta_n} x^\top A y = \min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y. \]
This common value is the minimax value of the game, and the maximum and minimum are both attained.
Setup
For fixed \(x\), the function \(y \mapsto x^\top A y\) is linear, so its minimum over \(\Delta_n\) is attained at a vertex (a pure strategy). Hence
\[ \min_{y \in \Delta_n} x^\top A y = \min_{j \in \{1, \ldots, n\}} (x^\top A)_j. \]
By symmetry,
\[ \max_{x \in \Delta_m} x^\top A y = \max_{i \in \{1, \ldots, m\}} (A y)_i. \]
Both extrema are attained because the simplex is compact and the objective is continuous.
Proof
Step 1: max-min ≤ min-max (the easy direction).
For any \(x \in \Delta_m\) and \(y \in \Delta_n\),
\[ \min_{y' \in \Delta_n} x^\top A y' \;\le\; x^\top A y \;\le\; \max_{x' \in \Delta_m} x'^\top A y. \]
The leftmost expression depends only on \(x\) and the rightmost only on \(y\). Taking \(\max_x\) of the left and \(\min_y\) of the right preserves the inequality:
\[ \max_{x \in \Delta_m} \min_{y \in \Delta_n} x^\top A y \;\le\; \min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y. \]
Step 2: max-min ≥ min-max via linear programming duality.
Consider the linear program for MAX, who commits first to a mixed strategy \(x\) and then guarantees the worst-case row inner product:
\[ \text{(P)} \qquad \max_{v, x} v \quad \text{s.t.} \quad A^\top x \ge v \mathbf{1}_n, \quad \mathbf{1}_m^\top x = 1, \quad x \ge 0. \]
The constraint \(A^\top x \ge v \mathbf{1}_n\) says \((x^\top A)_j \ge v\) for every column \(j\), i.e., \(\min_j (x^\top A)_j \ge v\). Maximizing \(v\) gives the optimal value \(v^* = \max_{x \in \Delta_m} \min_{y \in \Delta_n} x^\top A y\).
The dual LP is the corresponding problem for MIN:
\[ \text{(D)} \qquad \min_{w, y} w \quad \text{s.t.} \quad A y \le w \mathbf{1}_m, \quad \mathbf{1}_n^\top y = 1, \quad y \ge 0, \]
with optimal value \(w^* = \min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y\).
Both programs are feasible: \(x = (1/m, \ldots, 1/m)\) with \(v = \min_j (\mathbf{1}^\top A)_j / m\) is feasible for (P), and symmetrically for (D). Both have bounded optimal values because the objective is bounded by \(\max_{i,j} |A_{ij}|\) on the simplex. By the strong duality theorem of linear programming, \(v^* = w^*\).
Step 3: combine.
Step 1 gives \(v^* \le w^*\). Step 2 gives \(v^* = w^*\). Hence
\[ \max_{x \in \Delta_m} \min_{y \in \Delta_n} x^\top A y = \min_{y \in \Delta_n} \max_{x \in \Delta_m} x^\top A y. \]
The maxima and minima are attained because each LP attains its optimum on the compact feasible region. \(\blacksquare\)
Remarks
Existence of optimal strategies. The optimal \(x^*\) from (P) and \(y^*\) from (D) form a saddle point: \(x^\top A y^* \le x^{*\top} A y^* \le x^{*\top} A y\) for all \(x \in \Delta_m\), \(y \in \Delta_n\). Equivalently, \((x^*, y^*)\) is a Nash equilibrium of the zero-sum game.
Pure vs. mixed strategies. Without randomization, the analogous identity \(\max_i \min_j A_{ij} = \min_j \max_i A_{ij}\) fails in general — the gap is the standard penalty for committing first. The minimax theorem says randomization closes that gap exactly.
Perfect-information case. When the players move sequentially and observe each other’s choices (a game tree), backward induction produces pure strategies that already achieve max-min and min-max simultaneously. The recursive minimax value on a game tree is the perfect-information specialization of this theorem.
Historical note. This theorem is due to von Neumann (1928). The LP-duality proof presented here was developed later, after Dantzig’s work on linear programming made strong duality available; von Neumann’s original proof used a fixed-point argument.