对手下界方法

算法只看见已经询问的信息，对手便尽量推迟会缩小候选集的承诺。它不是运行中篡改一个秘密输入，而是持续维护一组仍能解释全部答案的输入；最后任选其中一个，算法在这条真实输入上确实经历了同样的困难路径。

下界的量词是“对每个算法，都能找到一个困难输入”，而不是“存在一个输入，让所有算法都很慢”。不同算法可以被不同问答路径难住；固定算法后，对手最终选出的补全才是对应的真实输入。

有效证明需要一个可量化不变量，例如“仍可能是最大值的元素数”或“尚未区分的排列数”。只说对手总给最麻烦答案，不足以证明这些答案彼此兼容，也无法推出查询次数。

考虑只允许两两比较、要求找出 $n\ge 1$ 个互异元素最大值的问题。初始每个元素都可能最大。对手对每次比较任选一个尚未矛盾的方向，并把失败者标记为“不再可能最大”；一次比较至多淘汰一个候选。正确结束时必须只剩一个候选，因此至少需要 $n-1=\mathrm{\Omega }(n)$ 次比较。

全局一致性可由比赛有向图说明：把胜者指向败者，对手始终保持图无环；任一拓扑序都能赋予互异数值，使所有已答比较同时成立。算法若在两个未输过的元素仍存在时停止，可选拓扑序让任一个成为最大，故同一输出不可能对两种补全都正确。

例如四个元素 a,b,c,d，已知 a>b 和 c>d 后，仍有 a、c 两个最大值候选。赋值 $(a,b,c,d)=(4,1,3,2)$ 与 $(3,1,4,2)$ 都解释这两次回答，却有不同最大值。第三次比较 a 与 c 才能合并两条胜负链；没有必要再比较全部六对元素。

一般的自适应对手证明首先针对确定性算法。要推出随机算法对固定输入的期望下界，不能让输入事后依赖算法的秘密随机位；常用办法是固定困难输入分布，再应用 Yao 原理。不过，找最大值这个例子更强：任何正确执行在结束时都必须让另外 $n-1$ 个元素各输过一次。因此对始终正确的随机比较算法，每条终止执行同样至少需 $n-1$ 次比较，不必借助 Yao。允许出错概率时则须重新论证。

对手法可证明选择、搜索、在线算法和数据结构查询下界。设计时应依次写清候选对象、回答策略、不变量、每次查询最多减少多少不确定性，以及最终两个不同输出的可实现补全。

与叶数法相比，对手法更容易利用问题结构和自适应查询；两者都在追踪可区分信息。若对手不变量无法给出紧界，信息论计数、通信复杂度或 cell-probe 技术可能更合适。