Prophet inequality with recourse

Prophet inequalities compare the expected performance of a stopping rule to a "prophet" who has complete knowledge of the future. The classical prophet inequality states that for a sequence of nonnegative random variables $X_1,\dots,X_n$ with known distributions, there is a stopping rule which recovers at least 1/2 of the expected maximum. We consider a setting where decisions are not irrevocable, and a previously selected random variable $X_i$ can be discarded at a cost of $\beta X_i$, for some parameter $\beta>0$. We determine the optimal factor for $\beta>1$ to be $(1+\beta)/(1+2\beta)$, via combinatorial optimization techniques involving flows and cuts. The problem is still open for $\beta<1$ and we give some partial results in this regime.

This is based on joint work with F. Ekbatani, R. Niazadeh and P. Nuti.