Secretary, Prophet, and Stochastic Probing via Big-Decisions-First

We revisit three fundamental problems in algorithms under uncertainty: the Secretary Problem, Prophet Inequality, and Stochastic Probing, each subject to general downward-closed constraints. When elements have binary values, all three problems admit a tight Θ(log n)-factor approximation guarantee. For general (non-binary) values, however, the best known algorithms lose an additional log n factor when discretizing to binary values, leaving a quadratic gap of Θ(log n) vs. Θ(log 2 n).

We resolve this quadratic gap for all three problems, showing Ω(log 2 n)-hardness for two of them and an O(log n)-approximation algorithm for the third. While the technical details differ across settings, and between algorithmic and hardness proofs, all our results stem from a single core observation, which we call the Big-Decisions-First Principle: Under uncertainty, it is better to resolve high-stakes (large-value) decisions early.