Prophet Inequalities with Moment Knowledge.

Abstract: 

In this talk, we study a variant of the prophet inequality with limited information, where the decision maker only has access to the first k moments of each random variable, rather than their full distributions. Our main result is that, for any k, even one dependent on n, the best possible competitive ratio is Θ(1/ log(n)), which we show can already be achieved with knowledge of the first moment only.

Our result implies that the moments are not very informative in this setting, so extra information is needed if one aims for better guarantees. To showcase the impact of extra information, we investigate the case of monotone-hazard-rate (MHR) distributions, showing that a guarantee of Ω( 1 / log(log(n)))$ is possible already with a single moment. In addition, we show that under a condition on the growth rate of the moments, constant-competitive guarantees are possible with k = Ω(log(n))$ moments.

This work provides an answer to a prior open question about the prophet inequality with limited information, and also presents a framework for online selection problems under constraints of moment knowledge. This talk is based on joint work with José Correa (U. de Chile), Andrés Cristi (EPFL), Victor Verdugo (PUC Chile) and Jiechen Zhang (EPFL).

Posted on Oct 14, 2025 in ACGO, Seminars