Uncertainty and Probability Secretary Problem

Ambiguous Secretary Problem

Reduction to a Monotone Problem

Xn=YnminP P[Yn+1= 0,...,YN= 0]

=Yn

∏N

k=n+1

(1−bk)

payoffs a linear inYnand monotone inBn=

∏N

k=n+1(1−bk)

the worst–case measure assigns probabilityanto{Yn= 1}