When Should You Stop and what do You Get? Some Secretary Problems

A version of a secretary problem is considered: Let X_j, j = 1,...,n be i.i.d. random variables. Like in the classical secretary problem the optimal stopper only observes Y_j = 1, if X_j is a (relative) record, and Y_j = 0, otherwise. The actual X_j-values are not revealed. The goal is to maximize the expected X-value at which one stops. We describe the structure of the optimal stopping rule, its asymptotic properties and the asymptotic expected reward. Three different families of distributions of X are considered, belonging to the three different domains of attraction of the maximum. It is shown that both the time of stopping, as well as the expected reward are strongly distribution dependent. The last section discusses an ‘inverse’ of ‘Robbins’ Problem’.