PGMO Lectures: Jose Correa, Prophet Inequalities

We have the pleasure to advertise the PGMO lecture of

José Correa, Universidad de Chile


Prophet Inequalities

which will take place at ENSAE Paris – IP Paris, Palaiseau, 

on April 11 and 13, 2023

PGMO lectures provide advanced synthetic courses on topics of current

interest. They are dedicated to academic and industrial researchers,

doctoral students, and also to master 2 students.

The abstract can be found below.

Registration is free of charge, but mandatory, via the following web site:

PGMO (Gaspard Monge Program for Optimization, Operations Research

and their Interactions with Data Sciences) is a program

of Fondation Mathématique Jacques Hadamard, supported

by Électricité de France,

This lecture is organizing jointly by ENSAE, PGMO and Master of Optimization

of Université Paris Saclay, see

The organizers

V. Perchet, ENSAE

S. Gaubert, INRIA and Ecole polytechnique

Q. Mérigot, Université Paris-Saclay

J.-C. Pesquet, CentraleSupelec

W. Van Ackooij, EDF

S. Elloumi, ENSTA

S.-M. Grad, ENSTA

Contacts: for scientific questions, and for practical questions.



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.

Location : ENSAE (Amphithéâtre 250)

Schedule :

Tuesday April 11, 9h30–12h00 and 15h15-17h45

Thursday April 13, 9h30–12h00 and 14h00–16h30

More information:

Vianney Perchet