= 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^TAy$.
Against a fixed row mixture, the worst column is a pure column, so the row problem introduces its guaranteed payoff $v$:
$$
\boxed{\max_{x,v}v:\quad x\geq0,\quad\mathbf1^Tx=1,\quad A^Tx\geq v\mathbf1.}
$$
Similarly the column player minimizes an upper guarantee $w$:
$$
\boxed{\min_{y,w}w:\quad y\geq0,\quad\mathbf1^Ty=1,\quad Ay\leq w\mathbf1.}
$$
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 is
$$
\mathcal L=v+y^T(A^Tx-v\mathbf1)+w(1-\mathbf1^Tx)
=w+v(1-\mathbf1^Ty)+x^T(Ay-w\mathbf1).
$$
The supremum over free $v$ and nonnegative $x$ is finite precisely when $\mathbf1^Ty=1$ and $Ay\leq w\mathbf1$, 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_*$ satisfying
$$
\boxed{Ay\leq v_*\mathbf1,\qquad A^Tx\geq v_*\mathbf1.}
$$
Equivalently, both programs are feasible with equal values. Positive-probability rows then have $(Ay)_i=v_*$ and positive-probability columns have $(A^Tx)_j=v_*$, the <complementary slackness> conditions. These conditions certify a <saddle point> and hence optimal mixed strategies for both players.
Back to article page
