Von Neumann’s Minimax Theorem for Matrix Games

Why Mixed Strategies Matter

In a finite zero-sum game, one player chooses a row and seeks to make the payoff large; the other chooses a column and seeks to make it small. If each player is restricted to a single pure strategy, the best guaranteed payoff for the row player need not equal the smallest payoff the column player can force. Allowing each player to randomize changes the strategy sets, and in a finite game it removes this gap.

The result is the finite form of von Neumann’s minimax theorem. It says that a mixed strategy exists for each player such that the row player can guarantee a value $v$, while the column player can hold the payoff to at most $v$. The proof below uses a fixed-point argument to establish those guarantees.

Strategies and Values

Definition: Let $A=(a_{ij})$ be a real $m\times n$ payoff matrix. The row player receives $a_{ij}$ when row $i$ and column $j$ are chosen; the column player receives its negative. A mixed strategy for the row player is a vector $p\in\Delta_m$, and a mixed strategy for the column player is a vector $q\in\Delta_n$, where $$ \Delta_m=\left\{p\in\mathbb{R}^m:p_i\geq 0,\ \sum_{i=1}^m p_i=1\right\},\qquad \Delta_n=\left\{q\in\mathbb{R}^n:q_j\geq 0,\ \sum_{j=1}^n q_j=1\right\}. $$ When the players use $p$ and $q$, the expected payoff to the row player is $p^\mathsf{T}Aq$.

The row player’s maximin value and the column player’s minimax value are, respectively, $$ \underline v=\max_{p\in\Delta_m}\min_{q\in\Delta_n}p^\mathsf{T}Aq,\qquad \overline v=\min_{q\in\Delta_n}\max_{p\in\Delta_m}p^\mathsf{T}Aq. $$ The first is the largest payoff the row player can guarantee, whatever the column player chooses. The second is the smallest upper bound the column player can guarantee, whatever the row player chooses. These maxima and minima are attained: for a fixed $p$, the minimum over $q$ is the minimum of the finitely many expected payoffs against pure columns, and for a fixed $q$, the maximum over $p$ is the maximum of the finitely many expected payoffs for pure rows. The resulting functions are continuous on compact simplices.

Result (weak minimax inequality): For every finite real matrix $A$, $\underline v\leq\overline v$.

Proof. For every $p\in\Delta_m$ and $q\in\Delta_n$, $$ \min_{q'\in\Delta_n}p^\mathsf{T}Aq'\leq p^\mathsf{T}Aq \leq\max_{p'\in\Delta_m}{p'}^\mathsf{T}Aq. $$ For a fixed $q$, taking the maximum over $p$ in the leftmost expression gives $$ \max_{p\in\Delta_m}\min_{q'\in\Delta_n}p^\mathsf{T}Aq' \leq \max_{p\in\Delta_m}{p}^\mathsf{T}Aq. $$ This holds for every $q$, so taking the minimum over $q$ on the right proves $\underline v\leq\overline v$. $\square$

Worked Examples: Finding the Common Value

Worked Example: Matching Pennies

Consider $$ A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}. $$ The row player chooses between the two rows, and the column player chooses between the two columns. Let $p$ be the probability of row 1 and $q$ the probability of column 1.

Against $q$, the expected payoffs for pure row 1 and pure row 2 are $2q-1$ and $1-2q$. Thus the row player’s payoff using $p$ is $$ p(2q-1)+(1-p)(1-2q)=(2p-1)(2q-1). $$ If $p=1/2$, this payoff is zero for every $q$, so the row player guarantees zero. If $q=1/2$, it is zero for every $p$, so the column player holds the payoff to zero. The common value is $0$. By contrast, each pure row has minimum payoff $-1$, and each pure column has maximum payoff $1$; the pure-strategy values differ.

Worked Example: An Asymmetric Two-by-Two Game

Let $$ A=\begin{pmatrix}3&0\\1&2\end{pmatrix}. $$ Write $p$ for the probability of row 1. Against pure column 1 the expected payoff is $3p+1(1-p)=1+2p$; against pure column 2 it is $0p+2(1-p)=2-2p$. Therefore the row player’s guaranteed payoff is $$ \min(1+2p,\,2-2p). $$ The first expression increases with $p$ and the second decreases. Their intersection satisfies $1+2p=2-2p$, so $p=1/4$, and both payoffs there equal $3/2$. The minimum is no larger away from the intersection, so this mixture maximizes the guaranteed payoff.

Now let $q$ be the probability of column 1. The expected payoffs for the two pure rows are $3q$ and $q+2(1-q)=2-q$. The column player minimizes $\max(3q,2-q)$. The increasing and decreasing expressions meet when $3q=2-q$, giving $q=1/2$ and a maximum payoff of $3/2$. Since one expression is at least $3/2$ on either side of this intersection, this choice minimizes the maximum. Both players’ guarantees agree at $3/2$.

Worked Example: A Second Guarantee Calculation

Consider $$ A=\begin{pmatrix}0&4\\3&1\end{pmatrix}. $$ If the row player assigns probability $p$ to row 1, the expected payoffs against columns 1 and 2 are $3(1-p)=3-3p$ and $4p+1(1-p)=1+3p$. The guaranteed payoff is their minimum. They are equal when $3-3p=1+3p$, so $p=1/3$; both equal $2$. Because one expression decreases and the other increases, their minimum cannot be larger away from this intersection. Thus this mixture guarantees $2$.

If the column player assigns probability $q$ to column 1, the payoffs for rows 1 and 2 are $4(1-q)$ and $3q+1(1-q)=1+2q$. To minimize their maximum, set them equal: $4-4q=1+2q$, giving $q=1/2$. Each payoff is then $2$. On either side of the intersection, the larger of the two expressions exceeds $2$, so this mixture holds the row player to at most $2$. The common value is $2$.

Von Neumann’s Minimax Theorem

Theorem: For every finite real payoff matrix $A$, there exist mixed strategies $p^*\in\Delta_m$ and $q^*\in\Delta_n$, and a real number $v$, such that $$ \min_{q\in\Delta_n}{p^*}^\mathsf{T}Aq=v =\max_{p\in\Delta_m}p^\mathsf{T}Aq^*. $$ Consequently, $\underline v=\overline v=v$.

Proof. We use Brouwer’s fixed-point theorem in its standard finite-dimensional form: every continuous map from a nonempty compact convex subset of a Euclidean space into itself has a fixed point. The product $\Delta_m\times\Delta_n$ is such a set.

For $p\in\Delta_m$ and $q\in\Delta_n$, define the payoff $w=p^\mathsf{T}Aq$. Let $u_i(q)$ be the payoff from pure row $i$ against $q$, and $c_j(p)$ the payoff from $p$ against pure column $j$: $$ u_i(q)=\sum_{j=1}^n a_{ij}q_j,\qquad c_j(p)=\sum_{i=1}^m p_i a_{ij}. $$ Define the nonnegative improvements $$ r_i(p,q)=\max\{u_i(q)-w,0\},\qquad s_j(p,q)=\max\{w-c_j(p),0\}, $$ and their sums $R=\sum_i r_i$ and $S=\sum_j s_j$. Consider the map $$ T(p,q)=\left( \left(\frac{p_i+r_i}{1+R}\right)_{i=1}^m,\ \left(\frac{q_j+s_j}{1+S}\right)_{j=1}^n \right). $$ Every coordinate is nonnegative, and the row coordinates sum to $(1+R)/(1+R)=1$; the column coordinates likewise sum to one. The map takes $\Delta_m\times\Delta_n$ into itself. It is continuous because its numerators and denominators are continuous functions of $p,q$, and its denominators are at least one. Brouwer’s theorem therefore supplies a fixed point $(p^*,q^*)$.

Evaluate all quantities in the next argument at this fixed point. The fixed-point equations for the row coordinates give $r_i=Rp_i$. If $R>0$, then every $i$ with $p_i>0$ has $r_i>0$, which implies $u_i(q^*)-w>0$. But $$ \sum_{i=1}^m p_i\bigl(u_i(q^*)-w\bigr) ={p^*}^\mathsf{T}Aq^*-w\sum_{i=1}^m p_i=0. $$ All terms with $p_i=0$ vanish, while every term with $p_i>0$ would be strictly positive. This contradicts the displayed equality. Hence $R=0$, so $u_i(q^*)\leq w$ for every row $i$.

Similarly, the column fixed-point equations give $s_j=S q_j$. If $S>0$, then every $j$ with $q_j>0$ has $s_j>0$, which implies $w-c_j(p^*)>0$. Yet $$ \sum_{j=1}^n q_j\bigl(w-c_j(p^*)\bigr) =w-{p^*}^\mathsf{T}Aq^*=0. $$ The terms with $q_j=0$ vanish and those with $q_j>0$ would all be strictly positive, a contradiction. Thus $S=0$, and $c_j(p^*)\geq w$ for every column $j$.

For any mixed row strategy $p$, its payoff against $q^*$ is a weighted average of the $u_i(q^*)$, each at most $w$. Therefore $p^\mathsf{T}Aq^*\leq w$. For any mixed column strategy $q$, the payoff under $p^*$ is a weighted average of the $c_j(p^*)$, each at least $w$. Therefore ${p^*}^\mathsf{T}Aq\geq w$. It follows that $$ \underline v\geq w,\qquad \overline v\leq w. $$ The weak minimax inequality gives $\underline v\leq\overline v$. Consequently both values equal $w$, and the stated guarantees hold with $v=w$. $\square$

Interpreting the Result and Avoiding a Pitfall

The theorem is an existence result for finite games with a real payoff in every matrix entry. It does not say that every pair of strategies produces the value, or that a pure strategy attains it. Instead, it guarantees a pair of mixed strategies: one protects the row player against every column mixture, while the other protects the column player against every row mixture. The fixed-point proof works by adjusting probabilities toward pure strategies that would improve the current payoff, then showing that at a fixed point neither player has a profitable pure-strategy improvement.

Pitfall: confusing the theorem with equality for pure strategies. One might calculate the best worst-case payoff among pure rows and the smallest worst-case payoff among pure columns, then conclude that a gap disproves minimax equality. That only compares pure-strategy values. Matching pennies has pure values $-1$ and $1$, but its mixed-strategy values both equal $0$.
Pitfall: treating a particular expected payoff as a guarantee. A payoff $p^\mathsf{T}Aq$ for one chosen pair says nothing by itself about what happens against every opposing strategy. A guarantee requires checking all opposing strategies, as the theorem’s inequalities do.

Key takeaway: In every finite zero-sum matrix game, mixed strategies make the row player’s largest guaranteed payoff equal the column player’s smallest guaranteed upper bound. The common value is attained by strategies that secure opposite-sided guarantees.

Check Your Understanding

Use the definitions and proof to check each point.

For a fixed $p$, why is the minimum payoff over mixed $q$ attained against at least one pure column?
State the weak minimax inequality and identify the quantifier step that proves it.
In the fixed-point proof, why does $R>0$ contradict the weighted sum of the row payoff differences being zero?
For matching pennies, what payoff does each player guarantee by using equal probabilities?
Why does the theorem not imply that a pure-strategy minimax gap is impossible?