向下封闭预言家与秘书问题的紧确界
Tight Bounds for Downward-Closed Prophet and Secretary Problems
Hanrui Zhang
AI 速读 基于摘要
该论文在任意向下封闭可行性约束下，为不同到达顺序和分布假设的在线选择问题建立了渐近紧确的竞争比界。
cs.GT · cs.DS
查看原文摘要
We study online selection problems subject to arbitrary downward-closed feasibility constraints, under different arrival orders, with different distributional assumptions. We establish the following bounds: (1) $Θ(\log^2 n / \log \log n)$ for the standard (adversarial-order) prophet problem, (2) $Ω(\log n)$ for the (Bayesian, random-order) prophet secretary problem, and by extension, for the standard (prior-free, random-order) secretary problem, and (3) $O(\log n / \log \log n)$ for the free-order prophet problem. Together with complementary bounds established in prior work, these results pin down the asymptotically tight competitive ratios for all these variants of prophet and secretary problems subject to downward-closed constraints. Our results refine and reinforce the big-decisions-first principle by Rubinstein and Singla [2026], establishing a superconstant separation between the random-order and free-order models.