Hiring the Best Candidate

  • Hard
  • Game strategy puzzles
  • Tests: Trading information against opportunity

The puzzle

You must hire one person from 100 applicants. You interview them one at a time in random order, and after each interview you can rank that candidate against everyone seen so far - but you must accept or reject on the spot, and a rejected candidate is gone for good.

What strategy maximises the chance of hiring the very best applicant, and what is that chance?

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Rejecting everybody for a while costs you nothing except the chance that the best was among them - and buys you a benchmark.

Hint 2

Interview and reject the first k, then take the first candidate who beats all of them. Optimise over k.

Show the answer Hide the answer

Reject the first 37 candidates outright, then hire the first one who is better than all of those. The chance of getting the best applicant is about 37% - specifically 1/e.

How to get there

Fix a cutoff k: reject the first k, then accept the first candidate who beats every one of them. This succeeds when the best candidate is at some position i > k and the best of the first i-1 candidates lies within the first k - otherwise you would have stopped too early.

Summing those probabilities gives roughly (k/n) * ln(n/k) for large n. Maximising over k, the derivative vanishes at k/n = 1/e, and the success probability there is also 1/e = 0.3679.

So with 100 applicants, reject the first 37 and the chance of hiring the best is about 37%. Two things are counterintuitive: the answer does not shrink as n grows - it is 37% for a hundred applicants and for a million - and a third of the field is deliberately thrown away to buy a benchmark. Settling for a "good" rather than the "best" candidate allows a much higher success rate with a smaller cutoff.

The technique worth keeping

In optimal stopping, parameterise the strategy with a single cutoff, write the success probability as a function of it, and optimise. The tension is always the same: observing longer improves your judgement and reduces your remaining choices.