1/e-law of best choice

Statement

The essence of the model is based on the idea that life is sequential and that real-world problems pose themselves in real time. Also, it is easier to estimate times in which specific events (arrivals of applicants) should occur more frequently (if they do) than to estimate the distribution of the number of specific events which will occur. This idea led to the following approach, the so-called unified approach (1984):

The model is defined as follows: An applicant must be selected on some time interval $[0,T]$ from an unknown number $N$ of rankable applicants. The goal is to maximize the probability of selecting only the best under the hypothesis that all arrival orders of different ranks are equally likely. Suppose that all applicants have the same, but independent to each other, arrival time density $f$ on $[0,T]$ and let $F$ denote the corresponding arrival time distribution function, that is

$F(t) = \int_{0}^{t} f(s)ds$, $\, 0\le t\le T$.

Let $\tau$ be such that $F(\tau)=1/e.$ Consider the strategy to wait and observe all applicants up to time $\tau$ and then to select, if possible, the first candidate after time $\tau$ which is better than all preceding ones. Then this strategy, called 1/e-strategy, has the following properties:

The 1/e-strategy

(i) yields for all $N$ a success probability of at least 1/e,

(ii) is a minimax-optimal strategy for the selector who does not know $N$,

(iii) selects, if there is at least one applicant, none at all with probability exactly 1/e.

The 1/e-law, proved in 1984 by F. Thomas Bruss, came as a surprise. The reason was that a value of about 1/e had been considered before as being out of reach in a model for unknown $N$, whereas this value 1/e was now achieved as a lower bound for the success probability, and this in a model with arguably much weaker hypotheses (see e.g. Math. Reviews 85:m).

However, there are many other strategies that achieve (i) and (ii) and, moreover, perform strictly better than the 1/e-strategy simultaneously for all $N$>2. A simple example is the strategy which selects (if possible) the first relatively best candidate after time $\tau$ provided that at least one applicant arrived before this time, and otherwise selects (if possible) the second relatively best candidate after time $\tau$.

The 1/e-law is sometimes confused with the solution for the classical secretary problem described above because of the similar role of the number 1/e. However, in the 1/e-law, this role is more general. The result is also stronger, since it holds for an unknown number of applicants and since the model based on an arrival time distribution F is more tractable for applications.