April Tuesday 11^th and Thursday 13^th, 2023

"Prophet Inequalities"

A prophet inequality refers to the existence of an online algorithm for a stochastic optimization problem whose outcome is, in expectation, close to that of a prophet, who can see the input in advance. The study of prophet inequalities has been very active since the classic work of Krengel and Sucheston, who established the single-item case. They proved that a gambler facing a finite sequence of non-negative independent random variables and who is allowed to stop the sequence at any time, can obtain, in expectation, at least half as much reward as a prophet who knows the values of each random variable and can choose the largest. Following this classic theorem from the 70s, many results have been obtained for several related optimal stopping problems. Moreover, the recently uncovered connection between prophet inequalities and posted price mechanisms, has given the area a new surge. In this short course, we will cover not only some of the classic results in prophet inequalities but also new approaches and variants of the problem. These include data-driven approaches to prophet inequalities, combinatorial prophet inequalities, and online combinatorial auctions.

--> ENSAE (Amphithéâtre 250)

Schedule : Tuesday 11th,  09:30 - 12:00 and 15:15 - 17:45 / Thursday 13^th,  09:30 - 12:00 and 14:00 - 16:30

Slide-1 Slide-2 Slide-3 Slide-4

Information and registration