Minimax theorem

In the mathematical area of game theory, a minimax theorem is a theorem providing conditions that guarantee that the max–min inequality is also an equality. The first theorem in this sense is von Neumann's minimax theorem about zero-sum games published in 1928,^[1] which was considered the starting point of game theory. Von Neumann is quoted as saying "As far as I can see, there could be no theory of games ... without that theorem ... I thought there was nothing worth publishing until the Minimax Theorem was proved".^[2]

Since then, several generalizations and alternative versions of von Neumann's original theorem have appeared in the literature.^[3][4]

Formally, von Neumann's minimax theorem states:

Let ${\displaystyle X\subset \mathbb {R} ^{n}}$ and ${\displaystyle Y\subset \mathbb {R} ^{m}}$ be compact convex sets. If ${\displaystyle f:X\times Y\rightarrow \mathbb {R} }$ is a continuous function that is concave-convex, i.e.

${\displaystyle f(\cdot ,y):X\to \mathbb {R} }$ is concave for fixed ${\displaystyle y}$, and

${\displaystyle f(x,\cdot ):Y\to \mathbb {R} }$ is convex for fixed ${\displaystyle x}$.

Then we have that

${\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y).}$

Special case: Bilinear function

The theorem holds in particular if ${\displaystyle f(x,y)}$ is a linear function in both of its arguments (and therefore is bilinear) since a linear function is both concave and convex. Thus, if ${\displaystyle f(x,y)=x^{\mathsf {T}}Ay}$ for a finite matrix ${\displaystyle A\in \mathbb {R} ^{n\times m}}$, we have:

${\displaystyle \max _{x\in X}\min _{y\in Y}x^{\mathsf {T}}Ay=\min _{y\in Y}\max _{x\in X}x^{\mathsf {T}}Ay.}$

The bilinear special case is particularly important for zero-sum games, when the strategy set of each player consists of lotteries over actions (mixed strategies), and payoffs are induced by expected value. In the above formulation, ${\displaystyle A}$ is the payoff matrix.

See also

• Sion's minimax theorem
• Parthasarathy's theorem — a generalization of Von Neumann's minimax theorem
• Dual linear program can be used to prove the minimax theorem for zero-sum games.
• Yao's minimax principle

References