Abstract:
Prophet Inequalities originated in the field of Optimal Stopping Theory. 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 this work, we highlight the applications of prophet inequalities in mechanism design and online algorithms, and mention several open-questions that will require new ideas from the community.
Based on a tutorial by Michal Feldman, Thomas Kesselheim, and Sahil Singla from the ACM Conference on Economics and Computation: http://www.thomas-kesselheim.de/tutorial-prophet-inequalities/