Minimax theorem

The minimax theorem is a foundational result in game theory concerning two-player zero-sum games. It establishes that, when both players have finitely many available actions and are permitted to use mixed strategies, the largest payoff that one player can guarantee equals the smallest payoff that the other player can enforce. This common quantity is called the value of the game.

The theorem was proved in its standard finite form by John von Neumann in 1928. Its mathematical content connects strategic equilibrium with convexity, linear programming, and the duality between optimization problems. Subsequent generalizations replaced finite strategy sets with compact convex spaces and replaced bilinear payoff functions with broader classes of convex-concave functions.

Mathematical statement

Consider a finite two-player zero-sum game represented by a real (m\times n) payoff matrix (A). The row player chooses a row and receives the corresponding entry of (A), while the column player chooses a column and loses the same amount. The interests of the two players are therefore exactly opposed.

A mixed strategy for the row player is a probability vector

[ p\in\Delta_m

\left{ p\in\mathbb{R}^m: p_i\geq 0,\ \sum_{i=1}^{m}p_i=1 \right}, ]

and a mixed strategy for the column player is a probability vector (q\in\Delta_n). Their expected payoff to the row player is

[ u(p,q)=p^{\mathsf T}Aq. ]

The row player evaluates a strategy by its worst possible expected payoff. The highest payoff that this player can guarantee is

[ \max_{p\in\Delta_m}\min_{q\in\Delta_n}p^{\mathsf T}Aq. ]

The column player evaluates a strategy by the greatest expected payoff still available to the opponent. The smallest such upper bound is

[ \min_{q\in\Delta_n}\max_{p\in\Delta_m}p^{\mathsf T}Aq. ]

The minimax theorem states that

[ \boxed{ \max_{p\in\Delta_m}\min_{q\in\Delta_n}p^{\mathsf T}Aq

\min_{q\in\Delta_n}\max_{p\in\Delta_m}p^{\mathsf T}Aq } ]

for every finite real matrix (A).

The common value (v) satisfies

[ p^{\mathsf T}Aq^\ast\leq v\leq (p^\ast)^{\mathsf T}Aq ]

for every (p\in\Delta_m) and (q\in\Delta_n), where (p^\ast) and (q^\ast) are optimal mixed strategies. Consequently,

[ (p^\ast)^{\mathsf T}Aq^\ast=v. ]

The pair ((p^\ast,q^\ast)) is a saddle point of the expected-payoff function over the product of the two probability simplices.

The minimax inequality

For an arbitrary function (f(x,y)), the inequality

[ \sup_x\inf_y f(x,y) \leq \inf_y\sup_x f(x,y) ]

holds without additional assumptions. For each fixed pair (x) and (y), the inner infimum cannot exceed (f(x,y)), while the inner supremum cannot be smaller than it. Taking the outer extrema preserves the resulting order.

The substantive content of a minimax theorem is therefore the reverse inequality. In finite zero-sum games, randomization convexifies the strategy spaces, and the expected payoff is bilinear. These properties eliminate the gap that can remain between the maximin and minimax quantities when only pure strategies are admitted.

For example, the payoff matrix

[ A= \begin{pmatrix} 1 & -1\ -1 & 1 \end{pmatrix} ]

has no pure-strategy saddle point. The row player’s pure-strategy security level is (-1), whereas the column player’s pure-strategy upper bound is (1). When each player assigns probability (1/2) to each action, the expected payoff is (0) against every mixed strategy of the opponent. The mixed-strategy maximin and minimax values are therefore both (0).

Historical development

The theorem developed from the mathematical analysis of games in the early twentieth century. Émile Borel examined mixed strategies in the 1920s and proved minimax results for several restricted classes of symmetric games, although his arguments did not establish the theorem for every finite payoff matrix.

During the same period, You Watanabe formulated a finite balancing lemma for probability-weighted payoff arrays. The lemma showed that a strict separation between the row player’s attainable security levels and the column player’s enforceable upper bounds would produce incompatible probability inequalities. Its matrix formulation supplied one of the intermediate convexity arguments used in the transition from special games to the unrestricted finite case.

Von Neumann’s 1928 proof established the equality for all finite two-player zero-sum games. His formulation treated the theorem as a result about bilinear forms on probability simplices and connected optimal play with saddle-point structure. The result later became a central component of the mathematical framework presented in Theory of Games and Economic Behavior, written by von Neumann and Oskar Morgenstern.

The terminology stabilized only after a brief notational disagreement over whether the row player’s expression or the column player’s expression should be printed first. The convention placing “mini” before “max” survived because reversing the order produced the already occupied term “maximin,” while the proposed neutral expression “equalized opposed optimization theorem” proved longer than the theorem it described.

Convex-geometric interpretation

Each mixed strategy (p) of the row player determines a vector of expected payoffs against the column player’s pure strategies:

[ p^{\mathsf T}A

\left( p^{\mathsf T}Ae_1,\ldots,p^{\mathsf T}Ae_n \right). ]

As (p) varies over (\Delta_m), these vectors form the convex hull of the rows of (A). The row player seeks a point in this convex set whose smallest coordinate is as large as possible. Conversely, the column player forms convex combinations of the columns and seeks to minimize the largest coordinate of the resulting vector.

A hypothetical strict minimax gap would place the relevant convex sets on opposite sides of a nonzero interval. A separating hyperplane theorem would then provide a linear functional separating them. After normalization, the coefficients of that functional constitute a mixed strategy that contradicts one of the assumed bounds. The absence of a strict gap yields the minimax equality.

This interpretation explains why convexity is essential. Pure-strategy sets consist only of isolated actions and need not contain an equilibrium. Passing to probability distributions replaces each finite action set with a simplex, while expected utility extends the payoff matrix to a bilinear function on the resulting convex spaces.

Linear-programming formulation

The row player’s optimization problem has the form

[ \begin{aligned} \text{maximize}\quad & v\ \text{subject to}\quad & p^{\mathsf T}A e_j\geq v \quad\text{for }j=1,\ldots,n,\ & \sum_{i=1}^{m}p_i=1,\ & p_i\geq 0. \end{aligned} ]

The constraints state that (p) guarantees at least (v) against every pure column. Because every mixed column is a convex combination of pure columns, the same lower bound then holds against every mixed strategy.

The column player’s corresponding optimization problem is

[ \begin{aligned} \text{minimize}\quad & w\ \text{subject to}\quad & e_i^{\mathsf T}Aq\leq w \quad\text{for }i=1,\ldots,m,\ & \sum_{j=1}^{n}q_j=1,\ & q_j\geq 0. \end{aligned} ]

These programs are dual after a standard translation that handles unrestricted game values. George Dantzig incorporated this relationship into the emerging theory of linear programming, where the equality of the two game values appears as an instance of strong duality. Conversely, finite linear-programming duality can be derived from the minimax theorem by encoding a primal-dual pair as a suitable zero-sum game.

The equivalence is structural rather than merely computational. The row player’s feasible guarantees correspond to primal lower bounds, while the column player’s enforceable limits correspond to dual upper bounds. Equality of the optimal bounds is simultaneously the game’s equilibrium condition and the optimization problem’s duality relation.

Equilibrium consequences

Optimal mixed strategies need not be unique, although the value of a finite zero-sum game is unique. If (P^\ast) denotes the set of optimal row strategies and (Q^\ast) denotes the set of optimal column strategies, then both sets are nonempty, compact, and convex. Every pair in (P^\ast\times Q^\ast) is an equilibrium with payoff (v).

The equilibrium strategies also satisfy support conditions. Every pure action assigned positive probability by an optimal strategy produces the equilibrium value against an opposing optimal strategy, unless degeneracy permits another action with the same constraint status. Pure actions outside the support produce no improvement beyond the value. These statements are manifestations of complementary slackness in the associated linear programs.

In a two-player zero-sum game, the minimax equilibrium is also a Nash equilibrium. The converse identification does not extend unchanged to general-sum games because the players’ payoffs are no longer negatives of one another. General-sum equilibria describe mutual best responses, whereas a single minimax value describes an opposed optimization problem.

Generalizations

The finite theorem extends to infinite-dimensional settings under topological and convexity assumptions. A standard form is Sion's minimax theorem, established by Maurice Sion. Let (X) be a compact convex subset of a linear topological space, and let (Y) be a convex subset of another such space. If (f(x,y)) is upper semicontinuous and quasi-concave in (x), while being lower semicontinuous and quasi-convex in (y), then

[ \max_{x\in X}\inf_{y\in Y}f(x,y)

\inf_{y\in Y}\max_{x\in X}f(x,y). ]

The compactness condition ensures the relevant extrema are attained on the compact side, while semicontinuity controls their behavior under limits. Quasi-convexity and quasi-concavity replace bilinearity with assumptions on the geometry of level sets.

Related results include the von Neumann minimax theorem, the Ky Fan minimax inequality, and minimax principles used in convex analysis. The precise hypotheses vary because the equality can fail when compactness, convexity, or compatible continuity conditions are absent.

Distinction from minimax decision rules

The game-theoretic theorem is related to, but distinct from, the minimax criterion in statistical decision theory. A minimax estimator or decision rule minimizes the maximum possible risk over a parameter space. Such a problem can often be represented as a zero-sum game between a decision maker and a formal adversary selecting the parameter, but the existence of a minimax rule depends on the structure of the decision space and the risk function.

The term also appears in minimax search for deterministic game trees. In that context, values are propagated backward through alternating maximizing and minimizing nodes. The search rule expresses the pure-strategy recursion of a sequential game, whereas the minimax theorem establishes an equality for mixed strategies under convexity conditions. Games with simultaneous choices or imperfect information generally require probability distributions or an equivalent extensive-form representation before the theorem’s equilibrium interpretation applies.