The secretary problem: Minimizing the expected rank with i.i.d. random variables

The secretary problem: Minimizing the expected rank with i.i.d. random variables

0.00 Avg rating0 Votes
Article ID: iaor19971178
Country: United Kingdom
Volume: 28
Issue: 3
Start Page Number: 828
End Page Number: 852
Publication Date: Sep 1996
Journal: Advances in Applied Probability
Authors: ,
Keywords: programming: dynamic
Abstract:

n candidates, represented by n i.i.d. continuous random varaibles X1,...,Xn with known distribution arrive sequentially, and one of them must be chosen, using a non-anticipating stopping rule. The objective is to minimize the expected rank (among the ranks of X1,...,Xn) of the candidate chosen, where the best candidate, i.e. the one with smallest X-value, has rank one, etc. Let the value of the optimal rule be Vn, and limVn=V. The authors prove that V>1.85. Limiting consideration to the class of threshold rules of the form tn=min{k:Xk•ak} for some constants ak, let Wn be the value of the expected rank for the optimal threshold rule, and limWn=W. The authors show 2.295<W<2.327.

Reviews

Required fields are marked *. Your email address will not be published.