Prophet Inequalities via Linear Programming

Halil I. Bayrak, Mustafa Ç. Pınar, Rakesh Vohra

Prophet inequalities bound the expected reward that can be obtained in a stopping problem by the optimal reward of its corresponding off-line version. We propose a systematic techn…