有限二人零和博弈
设 $A\in\mathbb{R}^{n\times m}$，$X=\{1,2,\cdots,n\}$，$Y=\{1,2,\cdots,m\}$（即 $X$，$Y$ 均为有限集），$X$ 表示玩家 I 的（纯）策略集合，$Y$ 表示玩家 II 的（纯）策略集合。若玩家 I 选择纯策略 $i\in X$，玩家 II 选择纯策略 $j\in Y$，那么玩家 I 将获得 $A_{ij}$ 的收益，玩家 II 将获得 $-A_{ij}$ 的收益（零和）。注意在该游戏的原始定义中，两人应当同时提出策略，即不知道对方的策略。此外，不妨将玩家 II 的收益也称为 $A$，但是他的目标是最小化之。
此外，考虑混和策略 $X^{*}$ 和 $Y^{*}$：
$$ X^{*}=\{\boldsymbol{p}=(p_{1},p_{2},\cdots,p_{n})^{T}:p_{i}\ge0\land\sum_{i=1}^{n}p_{i}=1\}\\ Y^{*}=\{\boldsymbol{q}=(q_{1},q_{2},\cdots,q_{m})^{T}:q_{i}\ge0\land\sum_{i=1}^{m}q_{i}=1\} $$
含义为玩家 I 以 $p_{i}$ 的概率选择纯策略 $i$。下文中，不加说明的策略均指混合策略。
现在改变一下游戏规则，不妨假设玩家 II 需要先声明自己的策略，玩家 I 随后选择自己的策略。那么玩家 I 选择策略 $\boldsymbol{p}$ 的收益是 $\boldsymbol{p}^{T}A\boldsymbol{q}$。显然玩家 I 将选择对于特定的 $\boldsymbol{q}$ 收益最大的 $\boldsymbol{p}$，玩家 II 则在玩家 I 选择的基础上选择收益最小的 $\boldsymbol{q}$。那么玩家 I 的收益将是
$$ \overline{V}=\min_{\boldsymbol{q}\in Y^{*}}\max_{\boldsymbol{p}\in X^{*}}\boldsymbol{p}^{T}A\boldsymbol{q} $$
可以发现，这意味着玩家 II 可以在原游戏中保证自己的收益不超过 $\overline{V}$，他只要选择同样的操作即可。
将两人的操作顺序反过来，同理有
$$ \underline{V}=\max_{\boldsymbol{p}\in X^{*}}\min_{\boldsymbol{q}\in Y^{*}}\boldsymbol{p}^{T}A\boldsymbol{q} $$
这意味着玩家 I 可以在原游戏中保证自己的收益不低于 $\underline{V}$，他只要选择同样的操作即可。
首先证明 $\underline{V}\le\overline{V}$，这对于任意集合 $X^{*}$ 和 $Y^{*}$ 和定义在 $X^{*}\times Y^{*}$ 上的实值函数 $f$ 都成立，即证明
$$ \max_{x\in X^{*}}\min_{y\in Y^{*}}f(x,y)\le\min_{y\in Y^{*}}\max_{x\in X^{*}}f(x,y)$$
注意到
$$ \min_{y'\in Y^{*}}f(x,y')\le f(x,y)\le \max_{x'\in X^{*}}f(x',y) $$
对任意 $x,y$ 都成立。因此对左侧加上 $\max_{x\in X^{*}}$，右侧加上 $\min_{y\in Y^{*}}$ 不影响不等式。
事实上，可以证明在这一问题中，$\underline{V}=\overline{V}$。注意到在上述两种简化问题中，后手必然有最优的纯策略。事实上最优的策略是所有最优的纯策略的线性组合。考虑线性规划问题
$$ \text{maximize}\;\;\;\;\;\;\min_{j\in Y}\sum_{i=1}^{n}p_{i}a_{ij} $$
s.t.
$$ \sum_{i=1}^{n}p_{i}=1\\ p_{i}\ge0 $$
但是这不是个线性规划，因为优化目标中有个 $\min$。添加一个辅助变量 $v$：
$$ \text{maximize}\;\;\;\;\;\;v $$
s.t.
$$ v\le\sum_{i=1}^{n}p_{i}a_{ij}\text{ for all } j\\ \sum_{i=1}^{n}p_{i}=1\\ p_{i}\ge0 $$
它的解即为 $\underline{V}$。
考虑另一个线性规划：
$$ \text{minimize}\;\;\;\;\;\;v $$
s.t.
$$ v\le\sum_{j=1}^{m}a_{ij}q_{j}\text{ for all } i\\ \sum_{j=1}^{m}q_{j}=1\\ q_{j}\ge0 $$
它的解即为 $\overline{V}$。
注意到这两个线性规划互为对偶，因而有 $\underline{V}=\overline{V}$。记该值为 $V$，称为该游戏的值。这一定理称为最小最大值定理。
这样一来，玩家 I 可以保证自己至少获得 $V$ 的收益，玩家 II 可以保证对方至多获得 $V$ 的收益。那么显然两人都会按照这样的策略行动。这也预示着该问题可用线性规划求解。
