Yao 极小极大原理 | Codeboy's Blog

形式陈述

有限算法—输入博弈

设合法输入集 $U$ 有限，并固定资源硬上限 $c$ 。令 $\mathcal A_c$ 为成本至多 $c$ 的确定性算法集合；只保留它们在 $U$ 上不同行为后，这也是有限集。对算法 $A\in\mathcal A_c$ 与输入 $u\in U$ ，以有界函数 $L(A,u)$ 记录损失。判定问题通常取零一损失

L(A,u)=\mathbf1[A(u)\ne f(u)].

随机算法可视为 $\mathcal A_c$ 上的分布 $\rho$ ，输入方的分布记为 $\mu$ 。两者相遇时的期望损失是

L(\rho,\mu) =\mathbb E_{A\sim\rho,\ u\sim\mu}L(A,u).

算法方想让损失小，输入方想让损失大。资源单位、输出约定、promise 域与错误类型必须在进入博弈前固定；若等式两侧使用不同算法类或成本口径，便不再是同一个矩阵博弈。

定理陈述

有限矩阵博弈的 minimax 定理给出

\boxed{ \min_{\rho\in\Delta(\mathcal A_c)} \max_{u\in U} \mathbb E_{A\sim\rho}L(A,u) = \max_{\mu\in\Delta(U)} \min_{A\in\mathcal A_c} \mathbb E_{u\sim\mu}L(A,u) }.

左边先选择一份随机算法，再由对手挑它损失最大的固定输入；右边先选择输入分布，再允许确定性算法针对该分布优化，最后取最难分布。等式把“每个固定输入上的随机保证”转成“一个固定分布下所有确定性算法的平均保证”，同时保留相同的资源上限 $c$ 。

在零一损失下，阈值形式是：存在成本至多 $c$ 、逐输入错误至多 $\varepsilon$ 的随机算法，当且仅当对每个输入分布 $\mu$ ，都存在成本至多 $c$ 、 $\mu$ -平均错误至多 $\varepsilon$ 的确定性算法。有限性确保策略单纯形紧致、损失双线性；无限策略或输入空间不能只凭相似的量词外形交换 min 与 max。

为什么反向需要 minimax

从随机算法到每个固定分布不需要 minimax。若随机算法对每个输入的错误至多 $\varepsilon$ ，固定任意 $\mu$ 后联合平均错误也至多 $\varepsilon$ ；再对随机币取平均，至少有一个确定性算法的 $\mu$ -错误不超过 $\varepsilon$ 。

困难的是反向：已知每个 $\mu$ 各自有一个好算法，不代表可以凭直觉挑一份算法分布同时照顾所有输入。有限 minimax 定理正是把

\max_\mu\min_A L(A,\mu)

与

\min_\rho\max_u L(\rho,u)

连接起来。混合策略 $\rho$ 是一份统一的随机算法；它必须在输入揭示之前固定，不能让不同输入各自选择最有利的随机分布。

直觉

随机算法把自己的弱点分散在不同确定性策略上，输入对手则试图找到一份分布，让所有低成本确定性策略都暴露弱点。Minimax 说明在有限、同预算的零和博弈里，这两种混合方式达到同一个值；困难分布不是经验样本，而是输入方的最优混合策略。

量词顺序是原理的全部锋芒。逐个算法各挑一个坏输入，只得到随算法变化的反例，随机混合可能绕开它们；Yao 下界必须先固定同一分布，再证明每个低成本确定性算法都平均失败。这样才能反推出任何随机算法都有某个固定输入失败。

例子与边界

通信复杂度中的特化

令 $U=X\times Y$ ， $\mathcal A_c$ 取通信硬上限至多 $c$ 的确定性两方协议。分布 $\rho$ 由双方共同看见时，它实现一条公共币随机协议；输入分布 $\mu$ 则给出分布通信复杂度。在同一硬成本与错误约定下，

R^{\mathrm{pub}}_\varepsilon(f) =\max_\mu D^\mu_\varepsilon(f).

考虑一 bit XOR， $f(x,y)=x\oplus y$ ，并令 $c=0$ 。确定性公开输出协议只能恒输出 $0$ 或恒输出 $1$ 。输入方取四个输入上的均匀分布时，两种常数协议都恰错一半，所以分布侧值至少 $1/2$ 。协议方各以概率 $1/2$ 选择两种常数协议，则对每个固定输入都恰以概率 $1/2$ 出错，最坏输入侧值至多 $1/2$ 。这个小博弈把“困难分布”和“协议混合”画成了同一枚硬币的两面。

整数预算和“至多 $\varepsilon$ ”边界都包含在可行集合中。若改用严格错误不等式、期望通信或私有币协议，需要分别处理闭性、截断和随机种子共享；不能删掉模型标记后继续复用等号。

查询与性质测试中的特化

对固定长度的有限输入域，让 $\mathcal A_q$ 包含所有深度至多 $q$ 的确定性查询决策树。随机查询算法固定随机带后恰落入这个集合。因此，只要找到一个输入分布，使每棵 $q$ -query 确定性树的平均错误都大于 $\varepsilon$ ，就排除了逐输入错误至多 $\varepsilon$ 的 $q$ -query 随机算法。

性质测试带有 yes／far promise 时，困难分布必须完全支持在合法域内。常见做法是以某个先验混合 yes 分布 $\mathcal Y$ 与 far 分布 $\mathcal N$ ，再证明任何浅决策树看到的 transcript 都不足以判断来自哪一侧。这里的策略是查询树，不是通信协议；两者使用同一个有限极小极大等式，却保留各自的 oracle 语义和成本单位。

一个常见错误是针对每棵树分别挑坏输入。这只证明每个确定性算法都有弱点，坏输入却可能随算法改变；随机混合恰能分散这些弱点。Yao 下界要求先固定一份对整个低成本算法类共同困难的分布，再量化所有确定性算法。

适用边界

定理使用有限算法—输入矩阵。无限输入、无限精度消息或非紧策略空间需要拓扑、可测性与相应 minimax 条件；“同样是双方对抗”不足以无条件交换 min 与 max。

期望成本允许少量很长的运行，策略集合不再只是深度 $c$ 的有限树。常见处理是先截断并支付额外错误，再应用硬预算版本；截断阈值、增加的错误以及是否保持 promise 都要进入最终结论。

推论与应用

用于下界的标准量词

要证明资源 $c$ 不足，应构造固定分布 $\mu$ 并证明

\forall A\in\mathcal A_c, \qquad \mathbb E_{u\sim\mu}L(A,u)>\varepsilon.

通信中 $A$ 是低通信协议，查询中则是浅决策树。困难分布还必须支持在问题合法域内；若 $f$ 是偏函数， $U$ 只含 promise 输入。把质量放到 promise 外，或让成本口径从硬上限偷偷变成期望，都不能推出原模型的随机下界。

在通信中，Yao 把 public-coin worst-case complexity 化为最难输入分布上的确定性 distributional complexity；在查询与性质测试中，它把随机算法化为浅决策树分布。可复用的是有限博弈的量词转换，具体下界仍要由矩形、不可区分 transcript 或信息论证完成。

参考资料

Andrew Chi-Chih Yao, “Probabilistic Computations: Toward a Unified Measure of Complexity,” FOCS, 1977, pp. 222–227.
Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997, Section 3.3.
Anup Rao and Amir Yehudayoff, Communication Complexity and Applications, Cambridge University Press, 2020, Chapter 3.

形式陈述 ​

有限算法—输入博弈 ​

定理陈述 ​

为什么反向需要 minimax ​

通信复杂度中的特化 ​

查询与性质测试中的特化 ​

适用边界 ​

用于下界的标准量词 ​

反向链接