The minimax theorem is a foundational result in game theory and mathematical optimization establishing conditions under which a maximization and a minimization can be interchanged without changing their value. Its classical form, proved by John von Neumann in 1928, states that every finite two-player zero-sum game has a value when players may randomize their actions: the largest payoff one player can guarantee equals the smallest upper bound the opponent can enforce. More general minimax theorems extend this equality to suitable convex strategy spaces and payoff functions.
Finite-game formulation
Consider a two-player game represented by a real payoff matrix . The row player chooses a row and seeks to maximize the payoff; the column player chooses a column and seeks to minimize it. If row and column are selected, the row player receives , while the column player receives .
A mixed strategy is a probability distribution over a player's available actions. Write the two strategy sets as
and
When the players randomize independently, their expected payoff is
The row player's maximin value is
It is the greatest payoff the row player can guarantee, regardless of the column player's strategy.
The column player's minimax value is
It is the smallest upper bound on the row player's payoff that the column player can enforce.
The minimax theorem states that
Their common value is called the value of the game.
The theorem also guarantees optimal mixed strategies and satisfying
for every and . Thus, guarantees at least , while holds the payoff to at most .
Why the equality is significant
The general minimax inequality
For any real-valued function on nonempty sets,
This inequality requires no convexity or continuity assumptions. It follows because, for every and ,
The substantive assertion of a minimax theorem is the reverse inequality under additional hypotheses. Without such hypotheses, a strict gap may remain.
The nested optimization symbols describe guarantees against possible responses. They do not, by themselves, imply that a simultaneous-move game is played sequentially or that a player's realized random action is revealed before the opponent acts.
Why randomization matters
Consider the payoff matrix
If only pure actions are allowed, then
Each deterministic choice can be countered, so the pure-strategy maximin and minimax values differ.
If each player instead chooses either action with probability , the expected payoff is zero against every strategy of the opponent. Consequently,
Randomization replaces the finite action sets with their convex hulls in probability coordinates. The expected payoff is linear in each player's strategy separately, providing the structure needed for the theorem.
The guarantee concerns expected payoff, not the outcome of every individual play. Even under optimal strategies, a realized payoff can be above or below the game value.
Saddle points and equilibrium
The optimality inequalities characterize a saddle point of the expected-payoff function. Holding fixed, maximizes payoff; holding fixed, minimizes it.
Such a pair is also a Nash equilibrium: neither player can improve their own expected payoff by changing strategy unilaterally. In a two-player zero-sum game, every Nash equilibrium has the same payoff value.
Optimal strategies need not be unique. Nevertheless, any optimal row strategy can be paired with any optimal column strategy to form an equilibrium. This interchangeability is a special feature of the zero-sum setting and does not generally hold in games with arbitrary payoffs.
A pure-strategy saddle point exists precisely when there is an entry such that
for all . Such an entry is a maximum in its column and a minimum in its row. The minimax theorem does not guarantee such an entry; it guarantees a saddle point after mixed strategies are admitted.
Linear-programming formulation
Finite minimax problems can be solved through linear programming. Because a linear function on a probability simplex attains its extrema at pure actions,
The row player's problem is therefore
Here is an unrestricted real variable. Each payoff constraint ensures that the strategy guarantees at least against one of the opponent's pure actions.
The corresponding dual problem is
Both problems are feasible and have finite optimal objective values. Strong linear-programming duality therefore yields
which proves the finite minimax equality. This makes the theorem a central example of optimization duality: the two players' optimization problems provide matching lower and upper bounds.
The corresponding complementary-slackness conditions also describe optimal play. If , then
if , then
Thus every pure action used with positive probability is a best response to the opponent's optimal strategy. An unused action can also be a best response, so the converse implications need not hold.
Continuous and convex generalizations
A standard generalization replaces finite probability simplexes by nonempty compact convex sets and in finite-dimensional real vector spaces. Suppose is a continuous function such that:
- is concave on for every ;
- is a convex function on for every .
Then
and a saddle point exists.
These assumptions match the optimization directions: the maximizing variable enters concavely, and the minimizing variable enters convexly. A bilinear payoff is both convex and concave in either variable separately, so finite matrix games are a special case.
Sion's minimax theorem
Sion's minimax theorem, published in 1958, weakens the requirements further. One standard formulation takes:
- a nonempty compact convex set in a real topological vector space;
- a nonempty convex set in a real topological vector space;
- a real-valued function .
Suppose that for every , is lower semicontinuous and quasiconvex on , and for every , is upper semicontinuous and quasiconcave on . Then
Quasiconvexity means that every sublevel set is convex; quasiconcavity means that every superlevel set is convex. These conditions are weaker than convexity and concavity, respectively. Semicontinuity supplies one-sided regularity rather than full continuity.
Unlike the finite-game formulation, is the minimizing variable in this statement. Only one strategy set is assumed compact, and the equality alone does not guarantee that both outer extrema are attained.
Applications
Statistical decision theory
In statistical decision theory, let denote a decision rule, an unknown parameter, and
the risk associated with a loss function . A minimax rule minimizes worst-case risk:
Under suitable assumptions, allowing probability distributions over parameters and randomized decision rules gives a minimax identity relating this problem to Bayes risk:
A maximizing distribution , when it exists, is called a least favorable prior. This equality requires appropriate regularity conditions; it is not automatic for every statistical model or rule class.
Robust optimization and learning
In convex optimization, minimax identities support problems in which a decision is evaluated against an adverse choice of uncertain parameters. They can establish that a robust decision problem and its adversarial dual have the same value.
In machine learning, related formulations arise in adversarial training, distributional robustness, and online learning. However, objectives involving nonlinear models are often nonconvex in the minimizing variable or nonconcave in the maximizing variable. In such cases, the classical theorem may not apply, and an optimization algorithm need not find a global saddle point.
Limitations and distinctions
Infinite action sets require additional assumptions. Finite games automatically provide compact probability simplexes and continuous bilinear payoffs. Infinite games may lack compactness, continuity, optimal strategies, or even equality of the two values.
Equality is not the same as attainment. An infimum or supremum may exist without any strategy achieving it. A theorem asserting equality of values must be distinguished from one asserting the existence of optimal strategies.
The zero-sum hypothesis is essential to the game interpretation. General-sum games have separate payoff functions rather than a single quantity that one player maximizes and the other minimizes. Their equilibria are not generally characterized by one minimax equality.
A minimax algorithm is not a minimax theorem. The tree-search procedure called minimax evaluates positions by alternating maximizing and minimizing choices. Its recursive definition is distinct from the theorem establishing equality of optimization values.
Other results share the name. In functional analysis, “min–max theorem” can refer to variational characterizations of eigenvalues, such as the Courant–Fischer theorem. Those results concern subspaces and quadratic forms rather than the classical interchange of opposing players' optimization problems.
Historical development
Von Neumann's 1928 proof established the finite two-player zero-sum theorem as a foundation for mathematical game theory. The framework received a systematic treatment in Theory of Games and Economic Behavior, published by von Neumann and Oskar Morgenstern in 1944.
Subsequent work connected finite minimax equality with linear-programming duality and extended it to broader settings in convex analysis and topology. Generalizations by Ky Fan and Maurice Sion replaced finite strategy spaces with more general convex spaces and weakened the assumptions on payoff functions.