Contents
Prophet Inequalities originated in the field of Optimal Stopping Theory. The classic result of Krengel, Sucheston, and Garling showed that for any sequence of n independent random variables X_1, …, X_n there exists a stopping rule τ such that E[X_τ] ≥ 1/2 E[max_i X_i].
In 2007, Hajiaghayi, Kleinberg, and Sandholm introduced prophet inequalities to the field of Algorithmic Mechanism Design. They have since become an important tool because they naturally give posted-pricing mechanisms that are simple, efficient, and optimal. On the one hand, they help us understand the welfare that can be obtained by only posting prices in (combinatorial) settings of incomplete information. On the other hand, they have been used to obtain the first mechanisms with nearly-optimal revenue in several multi-dimensional settings.
Beyond mechanism design, prophet inequalities are an important direction in Theoretical Computer Science. They are particularly useful to understand online algorithms “beyond the worst-case”. For many basic online problems, e.g. selecting the maximum of n numbers, non-trivial algorithms are impossible in the traditional worst-case online model. Prophet inequalities can be viewed as bounding the competitive ratio of an online algorithm, when the online arrival is from some known product distribution.
In our tutorial we describe the various known prophet inequalities and the techniques used to obtain them. We highlight the applications of prophet inequalities in mechanism design and online algorithms, and mention several open-questions that will require new ideas from our community.