Yao 极小极大原理

有限算法—输入博弈 ​

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

$$L(A,u)=\mathbf{1}[A(u)\ne f(u)].$$

随机算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。可视为 ${\mathcal{A}}_c$ 上的分布公理库概率分布Probability distribution · Law定义在可测空间上的概率测度；随机变量的律是由推前得到的一类分布。 $\rho$，输入方的分布记为 $\mu$。两者相遇时的期望损失是

$$L(\rho ,\mu )={\mathbb{E}}_{A\sim \rho ,u\sim \mu }L(A,u).$$

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

定理陈述 ​

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

$$\boxed{{\displaystyle \underset{\rho \in \mathrm{\Delta }({\mathcal{A}}_c)}{min}\underset{u\in U}{max}{\mathbb{E}}_{A\sim \rho }L(A,u)=\underset{\mu \in \mathrm{\Delta }(U)}{max}\underset{A\in {\mathcal{A}}_c}{min}{\mathbb{E}}_{u\sim \mu }L(A,u)}}.$$

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

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

为什么反向需要 minimax ​

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

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

$$\underset{\mu }{max}\underset{A}{min}L(A,\mu )$$

与

$$\underset{\rho }{min}\underset{u}{max}L(\rho ,u)$$

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

通信复杂度中的特化 ​

令 $U=X\times Y$，${\mathcal{A}}_c$ 取通信硬上限至多 $c$ 的确定性两方协议。分布 $\rho$ 由双方共同看见时，它实现一条公共币随机协议公理库随机通信复杂度Randomized communication complexity允许双方使用随机币并在每个固定输入上承受受控错误，以通信量、误差与成本量词共同定义复杂度。；输入分布 $\mu$ 则给出分布通信复杂度公理库分布通信复杂度Distributional communication complexity固定输入分布后，以确定性协议在该分布下的平均错误衡量通信，是随机最坏复杂度的分布侧接口。。在同一硬成本与错误约定下，

$$R_{\epsilon }^{\mathrm{pub}}(f)=\underset{\mu }{max}{D}_{\epsilon }^{\mu }(f).$$

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

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

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

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

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

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

用于下界的标准量词 ​

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

$$\mathrm{\forall }A\in {\mathcal{A}}_c,{\mathbb{E}}_{u\sim \mu }L(A,u)>\epsilon .$$

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

适用边界 ​

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

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

参考资料

• 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.