Minimax theorem

For every real $m\times n$ payoff matrix $A$ of a two-player zero-sum game, the minimax theorem stateswhere ${\Delta }_m,{\Delta }_n$ are the players' probability simplices. Both outer optima are attained. The row player's security level payoff is the largest payoff it can guarantee against all opposing choices; the column player can hold that payoff to the same number $v$, the value of a zero-sum game. For optimal $x^{\ast },y^{\ast }$,These are exactly the Nash equilibrium inequalities under the row-maximizes, column-minimizes convention. Conversely, a Nash equilibrium of this two-player zero-sum game supplies both guarantees. This equality explains why independent worst-case optimization solves the opposing incentives in this special class.

Allowing mixed strategies is essential. For matching pennies, $A=\left(\begin{array}{cc}1& -1\\ -1& 1\end{array}\right)$. Restricting both players to pure strategies gives ${\max }_i{\min }_j{A}_{ij}=-1$ and ${\min }_j{\max }_i{A}_{ij}=1$. Allowing mixed strategies closes the gap: each fair mixture guarantees zero, so $v=0$. These guarantees hold even if the opponent knows the mixture's probabilities, provided the opponent does not observe the sampled choice before choosing.

John von Neumann proved the two-player zero-sum game result in Zur Theorie der Gesellschaftsspiele, Mathematische Annalen 100, 295–320 (1928); the original article's footnote 7 explicitly discusses the equality of max–min and min–max. Nash's ^[ref] states that existence of a Nash equilibrium is equivalent to this result in the two-player zero-sum game case, and extends existence to all finite games.