结果族 111：One-sample matroid prophet inequalities against an almighty adversary · 学科：Theoretical computer science · 验证状态：暂无形式化证明，请以社区核验为准
一排礼盒依次递来，打开看到金额就必须当场决定收不收，收了不能退；更麻烦的是有些盒子互相”犯冲”，犯冲的不能同时收。”先知”是全部看完再挑的人。你不知道金额的分布规律，只允许提前对每个盒子试抽一次看个参考值；安排盒子顺序的对手甚至能看光你的参考值、每次金额，连你掷骰子的种子都一览无余。苛刻到这个地步，本文构造的规则仍保证拿到先知期望收益的固定比例。
关键词卡片
看个具体例子
三个盒子：样本依次为 5、2、6，在线值依次为 8、3、7，且盒 1 与盒 3 犯冲。先知全知全览，拿 8+3=11；一种直觉玩法是”只收明显高过自己样本的盒子”——本例收下盒 1、放弃其余，得 8。论文的正式规则更精细，但接口相同，保证 @@M@@\mathbb{E}[\text{收益}]\ge 2^{-310}\cdot\mathbb{E}[\text{先知}]@@，且收下的组合永远不犯冲。
为什么值得关心
它把”零分布知识”的在线选择推到最严苛的对手模型：连算法的随机种子都被看光，一个样本仍然够用——突破在于”常数比成立”这件事本身，而不在常数大小。
暂无形式化证明（AI 结果待核验）
第一级台阶
把导读的礼盒图景半数学化：有一批依次呈现的选项，每个打开时露出一个数值，你必须当场决定收不收、收了不能退；选项之间存在着”哪些能同时收”的抽象冲突约束。你在开工前对每个选项做过一次独立试抽，看到过一个参考数值。安排呈现顺序的对局者极强：参考值、真实数值、甚至你自己的全部随机选择它都看得见。
第二级台阶
用本科术语精确化。拟阵 M=(E,𝓘) 是满足遗传性与增广公理的独立集族，刻画”可同时拿的组合”；先知基准 OPT_M(v) 是知道全部实现值后在独立集上能取到的最大权之和；先知不等式断言在线规则的期望收益不低于基准的固定倍数。全能对手指在选定呈现顺序前可读全部样本、全部在线值与算法完整随机种子的顺序规则——算法对它毫无信息与随机性优势。
第三级台阶
定理在这样的语境下陈述：对任意有限已知标签拟阵和相互独立的非负随机对 (S_e,V_e)——样本与在线值同律但分布完全未知——存在不依赖分布的可测在线规则，它先收到样本向量，再用与样本、在线值独立的种子运行；则对一切可测的顺序规则（允许依赖拟阵、分布、样本、在线值与完整种子），规则接受集保持拟阵独立，且期望收益不低于 2⁻³¹⁰·E[OPT_M(V)]。”同律”挡住样本失真，”E[OPT]<∞”挡住不可积病态，”可测而非多项式时间”则诚实划定了构造的效力范围。结论即导读那句：在最严酷的对手面前，一个样本仍够换来与规模无关的常数比。
在任意有限拟阵（matroid）上，每个元素仅凭一个独立样本、完全不知道值分布，就存在在线选取规则：即使到达顺序由看得见全部样本、在线值乃至算法完整随机种子的”全能对手”（almighty adversary）决定，仍能拿到离线最优期望收益的固定常数比例（@@M@@2^{-310}@@）。
先知不等式（prophet inequality）把”在线不可撤销选择”与”事后最优”作比较：元素带着各自未知分布的非负值依次到达，看到当前值必须立刻决定接受与否，且已接受集合须始终保持拟阵独立；基准 @@M@@\OPT_M(v)@@ 是知道全部实现值后可取得的最优。经典地，单选择情形在已知分布时有尖锐的 @@M@@1/2@@（Krengel–Sucheston，因子 2 界归功于 Garling）；Kleinberg 与 Weinberg 把同样的 @@M@@1/2@@ 推广到已知分布的任意拟阵。分布未知时，Azar–Kleinberg–Weinberg 提出用独立样本替代分布知识，Rubinstein–Wang–Weinberg 在单选择时用一个样本恢复了最优 @@M@@1/2@@。但对一般拟阵，已有常数比结果要么需要随规模增长的对数级样本数（Fu 等，以及 Feldman–Svensson–Zenklusen 的改进），要么只允许与样本、在线值和随机币都无关的固定顺序（Abdi 等）。在”全能对手”——看清样本、在线值与算法全部随机种子之后再排定顺序——面前，单样本的常数比保证一直空缺，本文补上了这一块。
主定理断言：存在可测的在线选取规则，不依赖任何分布描述。对任意有限已知标签拟阵 @@M@@M=(E,\mathcal I)@@ 与相互独立的非负随机对 @@M@@(S_e,V_e)@@（@@M@@S_e@@ 为样本、@@M@@V_e@@ 为在线值，二者同服从任意律 @@M@@D_e@@），只要 @@M@@\Ex[\OPT_M(V)]<\infty@@，规则先收到样本向量 @@M@@S@@，再用与 @@M@@S,V@@ 独立的种子 @@M@@R@@ 运行；则对任何可测的顺序规则 @@M@@\pi@@——允许它依赖 @@M@@M@@、诸 @@M@@D_e@@、@@M@@S@@、@@M@@V@@ 以及完整种子 @@M@@R@@——规则接受集 @@M@@A@@ 拟阵独立，且
@@M@@D\Ex\Big[\sum_{e\in A}V_e\Big]\ge 2^{-310}\,\Ex[\OPT_M(V)].@@
常数与拟阵的规模、秩及分布均无关；论文不主张多项式时间可实现（第 6 节实际证得更强的 @@M@@2^{-293}@@，定理陈述留有余量）。同一构造还给出秘书问题（secretary problem）推论：随机观察前缀被牺牲后，即使看见全部权重、有序前缀与完整种子的对手任意重排剩余元素，仍有常数比保证。
证明先落到”固定向量”版本（命题 2.1）：权重 @@M@@w@@ 是确定性的隐藏向量，规则从种子中抽取掩码 @@M@@B_0@@，揭示并牺牲其中标签，要证 @@M@@\Ex_R[\min_\pi\sum_{e\in A}w_e]\ge 2^{-293}\OPT_M(w)@@——极小值在期望之内，对手可为每个种子另选顺序，这是全能对手的严酷之处。随后作”胶水”耦合（引理 2.2）：在 @@M@@B_0@@ 上取样本值、在其余坐标取在线值拼成的向量与 @@M@@V@@ 同律且与整个种子独立；逐到达归纳可知两种执行接受集完全相同，故对手选任何顺序都不优于上述取极小。
主分支先把权重向下舍入为以 @@M@@B=2^{32}@@ 为底的几何级数，再让四个独立掩码分工：@@M@@H@@（概率 @@M@@1/2@@）过滤候选，@@M@@D@@（@@M@@1/4@@）登记权重组并提供密度数据，@@M@@C@@、@@M@@T@@（各以稀疏率 @@M@@t=2^{-140}@@）分别提供”卫兵”与在线资格稀疏化；@@M@@H\cup D\cup C@@ 上的标签被牺牲。对每个登记组 @@M@@h@@，密度扩张 @@M@@Q_h(P)@@ 取最大化 @@M@@|D_h\cap Z|-\kappa\rk(Z)@@（@@M@@\kappa=2^{100}@@）的最大 flat（等于自身闭包的集合），自低向高迭代出名义路径 @@M@@X_h(k)@@，@@M@@k@@ 是与真实到达时间无关的辅助时刻；再用卫兵提前一步扩张成守卫路径 @@M@@F_h(k)@@。按随机奇偶把最终路径分层，每层在基 flat @@M@@\widehat F(b-2)@@ 上贪心接受使秩增加的标签；嵌套性保证无论何种到达顺序，并集始终拟阵独立。
分析需闯三关。其一是安全：把卫兵掩码沿辅助时间反向暴露，配合”不相交查询证书”引理（成功交易数至多 @@M@@\log(1/\delta)@@），可知每个非环标签大概率在条件退出概率 @@M@@p\ge\eta@@ 的步骤离开名义路径；再用混合转移把离去卫兵的比特换成测试掩码比特，联合退出概率恰为 @@M@@p^2@@，一个确定性包含关系保证联合退出即”安全”。其二是样本转秩：安全样本本身已被牺牲，残差集合又依赖本组掩码，逐集合估计行不通；作者以”标记枢轴”组合引理（依靠 Schläfli 超平面区域计数）在掩码暴露前枚举出大小至多 @@M@@\exp(1000\log\kappa\cdot n/\kappa)@@ 的残差族，一次联合界排除大残差。其三是记账：名义路径换成最终路径的扩张费，由单一生成元集合经条件秩的伸缩求和只付一次账；独立 @@M@@T@@ 稀疏化后的秩统计量对一切排列同时下界接受数，此时才取期望并按权重层加权求和。最后与处理权重集中于单标签的最大值分支等概率混合，得常数 @@M@@2^{-140-16-5-100-32}=2^{-293}@@。
本文暂无形式化证明，按 OpenAI 官方声明，未经形式化的结果可能存在问题，请以社区核验为准。本结果族目前仅此一篇手稿，结论自成一体：固定向量命题、单样本模拟与秘书推论由同一条构造链推出。常数 @@M@@2^{-310}@@ 数值极小，其意义在”单样本＋全能对手”下首次取得与秩无关的常数比这一质的突破；与 Abdi 等固定顺序下的 @@M@@1/2@@ 结果相比，两者对手接口不同（逐序下界对照期望内的极小值），不宜直接比较。
问 1：证明里最脆弱的一步是哪里？
答：三道关卡中第二道——”样本转秩”——最为惊险。安全样本本身已被牺牲，残差集合依赖被牺牲的掩码，逐集合估计行不通；作者只能用”标记枢轴”组合引理（其计数依靠 Schläfli 超平面区域数）在掩码暴露前枚举大小至多 exp(1000·log κ·n/κ) 的残差族，再一次联合界排除大残差（引言 Proof strategy 第二损失段）。把一个实几何计数引理搬进拟阵掩码语境并保证界只依赖插入生成元数而不依赖辅助时刻数，这里任何一步松弛都会让秩下界落空。
问 2：哪个假设去掉后结论就塌？
答：样本与在线值必须同律 (S_e,V_e) 同服从未知 D_e。整个”胶水”耦合（引理 2.2）靠”在牺牲掩码上取样本、其余取在线值拼出的向量与 V 同律”来把固定向量命题搬运到单样本模型；若样本律与在线值律有偏，这一恒等接受集论证立即失效。论文未讨论样本失真（miscalibration）情形。
问 3：与已有工作相比真正的新意是什么？
答：接口之争。Fu 等与 Feldman–Svensson–Zenklusen 的常数比需要随 n 增长的样本预算；Abdi 等的单样本 1/2 只允许与一切随机量无关的固定顺序——那是对每个固定序控制”期望收益的最小值”，而全能对手要求控制”收益最小值的期望”，是严格更难的信息模式（引言对比段明言两者不可直接比较）。本文首次在后者下用单样本取得与秩无关的常数。
问 4：反向暴露卫兵的安全性论证为何可信、又最容易怎么错？
答：所有掩码一开始就全部抽定，反向暴露只是重新条件化的记帐手段，不向对手隐藏任何硬币——这在原则上自洽。但”沿辅助时间反向暴露使名义 flat 收缩、不相交查询证书至多 log(1/δ) 次”这类论证对条件次序极其敏感：若某处的条件 σ-代数次序写错，退出概率 η 的下界就会静默失效。这是全文最需要逐行核验的条件概率簿记。
问 5：2⁻³¹⁰ 这个数字说明了什么？
答：它是损失预算的乘积：稀疏率 t=2⁻¹⁴⁰、密度参数 κ=2¹⁰⁰、几何舍入底 B=2³² 及分层奇偶等各扣一项，第 6 节实际证得 2⁻²⁹³（2^{-140-16-5-100-32}）。数值本身无优化意图，其意义在”常数比成立”这一质的突破；改进常数是显然的后续问题，论文未给出改进路线。
问 6：谁会用到它、下游是什么？
答：直接下游有二：秘书问题推论——随机观察前缀被牺牲后，看见全部权重与完整种子的对手任意重排剩余元素仍有常数比；以及 FSZ16 全能对手型在线竞争消解（contention resolution）框架的单样本版。更远处是分布未知的一口价机制设计。注意规则只是可测构造，论文明言不主张多项式时间或独立性预言机可实现，机制设计者直接引用前须补计算层。
总评
这是”零分布知识＋全知对手”设定下拟阵先知不等式从无到有的突破，分量在模型而非常数；最大风险集中在标记枢轴枚举与反向暴露两处精细组合论证上，且全文无形式化证明，宜视为待独立核验的里程碑。