Ratio Prophet Inequalities when the Mortal has Several Choices

David Assaf, Larry Goldstein & Ester Samuel-Cahn

Let X_i be non-negative, independent random variables with finite expectation, and X*_n=max{X_1,...,X_n}. The value EX*_n is what can be obtained by a "prophet". A "mortal" on the other hand, may use k>=1 stopping rules t_1,...,t_k, yielding a return of E[max_i=1,...,k X_t_i]. For n>=k the optimal return is V^n_k(X_1,...,X_n)=supE[max_i=1,...,k X_t_i] where the supremum is over all stopping rules t_1,...t_k such that P(t_i<=n)=1. We show that for a sequence of constants g_k which can be evaluated recursively, the inequality EX*_n=k; g_1=2, g_2=1+e^-1=1.3678..., g_3=1+e^1-e=1.1793..., g_4=1.0979... and g_5=1.0567...Similar results hold for infinite sequences X_1,X_2,... Since with five choices the mortal is thus guaranteed over 94% of the prophet's value, more than five choices may not be practical.

February, 2001
Published in: 
Annals of Applied Probability 12 (2002) 972-984.