 Solution

In a finite two-person zero-sum game the row player chooses $i$, the column player chooses $j$, and the row player receives $a_{ij}$ while the column player receives $-a_{ij}$. The row player maximizes that payoff and the column player minimizes it. Mixed strategies are probability vectors $x\in {\mathbb{R}}^m$ and $y\in {\mathbb{R}}^n$, giving expected row payoff $x^{T}Ay$.

Against a fixed row mixture, the worst column is a pure column, so the row problem introduces its guaranteed payoff $v$:Similarly the column player minimizes an upper guarantee $w$:The values $v,w$ are unrestricted real variables; no positivity shift of the matrix is required.

To see the linear programming duality explicitly, introduce nonnegative multipliers $y$ for the first problem's payoff inequalities and multiplier $w$ for its normalization. Its upper-bound Lagrangian isThe supremum over free $v$ and nonnegative $x$ is finite precisely when $1^{T}y=1$ and $Ay\le w1$, and is then $w$. Minimizing it gives the displayed column problem, proving that the programs are a dual pair.

A sufficient optimality certificate is a pair of probability vectors and a common value $v_{\ast }$ satisfyingEquivalently, both programs are feasible with equal values. Positive-probability rows then have $(Ay{)}_i=v_{\ast }$ and positive-probability columns have $(A^{T}x{)}_j=v_{\ast }$, the complementary slackness conditions. These conditions certify a saddle point and hence optimal mixed strategies for both players.