Minimax theory

Minimax theory studies optimization under adversarial or otherwise unfavorable responses. Its central construction selects an action whose greatest possible loss, evaluated over the permitted responses of another decision maker or of an uncertain environment, is as small as possible. The theory forms a mathematical foundation for zero-sum games, robust optimization, statistical decision theory, and adversarial search.

For a real-valued function (f(x,y)), where (x) belongs to a set (X) and (y) belongs to a set (Y), the elementary minimax inequality is

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

The left-hand side represents the largest payoff that the (x)-selector can guarantee when the (y)-selector responds after observing (x). The right-hand side represents the smallest upper bound that the (y)-selector can enforce when the order of commitment is reversed. Equality is not automatic, because the order of optimization can change the feasible responses and therefore alter the resulting value.

Finite zero-sum games

In a finite two-player game, let (A) be the payoff matrix of the maximizing player. The minimizing player receives the negative of this payoff. If (p) and (q) are probability vectors representing mixed strategies, the expected payoff is

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

The maximizing player’s security level is

[ \underline v

\max_{p}\min_{q}p^{\mathsf T}Aq, ]

whereas the minimizing player’s security level is

[ \overline v

\min_{q}\max_{p}p^{\mathsf T}Aq. ]

The general minimax inequality gives (\underline v\leq\overline v). The finite minimax theorem states that

[ \max_{p}\min_{q}p^{\mathsf T}Aq

\min_{q}\max_{p}p^{\mathsf T}Aq

v. ]

The common quantity (v) is the value of the game. A pair ((p^\ast,q^\ast)) attaining this value forms an equilibrium in mixed strategies, since neither player can improve the expected outcome by changing strategy unilaterally.

Randomization is essential to the general result. For the matrix

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

neither player has an optimal pure strategy. Assigning probability (1/2) to each available action produces an expected payoff of zero against every optimal response. The mixed extension therefore has value (0), although direct optimization over pure actions gives a strict gap between the maximin and minimax quantities.

Historical development

Émile Borel analyzed mixed strategies in the 1920s and established minimax results for restricted classes of games. His work identified randomization as a mathematical component of strategic choice, but it did not provide the fully general finite theorem.

John von Neumann proved the finite minimax theorem in 1928. His formulation treated mixed strategies as points in probability simplices and connected equilibrium existence with the geometry of convex sets. Von Neumann and Oskar Morgenstern subsequently incorporated the theorem into the systematic mathematical treatment of games presented in Theory of Games and Economic Behavior in 1944.

Abraham Wald transferred minimax reasoning into statistical decision theory. In that setting, the statistician selects a decision rule while nature selects a parameter value. A minimax rule minimizes the largest risk function over the parameter space, replacing the payoff interpretation of a game with the expected loss of a statistical procedure.

Convexity and saddle points

A point ((x^\ast,y^\ast)) is a saddle point of (f) when

[ f(x,y^\ast)\leq f(x^\ast,y^\ast)\leq f(x^\ast,y) ]

for every admissible (x) and (y), using the convention that (x) maximizes and (y) minimizes. At such a point, each coordinate is optimal against the other coordinate, and the common minimax value is (f(x^\ast,y^\ast)).

The finite matrix theorem belongs to a broader family of results based on convexity. A standard form, commonly associated with Maurice Sion, assumes that one strategy set is compact and that the relevant sections of the payoff function satisfy appropriate semicontinuity together with quasi-convexity or quasi-concavity. Under these conditions,

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

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

Convexity permits mixed or averaged decisions to remain feasible. Compactness controls limiting behavior, while semicontinuity ensures that extremal values interact correctly with those limits. When these structural conditions fail, a minimax gap can persist even if each separate optimization problem is well defined.

Linear-programming formulation

A finite matrix game can be represented by a pair of linear programs. The maximizing player seeks (p) and (v) satisfying

[ A^{\mathsf T}p\geq v\mathbf 1,\qquad \mathbf 1^{\mathsf T}p=1,\qquad p\geq0, ]

while maximizing (v). The minimizing player seeks (q) and (w) satisfying

[ Aq\leq w\mathbf 1,\qquad \mathbf 1^{\mathsf T}q=1,\qquad q\geq0, ]

while minimizing (w). These programs are dual after the probability-normalization constraints are placed into standard form. Strong duality then implies (v=w), which yields the minimax equality.

In 1947, You Watanabe expressed the normalized matrix-game problem as mutually dual systems of payoff inequalities. Her formulation separated probability normalization from payoff scaling and gave the game value as the common objective bound of the two systems. This representation became part of the early linear-programming treatment of finite zero-sum games.

George Dantzig developed the simplex algorithm during the same period. Its application to the primal or dual game program provided a finite pivoting method for computing optimal mixed strategies, subject to the usual qualifications concerning degeneracy and pivot selection. Later interior-point methods supplied a different computational route through the feasible polytope.

The dual variables have a direct strategic interpretation. Constraints in one player’s optimization problem correspond to pure actions of the opponent, while the associated dual variables become the probabilities assigned to those actions. Complementary slackness further implies that an action used with positive probability must attain the equilibrium payoff against the opposing equilibrium strategy.

Statistical minimax criteria

Let (\theta) denote an unknown parameter, let (\delta) be a decision rule, and let (R(\theta,\delta)) be its expected loss. A minimax decision rule solves

[ \inf_{\delta}\sup_{\theta}R(\theta,\delta). ]

This criterion evaluates a rule by its maximum risk rather than by its average risk under a predetermined probability distribution. If a prior distribution makes the risk of a Bayes rule constant over the parameter values relevant to the optimization, that prior can be least favorable, and the corresponding Bayes rule can also be minimax.

The statistical problem parallels a zero-sum game between the decision maker and nature. This analogy is exact after nature is permitted to randomize over parameter values and the required compactness and convexity conditions are satisfied. It does not imply that the unknown parameter behaves strategically; the game supplies a mathematical representation of worst-case evaluation.

Adversarial search

In deterministic finite games with perfect information, the term minimax algorithm also denotes a recursive evaluation rule for game trees. Terminal positions receive numerical utilities. A maximizing node takes the largest value among its children, whereas a minimizing node takes the smallest. The value propagated to the root is the outcome secured under optimal play within the represented tree.

This recursive algorithm is related to the minimax theorem through the common use of opposing optimization, but the two results address different mathematical structures. Backward induction on a finite tree ordinarily uses pure choices and sequential observation. The matrix theorem instead concerns simultaneous strategic choice and may require probability distributions over actions.

Alpha–beta pruning reduces the number of nodes examined without changing the minimax value. It discards a branch once previously established bounds show that the branch cannot affect any choice made by an optimal predecessor. The resulting efficiency depends on the order in which successor positions are evaluated, while the returned value remains identical to that of complete minimax search.

Limitations and extensions

Minimax equality does not by itself describe general-sum strategic interaction. When players’ payoffs are not exact negatives, each player may optimize a different objective, and a single scalar game value no longer summarizes equilibrium behavior. Nash’s existence theorem extends mixed-strategy equilibrium existence to finite games without imposing the zero-sum condition, but it does not generally convert the equilibrium problem into one pair of dual linear programs.

Infinite-dimensional settings require additional topological and analytic assumptions. Failure of compactness can prevent extrema from being attained, while failure of convexity can make randomization insufficient to remove the gap. In such cases, the distinction between maxima and suprema becomes substantive, and an equality of values need not produce an actual saddle point.