Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
New research resolves a quadratic performance gap in three classic problems of decision-making under uncertainty.
Computer scientists Aviad Rubinstein and Sahil Singla have published a landmark paper, 'Secretary, Prophet, and Stochastic Probing via Big-Decisions-First,' accepted at the prestigious STOC 2026 conference. The work tackles three foundational problems in algorithmic decision-making under uncertainty: the Secretary Problem (hiring the best candidate from a sequence), Prophet Inequality (optimal stopping with known distributions), and Stochastic Probing (selecting elements with random values under constraints). For decades, a significant performance gap existed. When elements had binary values, these problems had a tight Θ̃(log n)-factor approximation guarantee. However, for general (non-binary) values, the best known algorithms suffered an extra log n factor, creating a quadratic gap of Θ̃(log n) versus Θ̃(log² n).
Rubinstein and Singla's research definitively closes this gap. They prove Θ̃(log² n)-hardness results for two of the problems, establishing that no algorithm can do significantly better. For the third, they provide a matching O(log n)-approximation algorithm. The unifying breakthrough is the 'Big-Decisions-First' principle: under uncertainty, algorithms achieve near-optimal performance by resolving decisions with the largest potential value (or stakes) as early as possible. This core insight, applied across different technical settings, provides a new lens for designing robust online and stochastic algorithms. The resolution of this quadratic gap represents a major theoretical advance in understanding the fundamental limits of optimization when information is revealed sequentially or probabilistically.
- Resolves a quadratic Θ̃(log n) vs. Θ̃(log² n) performance gap that persisted for general values in three classic algorithmic problems.
- Introduces the 'Big-Decisions-First' principle: optimal strategies under uncertainty prioritize high-stakes decisions early.
- Provides new O(log n)-approximation algorithms and matching Θ̃(log² n) hardness proofs, accepted at the top-tier STOC 2026 conference.
Why It Matters
This theoretical advance provides a fundamental principle for designing better algorithms in real-world scenarios like online hiring, investment, and resource allocation under uncertainty.