![statistics image](/sites/default/files/styles/max_325x325/public/2022-03/ev-stats_0.png?itok=w6pZu2aD)
Prophet inequality with recourse
Sequoia Hall Room 200
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.