矩阵博弈极小极大定理

形式陈述

设 $A\in\mathbb R^{m\times n}$ 是实矩阵， $m,n\ge1$ 。行玩家选行、列玩家选列，行收益为 $A_{ij}$ ，列收益为 $-A_{ij}$ 。以 $\Delta_m=\{x\in\mathbb R^m:x\ge0,\ \mathbf1^{\mathsf T}x=1\}$ 表示行玩家的混合策略集，列玩家的策略集为 $\Delta_n$ 。双方独立抽样时，行玩家期望收益是

\sum_{i,j}x_iA_{ij}y_j=x^{\mathsf T}Ay.

行玩家希望这个数大，列玩家希望这个数小。有限矩阵博弈极小极大定理断言

\boxed{\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^*.}

两侧最优策略都能取得，公共数 $v^*$ 称博弈的价值。左边给行玩家一份能抵抗所有列策略的收益下界，右边给列玩家一份能压住所有行策略的收益上界。由于列收益为其相反数，双方的均衡收益是 $(v^*,-v^*)$ ；零和并不要求 $v^*=0$ 。

写成一对线性规划

固定 $x$ 后， $x^{\mathsf T}Ay$ 是各列收益 $(A^{\mathsf T}x)_j$ 的加权平均，其最小值就是最小的列收益。因此行玩家保证至少 $v$ ，等价于每列收益都至少为 $v$ 。固定 $y$ 的情形同理，得到

\begin{aligned} \text{(P)}\quad\max_{x,v}\quad &v\\ \text{s.t.}\quad&A^{\mathsf T}x\ge v\mathbf1,\\ &\mathbf1^{\mathsf T}x=1,\quad x\ge0,\quad v\in\mathbb R; \end{aligned}

\begin{aligned} \text{(D)}\quad\min_{y,w}\quad &w\\ \text{s.t.}\quad&Ay\le w\mathbf1,\\ &\mathbf1^{\mathsf T}y=1,\quad y\ge0,\quad w\in\mathbb R. \end{aligned}

这是线性规划对偶的一对原始与对偶问题。可以直接从上界构造核对配对：给 $A^{\mathsf T}x-v\mathbf1\ge0$ 配非负向量 $y$ ，给 $1-\mathbf1^{\mathsf T}x=0$ 配自由数 $w$ ，则对原始可行点

v\le v+y^{\mathsf T}(A^{\mathsf T}x-v\mathbf1)+w(1-\mathbf1^{\mathsf T}x) =w+x^{\mathsf T}(Ay-w\mathbf1)+v(1-\mathbf1^{\mathsf T}y).

要让右边对任意 $x\ge0$ 、自由变量 $v$ 都有有限上界，必须有 $Ay\le w\mathbf1$ 和 $\mathbf1^{\mathsf T}y=1$ ；此时上界就是 $w$ 。因此自由的 $v$ 产生概率归一化等式，原来的概率等式产生自由的 $w$ 。收益可能为负，不能另加 $v,w\ge0$ 。

弱对偶、强对偶与取得

任何两侧可行解都满足

v\le x^{\mathsf T}Ay\le w.

第一个不等式是用概率 $y$ 平均行方的各列保证，第二个是用概率 $x$ 平均列方的各行上界。这证明最大下界不超过最小上界，也给出了无需运行求解器的证书检查方式。

令 $a_{\min},a_{\max}$ 分别为 $A$ 的最小、最大条目。任意概率 $x$ 配 $v=a_{\min}$ 都原始可行，任意概率 $y$ 配 $w=a_{\max}$ 都对偶可行；所有可实现的期望收益又落在 $[a_{\min},a_{\max}]$ 内。因此两侧可行且最优值有限。有限维 LP 强对偶保证两侧取得最优解且目标相等，便证明了上面的 minimax 等式。

直觉

行玩家选定 $x$ 后，每一列都给出一条可能的收益，最危险的是其中最低的一条。行玩家提升的是这些收益的下包络。列玩家选定 $y$ 后，行玩家会挑收益最高的一行，因此列玩家降低的是各行收益的上包络。定理说，允许概率混合后，这两个优化过程会在同一高度相遇。

行收益矩阵为两行 2、-1 与 -2、3 时，下包络在 p=5/8 达到最大值 1/2，上包络在 q=1/2 达到最小值 1/2 — 两侧最优包络给出相同价值

图中粗线分别表示 $\min\{4p-2,3-4p\}$ 和 $\max\{3q-1,3-5q\}$ ，黑点给出最优概率。两点横坐标可以不同，因为它们属于不同玩家；相同的是纵坐标所表示的行收益。

例子与边界

从纯策略间隙算到混合价值

取

A=\begin{pmatrix}2&-1\\-2&3\end{pmatrix}.

若行玩家只能选一行，第一行最坏收益为 $-1$ ，第二行为 $-2$ ，所以纯策略最大保证是 $-1$ 。若列玩家只能选一列，第一列允许行方取得的最大收益为 $2$ ，第二列为 $3$ ，所以纯策略最小上界为 $2$ 。两者不同，说明没有纯鞍点；这并不违反允许混合的定理。

设 $x=(p,1-p)$ 。面对第一列，行方收益为 $2p-2(1-p)=4p-2$ ；面对第二列，为 $-p+3(1-p)=3-4p$ 。当 $p\le5/8$ ，第一条较低且递增；当 $p\ge5/8$ ，第二条较低且递减。下包络的最大值因而在交点取得：

4p-2=3-4p\quad\Longrightarrow\quad p=5/8,\qquad v=1/2.

设 $y=(q,1-q)$ 。第一行收益为 $2q-(1-q)=3q-1$ ，第二行为 $-2q+3(1-q)=3-5q$ 。当 $q\le1/2$ ，第二条较高且递减；当 $q\ge1/2$ ，第一条较高且递增。因此上包络最小点为 $q=1/2$ ，其值也是 $1/2$ 。

逐项核验证书

候选最优策略是 $x^*=(5/8,3/8)$ 、 $y^*=(1/2,1/2)$ 。两向量都非负且坐标和为 $1$ ，并且

A^{\mathsf T}x^*=\begin{pmatrix}2(5/8)-2(3/8)\\-(5/8)+3(3/8)\end{pmatrix}=\begin{pmatrix}1/2\\1/2\end{pmatrix},\qquad Ay^*=\begin{pmatrix}2(1/2)-(1/2)\\-2(1/2)+3(1/2)\end{pmatrix}=\begin{pmatrix}1/2\\1/2\end{pmatrix}.

前一式证明无论列方怎么混合， $x^*$ 都保证收益至少 $1/2$ ；后一式证明无论行方怎么混合， $y^*$ 都将收益压到至多 $1/2$ 。两侧相等形成精确最优证书。本例两向量全支持，所以各纯回应收益全部相等；一般最优策略的支持集外动作只需满足对应弱不等式。

鞍点与 Nash 均衡

一对策略 $(x^*,y^*)$ 是零和博弈的Nash 均衡，当且仅当对所有 $x,y$ 有

x^{\mathsf T}Ay^*\le (x^*)^{\mathsf T}Ay^*\le(x^*)^{\mathsf T}Ay.

左边表示行方无法提高收益，右边表示列方无法降低行收益。任取最优行策略和最优列策略，两侧保证把中间收益夹在 $v^*$ ，所以配对后满足鞍点条件。反过来，鞍点收益一方面是行方对当前列策略的最大值，另一方面是列方对当前行策略的最小值，夹住 minimax 两侧，故必等于 $v^*$ ，双方都是最优策略。

共同价值不保证策略唯一。例如全零矩阵的任意概率对都是均衡。有限性也不可随意删除：无限策略空间可能不取得最优值，交换极值需要额外条件。

推论与应用

Yao 极小极大原理把确定性算法与输入作为两侧纯策略，以损失形成矩阵。算法方最小化损失、输入方最大化损失，因此若沿用本页行方最大化的约定，应让输入做行、算法做列，或统一对损失取负。资源预算与合法输入域固定后，困难输入分布和随机算法保证才由同一个有限定理连接起来。

乘法权重更新方法提供逼近矩阵博弈值的算法方向。对任意候选 $x,y$ ，都可计算下界 $\ell=\min_j(A^{\mathsf T}x)_j$ 与上界 $h=\max_i(Ay)_i$ ；必有 $\ell\le v^*\le h$ 。若 $h-\ell\le\varepsilon$ ，则双方在当前配对中的单方改进都至多为 $\varepsilon$ ，因为当前收益也位于 $[\ell,h]$ 。这个可计算间隙可以检查近似输出；具体更新过程如何缩小间隙，则需要相应的遗憾界分析。

参考资料

Tim Roughgarden，CS261 Lecture 10，2016-02-04，§1.2–1.4，Theorem 1.1，pp. 2–5；矩阵 minimax、对偶 LP 与自由变量。
Omar Antolín Camarena，Matrix Games，Math 340 作者课程原稿，价值、minimax 和线性规划部分。

形式陈述 ​

写成一对线性规划 ​

弱对偶、强对偶与取得 ​

从纯策略间隙算到混合价值 ​

逐项核验证书 ​

鞍点与 Nash 均衡 ​