静5前沿讲座 | Residual Prophet Inequalities

The classic prophet inequality states that, when faced with a finite sequence of non-negative independent random variables, a gambler who knows their distribution and 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 one. We introduce a variant of this problem, called residual prophet inequality (RPI). Here, again we consider a finite sequence of n non-negative independent random variables with known distributions, and a known integer 0≤k≤n−1. Before the gambler observes the sequence, the top k values are removed, whereas the remaining n−k values are streamed sequentially to the gambler. For example, one can assume that the top k values have already been allocated to a higher-priority agent. Upon observing a value, the gambler must decide irrevocably whether to accept or reject it, without the possibility of revisiting past values. We study two variants of RPI, according to whether the gambler learns online of the identity of the variable that he sees (FI model) or not (NI model). Our main result is a randomized algorithm in the FI model with competitive ratio of at least 1/(k+2), which we show is tight. Our algorithm is data-driven and requires access only to the k+1 largest values of a single sample from the n input distributions. In the NI model, we provide a similar algorithm that guarantees a competitive ratio of 1/(2k+2). We further analyze independent and identically distributed instances when k=1. We build a single-threshold algorithm with a competitive ratio of at least 0.4901, and show that no single-threshold strategy can get a competitive ratio greater than 0.5464. Joint work with Sebastian Perez-Salazar, Dana Pizarro, Bruno Ziliotto.

José Correa is a full professor in the Department of Industrial Engineering and a principal researcher in the Center for Mathematical Modeling, both at Universidad de Chile. Jose obtained a mathematical engineering degree from Universidad de Chile in 1999 and a Ph.D. in Operations Research from MIT in 2004. His research, focusing on the interplay between economics and computation, has received numerous awards, including an ACM SIGecom best paper award, an INFORMS Transportation Science and Logistics best paper award, a Tucker prize finalist, and research awards from Amazon and Google. Jose serves and has served on the editorial board of some of the leading journals of his field: Mathematical Programming B, Mathematics of Operations Research (as Game Theory Area Editor), and Operations Research (as Transportation Area Editor), and he often sits on the program committee of international computer science conferences. Currently, Jose serves as Vice President of Information Technology at the University of Chile.