Best Candidate

Solution

You cannot see each candidate’s absolute quality, only whether they are the best so far. That means the only sensible kind of strategy is a threshold rule: \[ \text{reject the first } r \text{ candidates automatically, then accept the first later candidate who is ranked } 1 \text{ among all seen so far.} \] The reason this is the right structure is intuitive. Early on, you are mostly gathering information about what “good” looks like. Later on, once you have a benchmark, the first candidate who beats that benchmark is worth taking. So the question becomes: what value of \(r\) should you choose? If the best overall candidate appears in position \(k\), then under this strategy you succeed exactly when \[ k > r \] and the best among the first \(k-1\) candidates appeared during the initial sample of size \(r\). Since among the first \(k-1\) candidates, each is equally likely to be the best of that prefix, that probability is \[ \frac{r}{k-1}. \] Also, the best overall candidate is equally likely to be in any of the \(n\) positions, so \[ P(\text{success}) = \sum_{k=r+1}^{n} \frac{1}{n}\cdot \frac{r}{k-1} = \frac{r}{n}\sum_{k=r+1}^{n}\frac{1}{k-1}. \] \[ P(\text{success}) = \frac{r}{n}\sum_{j=r}^{n-1}\frac{1}{j}. \] For large \(n\), this is well approximated by \[ P(\text{success}) \approx \frac{r}{n}\ln\!\left(\frac{n}{r}\right). \] Let \[ x=\frac{r}{n}. \] Then we want to maximise \[ f(x)=x\ln\!\left(\frac{1}{x}\right). \] Differentiating, \[ f'(x)=\ln\!\left(\frac{1}{x}\right)-1. \] \[ \ln\!\left(\frac{1}{x}\right)=1 \quad\Rightarrow\quad \frac{1}{x}=e \quad\Rightarrow\quad x=\frac{1}{e}. \] So the optimal cutoff is \[ r \approx \frac{n}{e}. \] Since \[ \frac{1}{e}\approx 0.368, \] the practical strategy is: \[ \text{reject about the first } 36.8\% \text{ of candidates, then hire the first one who is best so far.} \] For example, if \(n=100\), you would reject the first \(37\) candidates, then accept the first later candidate who is ranked above everyone seen previously.