Prophet Secretary Through Blind Strategies

Abstract: In the classic prophet inequality, a problem in optimal stopping theory, samples from independent random variables arrive online. A gambler that knows the distributions, but cannot see the future, must decide at each point in time whether to stop and pick the current sample or to continue and lose that sample forever. The goal of the gambler is to maximize the expected value of what she picks and the performance measure is the worst case ratio between the expected value the gambler gets and what a prophet, that sees all the realizations in advance, gets. We study when the samples arrive in a uniformly random order, deriving a way of analyzing multi-threshold strategies that basically sets a nonincreasing sequence of thresholds to be applied at different times. The gambler will thus stop the first time a sample surpasses the corresponding threshold. We consider a class of robust strategies that we call blind quantile strategies. These constitute a clever generalization of single threshold strategies. Our main result shows that these strategies can achieve a constant of 0.669 in the prophet secretary problem, done by a sharp analysis of the underlying stopping time distribution for the gambler’s strategy that is inspired by the theory of Schur-convex functions. We further prove that our family of blind strategies cannot lead to a constant better that 0.675. Finally we prove that no nonadaptive algorithm for the gambler can achieve a constant better than 0.732.

Date: Nov 28, 2018 at 14:30:00 h
Venue: Republica 701, Sala 33.
Speaker: Raimundo Saona
Affiliation: DIM, Universidad de Chile
Coordinator: Prof. José Verschae

Posted on Mar 12, 2019 in AGCO, Seminars