Splitting Guarantees for Prophet Inequalities via Nonlinear Systems

Understand

The prophet inequality is one of the cornerstone problems in optimal stopping theory and has become a crucial tool for designing sequential algorithms in Bayesian settings.

• In the i.i.d.
• $k$-selection prophet inequality problem, we sequentially observe $n$ non-negative random values sampled from a known distribution.
• Each time, a decision is made to accept or reject the value, and under the constraint of accepting at most $k$.