Residual Prophet Inequalities

Information Systems and Operations Management

Speaker: Dana Maria Pizarro (TBS Education)

Room Bernard Ramanantsoa

Abstract:

In the classic prophet inequality, a gambler aims to select a high value from a sequence of random variables. But what if the top k choices are already gone? We introduce the Residual Prophet Inequality, a novel variant where the k highest values are removed  and the remaining n-k values are streamed sequentially. We study two information models depending on whether the gambler can identify the underlying distributions online (FI model) or not (NI model). Our main result is a tight, randomized algorithm for the FI model that achieves a competitive ratio of 1/(k+2). For the NI model, we provide an alternative algorithm with a 1/(2k + 2) guarantee.

Bio:

Dana Maria Pizarro is an Assistant Professor in the Department of Information, Operations and Management Sciences at TBS Education and an Associate Faculty member at Toulouse School of Economics. Her research interests include online algorithms, combinatorial optimization, prophet inequalities, and game theory, with a particular focus on online decision-making under competition and limited information.