博弈论

如果不进行随机化，「后」行动的一方（在得知对手策略之后再选择）会有优势，因此 maximin（行方先承诺）通常不超过 minimax（列方先承诺）。该定理令人惊讶之处在于，采用混合策略后这一差距会完全消失：随机化消除了后行动的任何优势，因为对手不再能够预测——并利用——一个固定的选择。

弱对偶性。 对任意固定的 $x_0 \in \Delta_m$ 和 $y_0 \in \Delta_n$：$\min_y x_0^\top A y \le x_0^\top A y_0 \le \max_x x^\top A y_0$。对左边取 $\max_{x_0}$、对右边取 $\min_{y_0}$ 仍保持不等式：$\max_x \min_y x^\top A y \le \min_y \max_x x^\top A y$。这个方向完全不需要随机化的论证。

归约为线性规划。 由于 $y \mapsto x^\top A y$ 是线性的，其在单纯形 $\Delta_n$ 上的最小值在某个顶点取得，即在某个纯策略 $j$ 处取得：$\min_y x^\top A y = \min_{j} \sum_{i=1}^m x_i A_{ij}$。因此行参与人的问题 $\max_x \min_y x^\top A y$ 就是如下线性规划：最大化 $v$，约束为 $\sum_{i=1}^m A_{ij} x_i \ge v$（对所有 $j = 1, \dots, n$），且 $x \in \Delta_m$。

对偶规划。 由线性规划的标准对偶理论，该线性规划的对偶为：最小化 $w$，约束为 $\sum_{j=1}^n A_{ij} y_j \le w$（对所有 $i = 1, \dots, m$），且 $y \in \Delta_n$ —— 这恰好是列参与人问题 $\min_y \max_x x^\top A y$ 的线性规划表述。

强对偶性。 原始与对偶的可行域（$\Delta_m$ 和 $\Delta_n$）都非空且紧致，因此该线性规划可行且有界；线性规划的强对偶定理由此保证原始与对偶最优值相等：$\max_x \min_y x^\top A y = \min_y \max_x x^\top A y$。结合此前弱对偶性已给出该方向的 $\le$，等式成立，定理得证。

证明在所有策略组合构成的空间上构造了一个连续的「稍微改进策略」映射：将概率向当前表现优于平均水平的纯策略倾斜。由于策略组合空间是紧致且凸的，布劳威尔不动点定理保证该映射存在一个不动点——一个映射不想再改变的组合。证明剩余的部分说明不动点恰好就是没有有利偏离的组合，即纳什均衡。

设 $\Delta = \Delta_1 \times \cdots \times \Delta_n$，即各参与人混合策略单纯形的乘积——这是欧几里得空间中一个紧致凸子集。对 $x \in \Delta$、参与人 $i$ 以及纯策略 $j \in S_i$，定义增益函数 $g_{ij}(x) = \max\big(0,\, u_i(s_{ij}, x_{-i}) - u_i(x)\big)$，即参与人 $i$ 完全改用纯策略 $j$ 所能获得的收益（若该转换无益则为 $0$）。定义 $f : \Delta \to \Delta$ 为 $f_i(x)_j = \dfrac{x_{ij} + g_{ij}(x)}{1 + \sum_{k \in S_i} g_{ik}(x)}$；由于 $u_i$ 关于 $x$ 连续（实际上是多重线性的），$g_{ij}$ 连续，故 $f$ 连续，且由构造可知每个 $f_i(x)$ 仍是概率向量。

由布劳威尔不动点定理，紧致凸集 $\Delta$ 上的连续映射 $f$ 存在不动点 $x^\star$，满足 $f(x^\star) = x^\star$。记 $S_i := \sum_{k \in S_i} g_{ik}(x^\star)$；对每个 $(i,j)$ 的不动点方程为 $x_{ij}^\star (1 + S_i) = x_{ij}^\star + g_{ij}(x^\star)$，即 $x_{ij}^\star S_i = g_{ij}(x^\star)$。

固定参与人 $i$，令 $d_{ij} := u_i(s_{ij}, x_{-i}^\star) - u_i(x^\star)$，则 $g_{ij}(x^\star) = \max(0, d_{ij})$。将不动点方程乘以 $d_{ij}$ 并对 $j \in S_i$ 求和：左边为 $S_i \sum_j x_{ij}^\star d_{ij} = S_i\left(\sum_j x_{ij}^\star u_i(s_{ij}, x_{-i}^\star) - u_i(x^\star)\sum_j x_{ij}^\star\right) = S_i(u_i(x^\star) - u_i(x^\star)) = 0$，此处用到 $\sum_j x_{ij}^\star u_i(s_{ij}, x_{-i}^\star) = u_i(x^\star)$ 及 $\sum_j x_{ij}^\star = 1$。

右边为 $\sum_j g_{ij}(x^\star)\, d_{ij} = \sum_j \max(0,d_{ij})\, d_{ij} = \sum_{j:\, d_{ij} > 0} d_{ij}^2 \ge 0$。令两边相等，得 $\sum_{j:\, d_{ij}>0} d_{ij}^2 = 0$，这是平方和为零，故每一项都为零：不存在使 $d_{ij} > 0$ 的 $j$。由于 $i$ 是任意的，对每个参与人 $i$ 和每个纯策略 $j$ 都有 $u_i(s_{ij}, x_{-i}^\star) \le u_i(x^\star)$——这恰好就是纳什均衡的条件。因此 $x^\star$ 是一个纳什均衡。