带截止时间的 Pandora 问题存在 1/2 近似吗？

1/2 保证究竟衡量什么

Pandora 问题刻画的是在代价高昂的备选项之间进行序贯搜索：每个箱子装有一个来自已知分布的不确定价值，打开它要付出已知成本，搜索者决定何时停止并取走已打开箱子中的最好价值。在 Berger 等人提出的截止时间变体中，每个箱子还有一个公开已知的截止时间，打开和承诺都必须遵守它。目标是所选箱子的价值减去总开箱成本。

1/2 是同一实例上两个期望效用之间的比值。较低的一侧是论文算法获得的效用。较高的一侧记作 OPT，是采用“延迟到停止”承诺规则的最佳完全自适应策略：它可以根据此前观察到的一切选择下一个箱子，也可以选择任何此前打开过的箱子，即使该箱子的截止时间已过。截止时间只约束它的开箱行为。由于这一基准是论文定义的三种承诺规则中最宽松的一种，针对它的保证也适用于“延迟到截止时间”或“立即承诺”规则下的完全自适应最优策略。

基准的选择会影响如何理解这一结果。算法本身在两处刻意较弱：它是部分自适应的，在任何价值被观察到之前就固定箱子集合及其开箱顺序；它采用立即承诺，箱子一打开就不可撤销地接受或丢弃。因此，1/2 是一个受限策略相对于一个宽松比较对象取得的，而不是同类之间的比较。

Weitzman 规则为何在截止时间下失效

在经典问题中，Weitzman 规则是最优的。每个箱子有一个保留值 r_i，由 c_i = E[(v_i - r_i)^+] 定义，即开箱成本等于价值超过该阈值的期望超出量。该规则按保留值从大到小的顺序开箱，一旦已观察到的最好价值达到未打开箱子中最大的保留值就停止。开箱顺序事先固定，但停止决策会根据观察到的价值调整。

截止时间破坏了开箱顺序。打开一个箱子可能使另一个箱子不可用，因此顺序不仅决定成本和信息，还决定哪些选项仍然可行。论文给出一个两个箱子的实例，说明这种失效可以无界。箱子 1 的截止时间为 1，箱子 2 的截止时间为 2，箱子 2 的保留值略大，因此 Weitzman 规则先打开箱子 2。此后箱子 1 无法再打开，如果箱子 2 取值为零就没有退路。该规则的期望效用为 1/N + 1/N^2，而先打开箱子 1 并立即承诺至少能得到 1，因此随着 N 增大，比值趋于零。

诊断很具体：保留值顺序忽略了截止时间，而“延迟到停止”承诺无法挽回一个截止时间已过、尚未打开的箱子。任何修正都必须选择一个可行集合和遵守截止时间的顺序，再决定该集合的价值中有多少能在立即承诺下保留下来。

与预言不等式建立直接联系

此前的 0.158 保证来自一串黑箱归约。Berger 等人通过保留值恒等式把截止时间模型与一个预言不等式联系起来，其中自适应差距界贡献因子 1/2，子模最大化贡献 1 - 1/e，然后调用经典预言不等式再贡献一个因子 1/2。相乘得到 (1/2)·(1 - 1/e)·(1/2) = (e-1)/(4e) ≈ 0.158。

这篇论文用一个对象取代了这条链。对每个箱子，把它的价值截断在保留值处，即 y_i = min{v_i, r_i}，并对阈值 t 定义保留值截断阈值剩余 w_i(t) = E[(y_i - t)^+]。对一个截止时间可行的集合 S，基准为 B_t(S) = t + S 中所有 i 的 w_i(t) 之和。该剩余衡量的是，在期望意义上，一个箱子的截断奖励超过阈值多少。

两条性质构成了整个论证。第一，对每个遵守开箱截止时间的自适应策略和每个阈值 t，期望效用至多为 t + W(t)，其中 W(t) 是所有截止时间可行集合上剩余总和的最大值。证明利用了这样一个事实：打开一个箱子的决定是在看到其价值之前做出的，因此超过保留值的期望超出量恰好与开箱成本抵消。第二，在一个选好的集合上运行简单阈值策略，至少能获得 t 与 W(t) 中的较小者。选择使两者相等的 t，就得到效用至少为 t，而 OPT 至多为 2t，于是得到因子 1/2。

中间损失之所以消失，是因为截止时间结构在剩余基准内部得到处理，而不是通过若干独立的松弛。论文把这种分析称为白箱阈值剩余分析，以区别于此前的黑箱组合。

在多项式时间内精确选出可行集合

该基准要求在截止时间可行集合上最大化总剩余，因此论文既需要可行性检验，也需要一个优化过程。把集合按截止时间非降序排列。该集合可行，当且仅当其中第 j 个箱子的截止时间至少为 j，因为截止时间最小的 j 个箱子必须在前 d_ij 轮内占据不同的轮次。

于是，在可行集合上最大化总权重就变成一个具有 O(n^2) 次状态转移的动态规划。把箱子按截止时间排序后，状态记录从前 i 个箱子中恰好选 j 个所能达到的最佳权重，只有当 d_i ≥ j 时，箱子 i 才能作为第 j 个被选中的箱子。用权重 w_i(t) 运行该动态规划，就能计算 W(t)，并为每个固定阈值返回一个最大化集合。

寻找平衡阈值同样是构造性的。由于 W 是 n-Lipschitz 的，且平衡点至少为 W(0)/(n+1)，在 [0, W(0)] 上做二分搜索，在精确计算 W 的前提下，需要 O(log(n/ε)) 次迭代即可得到 1/2 - ε 的比值。对于显式表示的有限支撑分布，精确阈值可以写成一个具有 O(M + n^2) 个变量和约束的线性规划，其中 M 是支撑点总数，并且对有理数输入可以在多项式时间内精确求解。因此，精确的 1/2 保证附带一个高效过程，而不只是一个存在性断言。

1/2 对立即承诺是紧的

1/2 不是分析产生的假象。论文证明，没有任何立即承诺策略——即使是完全自适应的策略——能在面对采用“延迟到停止”承诺的最佳部分自适应策略时超过 1/2。构造方式模拟了预言不等式的经典紧例：两个零成本箱子，第一个截止时间为 1、价值为 1，第二个截止时间为 2、以概率 ε 取值 1/ε，否则取 0。

采用延迟承诺的部分自适应策略会打开两个箱子并取较大值，期望获得 2 - ε。任何立即承诺策略至多获得 1：先打开箱子 2 会妨碍之后打开箱子 1，而先打开箱子 1 则必须在接受 1 和继续打开一个期望同样为 1 的箱子之间做选择。比值至多为 1/(2 - ε)，它趋于 1/2。

这把保证锁定在承诺规则上，而不是算法的简单性上。在立即承诺这一类策略中，1/2 就是上限；要改进它，必须放宽已打开箱子保持可用的时长。

部分自适应本身带来 0.778 的代价

另一项结果单独刻画了固定开箱顺序的代价。论文构造了一个实例，其中两类箱子各有至少 k 个，所有箱子的截止时间都是 k，开箱成本为零，因此最多能打开 k 个箱子。类型 1 箱子以概率 p_1 = 1/(λ_1 k) 取值 1；类型 2 箱子以概率 p_2 = 1/(λ_2 k^2) 取值 k。

部分自适应策略事先固定顺序，并且由于开箱免费，最优做法是恰好打开 k 个箱子。用 α 表示类型 1 箱子所占比例，其极限效用为 1 - e^{-α/λ_1} + (1-α)/λ_2，在 α* = λ_1 ln(λ_2/λ_1) 处取最大。完全自适应策略则不同：它一直打开类型 1 箱子直到看到 1，然后把剩余轮次用于类型 2 箱子，从而利用第一次成功出现的时机。

取 λ_1 = 0.513、λ_2 = 1.541，两个极限效用之比被界定在 0.77792 以下，因此对所有足够大的有限 k，部分自适应最优严格小于完全自适应最优的 0.778 倍。任何部分自适应策略，即使计算能力无限，也无法保证超过 0.778。这与经典问题形成分离：在经典问题中，Weitzman 的部分自适应规则已经对完全自适应策略最优；而截止时间使部分自适应严格变弱。

尚未解决的问题在哪里

这两个界回答的是不同问题，不应合并成一个数字。1/2 对立即承诺策略相对于“延迟到停止”基准是紧的。0.778 是部分自适应策略在“延迟到停止”承诺下的上限，而这一承诺规则比算法所用的规则更宽松。两个界都没有确定使用“延迟到截止时间”承诺的高效算法所能达到的最佳比值；这种承诺规则让已打开的箱子在其截止时间之前保持可选，使策略能够收集更多观察，同时保留此前的选项。本文算法和 Berger 等人的算法都没有利用这种灵活性。

另一个开放方向是开箱顺序上的完全自适应。分离结果表明，截止时间使部分自适应严格弱于完全自适应，这与经典情形不同，因此自然会问：在共同的延迟承诺规则下，高效完全自适应算法能否超过 1/2。

实际解读也遵循同样的区分。当评估必须提前安排，且每次评估都迫使做出接受或拒绝的决定时，论文的部分自适应、立即承诺策略相对于最宽松的基准提供 1/2 保证，并且该类策略中没有能做得更好的。当应用可以让已打开的选项一直保留到其截止时间时，1/2 的上限不再适用，而延迟承诺能带来多少收益仍是一个开放问题。

本文引用的文献