Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
This resolves a long-standing theoretical gap in algorithmic uncertainty for researchers, though it is incremental as it builds on prior binary-value results.
The paper tackled the quadratic gap in approximation guarantees for three fundamental problems in algorithms under uncertainty—Secretary Problem, Prophet Inequality, and Stochastic Probing—by showing $ ilde{\Omega}(\log^2 n)$-hardness for two and providing an $O(\log n)$-approximation algorithm for the third, based on the Big-Decisions-First Principle.
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 $\tildeÎ(\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 $\tildeÎ(\log n)$ vs. $\tildeÎ(\log^2 n)$. We resolve this quadratic gap for all three problems, showing $\tildeΩ(\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.