Optimal Stopping and the 37% Rule

You are hiring from $n = 100$ candidates who arrive in random order. After each interview you must hire or reject on the spot, and a rejected candidate never comes back. You can rank everyone you have seen so far against each other, but you have no outside scale for how good the pool is. You win only if you hire the single best of the 100.

Hiring the first person wins with probability $1/100$. Waiting until the end is no better, since the last candidate is the best with probability $1/100$ too. The good strategies sit in between. A look-then-leap rule with cutoff $r$ rejects the first $r$ candidates no matter what, then hires the first one who beats everyone seen so far.

The choice of $r$ moves the answer a lot. With $r = 10$ you land the best about 23.5% of the time, with $r = 50$ about 34.9%, and with $r = 37$ about 37.1%, which is the most any rule can achieve for $n = 100$. That is 37 times better than guessing, from a rule that only ever asks "is this one better than all the others I have seen?"