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.

Slides

Reading List

Please check out our reading list, giving a brief overview of all papers covered in the tutorial as well as many other references.

About Us

Michal Feldman is a professor of computer science in the Blavatnik School of Computer Science at Tel Aviv University and a visiting scholar at Microsoft Research (MSR) Herzliya.

Thomas Kesselheim is a professor in the Institute of Computer Science at University of Bonn.

Sahil Singla is a research instructor (postdoc) jointly between the Department of Computer Science at Princeton University and the School of Mathematics at Institute for Advanced Study.