= Minimax theorem
{title2=$\max_x\min_y x^{\mathsf T}Ay=\min_y\max_x x^{\mathsf T}Ay$}
{wiki}
For every real $m\times n$ <payoff matrix> $A$ of a two-player <zero-sum game>, the <minimax theorem> states
$$
\max_{x\in\Delta_m}\min_{y\in\Delta_n}x^{\mathsf T}Ay
=\min_{y\in\Delta_n}\max_{x\in\Delta_m}x^{\mathsf T}Ay=v,
$$
where $\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^*,y^*$,
$$
x^{\mathsf T}Ay^*\leq v=(x^*)^{\mathsf T}Ay^*\leq(x^*)^{\mathsf T}Ay
\quad\text{for all }x\in\Delta_m,\ y\in\Delta_n.
$$
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{smallmatrix}1&-1\\-1&1\end{smallmatrix}\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 https://link.springer.com/article/10.1007/BF01448847[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 https://pmc.ncbi.nlm.nih.gov/articles/PMC1063129/[1950 paper]{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>.
Back to article page
