技术摘要：用于精细化先知不等式的核方法

1. 问题陈述

本文研究了单次选择先知不等式（single-selection prophet inequality），这是一个经典的贝叶斯在线选择问题。在该问题中，决策者按顺序观察独立且非负的随机变量 $X_1, \dots, X_n$，并必须不可撤回地选择至多一个，以最大化其相对于后验最大值 $M = \max_i X_i$ 的期望值。

虽然经典结果已经确立了紧致的最坏情况竞争比（例如，对于非同分布情况为 $1/2$，对于 IID 情况使用单阈值规则为 $1-1/e$），但这些保证是由以“罕见且极大的最大值实现”为特征的“困难实例”驱动的。这些实例通常表现出先知基准值的高离散性，这可能无法反映在实际应用（如发布价格机制）中常见的轻尾环境。

作者提出通过对先知的最大值分布 $G$ 施加相对方差限制来精细化最坏情况分析：
$$\Gamma^2(G) = \frac{\text{Var}(M)}{\mathbb{E}[M]^2} \leq \gamma$$
其中 $\gamma$ 是一个非参数复杂度度量：

• $\gamma = 0$：最大值为确定性的，允许通过阈值恢复出完整的先知值（比例为 1）。
• $\gamma \to \infty$：约束失效，回归到经典的最坏情况常数。

目标是刻画三种到达模型下的最优单阈值竞争比 $C(\gamma)$：IID 模型、固定顺序模型（Fixed Order）（独立非同分布）以及先知秘书模型（Prophet Secretary）（随机顺序）。

2. 方法论：核框架

其核心技术贡献是引入了一种核方法（kernel method），将先知不等式问题转化为在分位数函数上的无限维凸规划问题。

2.1 分位数表示

该问题利用最大值 $M$ 的分位数函数 $Q = G^{-1}$ 进行重构。在归一化 $\mathbb{E}[M] = 1$ 后，相对方差约束变为关于 $Q$ 的 $L^2$ 范数的凸约束：
$$\int_0^1 Q(u)^2 du \leq 1 + \gamma$$
分位数函数的可行集记为 $\mathcal{Q}_\gamma$。

2.2 核化

由最大分位数水平 $q \in [0, 1]$ 参数化的单阈值期望收益可以表示为 $Q$ 的一个线性泛函：
$$L_K(Q, q) = \int_q^1 Q(u) K_q(u) du$$
这里，$K_q(u)$ 是针对特定到达模型的核函数。这种表示法将模型动态隔离到核函数中，从而保留了通用的优化结构。最坏情况下的比例即为核博弈的值：
$$\text{Val}(\mathcal{Q}_\gamma, K) = \inf_{Q \in \mathcal{Q}_\gamma} \sup_{q \in [0, 1]} L_K(Q, q)$$

2.3 关键技术工具

1. 强极小极大对偶性（Strong Minimax Duality）： 在满足温和条件（拓扑容许性和拟凹性）的情况下，作者通过 Sion 定理证明：
   $$\inf_{Q} \sup_{q} L_K(Q, q) = \sup_{q} \inf_{Q} L_K(Q, q)$$
   该对偶性在分位数阈值空间中成立，允许通过对固定阈值 $q$ 进行最小化来解决对手的问题（即对 $Q$ 的最小化）。

2. 变分归约（Variational Reduction）： 对于有界方差情况（$\mathcal{Q}_\gamma$），对 $Q$ 的内层最小化通过 Euler-Lagrange 参数化方法简化为一个单参数族：
   $$Q_{q,s}(u) = a_{q,s} + b_{q,s} (K_q(s) - K_q(u))_+$$
   其中 $s \in [q, 1)$ 是接触点。这使得无限维问题坍缩为对标量 $s$ 的优化问题。

3. 极值点归约（Extreme-Point Reduction）： 对于随机时界模型（无方差约束），问题归约为对归一化阶梯函数（$\mathcal{Q}_\infty$ 的极值点）的优化。

3. 主要贡献与结果

3.1 IID 模型

作者推导出了有界方差曲线 $C^2_{\text{IID}}(\gamma)$ 的精确特征。

• 结果： 该值由一个关于闭式函数 $\psi(q, s)$ 的极大极小程序给出（定理 2）。
• 渐近性：
  • 当 $\gamma \to 0$ 时：$C^2_{\text{IID}}(\gamma) = 1 - \Theta(\gamma^{1/3} / \log^{2/3}(1/\gamma))$。
  • 当 $\gamma \to \infty$ 时：$C^2_{\text{IID}}(\gamma) = 1 - 1/e + \Theta(1/\gamma)$。
• 算法意义： 对偶解 $q^\star$ 给出了渐近最优的有限时界阈值 $T_n = F^{-1}(1 + (\log q^\star)/n)$。

3.2 固定顺序模型

对于固定顺序下的独立非同分布变量，其核函数为 $K^{\text{FO}}_q(u) = q/u^2$。

• 结果： 由于核函数中不存在对数项，允许得到闭式解（定理 3）：
  $$C^2_{\text{FO}}(\gamma) = \frac{3 + 2x_\gamma^2}{2(3 + x_\gamma^2)}, \quad \text{其中 } x_\gamma = 2 \sinh\left(\frac{1}{3} \text{arsinh}\sqrt{\frac{3}{4\gamma}}\right)$$
• 渐近性： 当 $\gamma \to 0$ 时，向 1 的收敛速度为 $1 - \Theta(\gamma^{1/3})$，由于缺乏对数改进，其速度略慢于 IID 情况。

3.3 先知秘书模型

在该模型中，最大值分布并不能唯一确定实例。核方法提供了一个可计算的下界（定理 4）。

• 分离结果： 一个令人惊讶的发现是，对于任何有限的 $\gamma > 0$，先知秘书的比例都严格小于 IID 比例（$C^2_{\text{PS}}(\gamma) < C^2_{\text{IID}}(\gamma)$），尽管它们共享相同的无约束最坏情况常数（$1-1/e$）。这是通过构造一个具有相同最大值分布但引入了对单阈值不利的“罕见顶端信号”的非 IID 分解来证明的。

3.4 随机时界模型

该框架被应用于观测到概率生成函数为 $\phi$ 的 IID 值直至随机时界 $N$ 的情况。

• 结果： 推导出了一个紧致下界：$C_{\text{IID}}(\phi) \geq 1 - \phi(1 - 1/\mu)$。
• 条件： 当 $z \mapsto (1-z)/(1-\phi(z))$ 是凸函数时，等式成立，该条件在单调风险率（MHR）分布（如几何分布、泊松分布、二项分布）中得到满足。

4. 重要性与主张

本文声称提供了一种系统性的替代方案，用以取代先知不等式文献中通常需要的特设构造（ad hoc constructions）。通过将重点从为每个模型发明特定的困难实例，转向验证对应核函数的结构条件，作者统一了多种不同到达模型的分析。

关于本研究重要性的核心主张包括：

• 最坏情况的精细化： 相对方差约束提供了一种非参数化的插值，连接了集中分布实例与经典的极端情况，解决了标准竞争比存在的“过度悲观”问题。
• 恢复对偶性： 核化形式在分位数空间中恢复了强极小极大对偶性，解释了为什么均匀分位数规则能够在原始空间中极大化保证失效的情况下，依然能达到先知风格的保证。
• 精确特征刻画： 该方法给出了 IID 曲线和固定顺序曲线的精确公式，并揭示了 IID 与先知秘书模型在有限方差下的严格分离。
• 广泛的适用性： 该技术可以扩展到更广泛的凸约束（如 $L^p$ 空间、Orlicz 空间）以及不同的时界设置，表明其作为单阈值设置下通用框架的潜力。

作者明确指出，虽然核方法为 IID 和固定顺序模型提供了精确结果，但对于先知秘书模型，它仅提供了一个下界，因此 $C^2_{\text{PS}}(\gamma)$ 的精确刻画仍是一个开放问题。同样，由于目前的框架专门针对静态单阈值，将其扩展到动态（自适应）阈值被确定为一个未来的研究方向。