Tightness without Counterexamples: A New Approach and New Results for Prophet Inequalities

A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: given a sequence of random variables X1, ..., Xn drawn independently from a distribution F, the goal is to ...

In this paper, we introduce an over-time variant of the well-known prophet inequality with i.i.d. random variables. Instead of stopping with one realized value at some point in the process, we decide for each step how long we select the value. Then we ...

We introduce a new decomposition technique for random variables that maps a generic instance of the prophet inequalities problem to a new instance where all but a constant number of variables have a tractable structure that we refer to as (ε, δ)-...