结果族 110：Optimal-order randomized k-server on arbitrary metrics · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
想象一家只有 k 辆车的代驾公司：订单一个接一个冒出来，调度员必须立刻派一辆车过去，而且永远猜不到下一单在哪。这篇论文回答一个憋了三十多年的问题：会掷骰子的随机调度，最坏会比”开了上帝视角、早就知道全部订单”的完美调度贵多少倍？答案是至多约 (log k)² 倍——并且证明了这个倍数已经不可能再有本质改进。
关键词卡片
看个具体例子
取 k=15 辆车：经典的确定性最优策略约 2k−1=29 倍；本文的随机策略期望只需 @@M@@C\cdot(\log_2 16)^2=C\cdot 16@@ 倍（C 为绝对常数），而且对每张地图、每组起点、之后的一切订单序列都由同一个策略包办。2023 年已有人造出地图，逼任何随机策略都付出约 log²k 倍——所以”平方对数”这个阶刚好卡在最优。
为什么值得关心
k-server 是缓存置换、云资源调度等在线问题的共同骨架；本文确定了随机化竞争比的精确阶数，为这条争论多年的战线画上句号。
暂无形式化证明（AI 结果待核验）
第一级台阶
把导读里”代驾公司掷骰子派单”的图景换成半数学的说法：场上有 k 个可移动的服务单元，信息逐条到来且事先未知，每次都必须选定一个单元前去响应，费用按它在带距离的地图上走过的路程计。决策者可以随机化，出题的一方虽然刁钻，却不能偷看骰子的结果。
第二级台阶
现在用本科语言把对象钉死。度量空间 (X,d) 就是满足三角不等式的带距离点集，允许无限、无界；策略指一条”看到已揭示前缀后移动哪个服务器”的随机规则；不经意对手意味着请求序列独立于策略的随机数而事先固定。策略的期望总花费除以预知全部请求的事后最优花费 OPT，称为竞争比，问题问的是它对一切地图的最坏值。
第三级台阶
主定理在这样的语境下陈述：存在绝对常数 C，对每个 k≥2、每个至少 k+1 个点的度量空间和每组初始位置，都有一个随机在线策略，使一切有限请求序列的期望花费不超过 C·(log(k+1))²·OPT 再加一个只依赖地图与起点、不依赖序列及其长度的有限项 B；初始位置两两不同时可取 B=0。”不经意”假设挡住了对手临场变招，”有限序列”保证双方花费有定义。结论与已知的 Ω(log²k) 下界合并，便得导读里那句话：平方对数正是最坏情形的精确阶数，同一策略包办所有视界。
证明了在任意度量空间上，随机化 @@M@@k@@-server 对不经意请求序列可达竞争比 @@M@@O((\log(k+1))^2)@@，与已知最坏情形下界 @@M@@\Omega(\log^2 k)@@ 同阶，首次锁定了这一基本在线问题随机竞争比的精确阶数。
@@M@@k@@-server 问题由 Manasse、McGeoch 与 Sleator 于 1988 年提出：@@M@@k@@ 个服务器栖身于度量空间，请求点逐一到达，算法必须每次移动一个服务器到请求点，代价是移动距离；它是缓存置换等在线服务问题的统一抽象。离线最优预知全部请求，在线算法只看到已揭示前缀。确定性情形下著名的工作函数算法（work function algorithm）达到 @@M@@2k-1@@ 竞争比，下界为 @@M@@k@@。由于分页（均匀度量情形）的随机算法能达到调和数 @@M@@H_k@@ 的最优竞争比，学界长期信奉”随机化可在一切度量上取得 @@M@@O(\log k)@@“的猜想。2023 年 Bubeck、Coester 与 Rabani 证伪了它：存在 @@M@@(k+1)@@ 点度量迫使任何随机算法付出 @@M@@\Omega(\log^2 k)@@。而上界一侧，此前的最好结果要么带度量点数因子（如 @@M@@O(\log^2 k\log n)@@），要么只对层次分离树（HST）成立，最坏度量的匹配上界一直悬而未决。
主定理：存在绝对常数 @@M@@C@@，对每个 @@M@@k\ge 2@@、每个至少含 @@M@@k+1@@ 个点的度量空间 @@M@@(X,d)@@（允许无限、无界）及每个初始位置组 @@M@@s\in X^k@@，存在随机在线策略 @@M@@A@@ 与有限数 @@M@@B\ge 0@@，使对所有有限请求序列 @@M@@\sigma@@ 有
@@M@@D\mathbb{E}[\mathrm{cost}_{A,s}(\sigma)]\le C(\log(k+1))^2\,\mathrm{OPT}_{X,d,k,s}(\sigma)+B,@@
其中 @@M@@C@@ 不依赖度量的任何性质，@@M@@B@@ 依赖 @@M@@(X,d),k,s@@ 但不依赖请求序列及其长度，且同一个策略服务所有有限序列与所有视界。当初位置互异时可取 @@M@@B=0@@。结合上述 @@M@@\Omega(\log^2 k)@@ 下界，平方对数阶正是随机 @@M@@k@@-server 在最坏度量下的最优阶。
证明先在”策略额外知道请求分布”的强化模型中建立分布式估计：为每个输入选定一条离线最优轨迹作为隐藏比较者（hidden comparator），策略只使用其后验分布（条件于已揭示前缀），从不窥见未来的真实实现。核心构造先在多个距离尺度上随机划分有限度量，点在各层的胞腔标签串确定一棵固定树的叶，隐藏最优给出每个树顶点之下的期望服务器数 @@M@@m_v@@；再证支配型树分配定理（dominated tree allocation）：构造子树分数质量 @@M@@q_v\le C_0 m_v@@，根处为 @@M@@k@@，被请求的叶子至少分得 1，多余质量可停泊（parking）在内部顶点、不必紧跟快速变化的后验比例，其总移动 @@M@@V\le C\ell P@@，其中 @@M@@\ell=1+\log(k+1)@@、@@M@@P@@ 为比较者嵌入树后的移动。分区编辑费由一个紧变分势（pilot potential）支付：它是后验计数测度的凹的最小线性泛函，凹性使过滤步的期望不增；质量集中迫使极小位点在请求近旁近乎满载，搬移它并修复容量约束即得小斜率估计，经球质量比（ball-mass ratio）跨尺度望远镜求和恰得一个对数，从而 @@M@@P\le C\ell Q@@（@@M@@Q=\mathbb{E}\,\mathrm{OPT}@@）。保护机制上，重球（heavy ball）罩住高度集中的请求，其余尺度用按时间顺序的名册（roster）配倍增资格层级，首次命中损失依赖局部质量比而非逐层最坏对数，随机退役保持名册有限。最后把分数质量用原度量的代表点实现——保留锚点的漂移由一个仿射势与停泊质量系数逐点支付——再经允许父子状态相关的动态平衡舍入（balanced rounding）取整为恰好 @@M@@k@@ 个服务器，只付绝对损失，最后用匹配势的惰性模拟（lazy simulation）回到真实移动模型。三重账本 @@M@@P\le C\ell Q@@、@@M@@V\le C\ell P@@、@@M@@\mathbb{E}\,\mathrm{cost}\le C(V+\ell P+\ell Q)@@ 叠乘出 @@M@@\ell^2@@。收尾先由独立回合放大（episode amplification）经”正词—逆词—复位词”重复 @@M@@N@@ 次把可加项摊薄至消失，再用有限极小极大（Yao 原理）与 Kuhn 混合策略转行为策略覆盖任意有限输入族，最后借 Tychonoff 乘积紧性得到适用于所有有限输入的单一策略；初始位置有重复时以互异虚拟起点运行并匹配模拟，多付的匹配距离即 @@M@@B@@。
本文是结果族 110 的存在性一半；姊妹篇《Uniform computation of the squared-logarithmic k-server bound》仅引用本文”互异初始位置、零可加项”的条款作为可行性证书，把存在性落实为可一致计算的算法，两篇互相支撑。本文对策略不作任何计算效率承诺，效率问题恰由姊妹篇处理。按 OpenAI 官方声明，未经形式化的结果可能有问题；本文暂无 Lean 形式化证明，宜以社区核验为准。
问 1：证明把成本拆成 P≤CℓQ、V≤CℓP、E cost≤C(V+ℓP+ℓQ) 三级账本，哪一级最脆弱？
答：最脆弱的是分区一侧的紧变分势（pilot potential）。它要同时支付分区编辑费、并证明质量集中迫使极小位点在请求近旁近乎满载，再经球质量比跨尺度望远镜求和凑出一个对数（引言”Main ingredients”第二条）。引言自己承认：Lee 的 fusible-HST 框架正因同类 fission potential 在其 5.3.2 节的缺口而被撤回，本文声称在 partitions/travel 两节重证所需估计、不引用已撤回论证——这正是需要最仔细核验的接缝。
问 2：与 Bubeck–Cohen–Lee–Lee–Mądry 的 O(log²k)（仅对 HST）相比，真正的新意是什么？
答：BCLLM18 的结果经静态嵌入推到一般有限度量须乘 log n，得不到只依赖 k 的界。本文改用隐藏比较者的后验测度驱动分区调度，产生固定标签树，直接在任意（含无限、无界）度量上得到 O(log²k)，消除 n 依赖，并与 BCR23 的 Ω(log²k) 下界闭合成精确阶（引言 Context 节末段）。
问 3：”不经意对手”这个假设为什么不能去掉？
答：定理的全部力量来自请求序列独立于策略的随机数；后验分布只对已揭示前缀取条件，从不窥见未来实现。若对手可依随机结果临场变招，这套 posterior 构造失效；论文未讨论自适应对手情形，也未在该模型下给出任何界。
问 4：可加项 B 从何而来，为何初始位置互异时可取零？
答：B 来自把重复的初始位置换成互异虚拟起点运行策略、再用匹配模拟真实服务器，多付的匹配距离与序列无关（定理 1 及其后说明）。位置互异时无需虚拟化，故 B=0。存在性层面 B 无害，但姊妹篇明确指出计算版本中 B 可能极其巨大且依赖实例。
问 5：这类结果最可能以什么模式出错？
答：典型风险藏在多尺度复合估计的常数链：分区、分配、实现、舍入四级各自”只付一个对数”，若有一级暗中多乘一个对数或漏付编辑费，ℓ² 便不成立。另外动态平衡舍入引理允许父子状态相关，相关归纳的一致性与可测性论证是常见漏洞点。本文纯存在性、无形式化证明，发表前的核验应聚焦这两处。
问 6：谁会用到它？
答：它是存在性定理，对策略不作计算效率承诺（定理后第一句），效率由姊妹篇《Uniform computation》落实。理论价值是终结随机 k-server 竞争比阶数之争；方法学上，后验驱动的分区与带”停泊”的支配型树分配，可能迁移到其他在线度量问题。
总评
这项工作把三十余年悬而未决的随机 k-server 竞争比钉死在平方对数阶，分量极重；最大风险在于多尺度势函数账本浩繁而未经形式化，历史教训（Lee 撤稿）就悬在同一个技术环节上。