Title: Prophet Inequality with Recourse
Abstract: 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,...,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. Joint work with F. Ekbatani, R. Niazadeh, and P. Nuti.
Bio: Jan Vondrak obtained a PhD from MIT in 2005, and also from his alma mater, Charles University in Prague, in 2007. He spent some time as a postdoctoral researcher at Microsoft Research and Princeton University, and between 2009-15 he was a research staff member in the IBM Almaden research lab. Since 2016, he has been a faculty member in the Stanford Department of Mathematics.
