Two Best Candidates

Solution

Let the candidates be observed in order \(1,2,\dots,n\), with all global ranks distinct. You only ever see a candidate’s relative rank among those seen so far. To end up with exactly the best and second-best overall, two things must happen: \[ \text{the first hire must be the earlier of the top two overall,} \] and then \[ \text{the second hire must be the later of the top two overall.} \] That immediately tells us something important. A first hire can only ever be made when the candidate is best-so-far. If you hire someone who is not best-so-far, then some better candidate has already appeared and been rejected, so you can no longer possibly get both of the top two overall. So the first hire must be chosen from relative-rank \(1\) candidates only. After the first hire, suppose it happened at position \(m\). If that first hire really is one of the top two overall, then the other person you still need is simply the best candidate among the remaining \(n-m\) candidates. That reduces the second stage to the ordinary secretary problem on the suffix. Why? Because from that point on, a future candidate is the best among the remaining suffix seen so far exactly when their global relative rank is at most \(2\): they either beat your first hire, or are second only to it. So after the first hire, the optimal continuation is: reject a certain number of the remaining candidates, then take the next candidate whose global relative rank is \(1\) or \(2\). Equivalently: skip a threshold in the remaining suffix, then take the next record within that suffix. So the optimal overall policy is: \[ \text{reject the first } a_n \text{ candidates;} \] then \[ \text{hire the first candidate thereafter with relative rank }1; \] if that first hire occurs with \(t=n-m\) candidates still to come, then on the remaining \(t\) candidates use the usual secretary rule: \[ \text{skip the next } r_t \text{ remaining candidates, then hire the next one with relative rank } \le 2. \] Here \(r_t\) is the classical optimal secretary cutoff for choosing the best from \(t\) candidates, so asymptotically \[ r_t \sim \frac{t}{e}. \] That is the structure of the optimal strategy. Now let us write its success probability. Let \[ q_t \] be the optimal success probability in the ordinary secretary problem with \(t\) candidates left, so \[ q_t = \max_{0\le r < t} \frac{r}{t}\sum_{j=r+1}^{t}\frac{1}{j-1}. \] This is the probability of choosing the best from \(t\) candidates by the optimal one-choice rule. If we use first-stage cutoff \(a\), then the probability of success is \[ P_n(a) = \frac{2a}{n(n-1)} \sum_{m=a+1}^{n-1} \frac{n-m}{m-1}\, q_{\,n-m}. \] Here is what each factor means. The term \[ \frac{2(n-m)}{n(n-1)} \] is the probability that the earlier of the two best overall candidates occurs at position \(m\). The term \[ \frac{a}{m-1} \] is the probability that this candidate is the first record after the initial sample of size \(a\). And once that happens, there are \(n-m\) candidates left, and the optimal chance of getting the other one is exactly \[ q_{n-m}. \] So the optimal first cutoff is \[ a_n=\arg\max_a P_n(a). \] Asymptotically, since \[ q_t \to \frac{1}{e}, \] we get \[ P_n(a) \approx \frac{2}{e}\, x \int_x^1 \frac{1-u}{u}\,du, \qquad x=\frac{a}{n}. \] Now \[ \int_x^1 \frac{1-u}{u}\,du = -\ln x -1 + x, \] so asymptotically we maximize \[ f(x)=\frac{2}{e}\,x\bigl(-\ln x-1+x\bigr). \] Differentiating gives \[ f'(x)\propto -\ln x -2 + 2x, \] so the optimal \(x\) solves \[ -\ln x = 2(1-x). \] This gives \[ x \approx 0.20319. \] So for large \(n\), the first-stage rule is: \[ \text{skip about }0.203\,n\text{ candidates, then hire the first record.} \] After that, if \(t\) candidates remain, skip about \[ \frac{t}{e} \] of those remaining, and then hire the next candidate whose relative rank is at most \(2\). So the maximizing strategy is: \[ \text{First stage: skip }a_n\approx 0.203\,n,\ \text{then take the first best-so-far candidate.} \] \[ \text{Second stage: with }t\text{ candidates left, skip about }t/e,\ \text{then take the first candidate of relative rank }1\text{ or }2. \]