The secretary game

Twenty candidates arrive in random order. For each one, press Hire or Pass. You are only told how the current candidate ranks against the ones you have already seen, never their actual score. Pass, and that candidate's score is revealed on the strip, but they are gone for good. Hire, and the game ends. You win only if you hired the best of all twenty. The dashed orange line on the strip marks the 37% rule: look at the first 7 without hiring, then take the first one who beats everyone so far. Play a few rounds, then press Simulate to test every possible cutoff 10 000 times.

Mission. Before you simulate, predict: if you look at half the candidates before you start choosing, is your chance of ending with the best higher or lower than with the 37% cutoff? And what is the chance if you look at none and hire the first person?

Answer

Lower. Looking at 10 of 20 gives about 36%, against 38% for the best cutoff of 7; the curve is flat near its peak, so the penalty is small, but it grows quickly past half. Hiring the first candidate blind wins 1 in 20 = 5%. The simulation shows the whole curve; the formula is P(r) = (r/n)(1/r + 1/(r + 1) + … + 1/(n − 1)), which peaks at r ≈ n/e with value ≈ 1/e ≈ 0.368 for large n. Extension: switch the simulation to 100 candidates. The best cutoff moves to 37, and the peak chance barely changes. Why does more competition not hurt?

Press Simulate. For every cutoff r, the computer looks at the first r candidates, then hires the first one who beats all of them (or the last one if nobody does), and records whether that was the best.

What's going on

You cannot go back, so the only sensible plan is look, then leap: reject the first r candidates no matter what, then hire the first one who is better than everyone before. Reject too few and you leap at someone mediocre; reject too many and the best has probably already walked past. The strategy with cutoff r wins exactly when the best candidate comes after position r and the best of the candidates before them sits inside the first r. Adding up over where the best can land gives P(r) = (r/n) Σk=rn−1 1/k.

That sum is close to (r/n) ln(n/r). Write x = r/n and you are maximising −x ln x, which happens at x = 1/e ≈ 0.37, where the value is also 1/e. So look at 37% of the field, then leap, and you get the single best candidate about 37% of the time, whether there are 20 candidates or 20 million. The orange line on the chart is the exact formula; the bars are what actually happened in 10 000 random games, with the usual sampling wobble.

The assumptions do the work: candidates in uniformly random order, no recall, no ties, and the goal of the very best rather than someone good. Change the goal to "someone in the top 10%" and the right cutoff drops sharply. Real decisions about flats, jobs and parking spaces are usually closer to that version.

Sheet: When to stop looking.