Look at 37%.
Then leap.

Play a round with ten candidates

Bar height shows where each candidate stands among those you have seen so far. The bars rescale as new people arrive. Dark bars were the best so far when they arrived.

Two things become obvious after a few rounds. Early on you have nothing to compare against. Later on, the good ones may already be gone. Any strategy has to trade those two risks against each other.

The best candidate is the last record. Your challenge is to guess which record is the last.

First: only records are worth hiring

Call a candidate a record if they beat everyone who came before them. Here is one full line-up with true heights shown. The dashed line is the bar each newcomer has to beat.

Anyone below the dashed line is already beaten. And the best overall is always the last record in the line-up. So the problem boils down to: a record is in front of you, and you must predict whether it is the last one.

Second: how likely is this record to be the last one?

Give each of the 20 positions one chip. A chip stands for a 1-in-20 chance that the overall best sits there. Now suppose you have interviewed k people and the latest one is a record.

If the overall best is anywhere among the k people you have seen, it has to be this record, because this record beats all of them. So the chips from all k seen positions pile onto the record. Each unseen position keeps its single chip.

So the rule is a cutoff

Slide k from left to right. An early record holds a short stack, and most of the chips sit on people you have not met yet. A late record holds nearly all of them. A record gets more believable the later it shows up, so a sensible rule ignores early records and accepts late ones: skip the first r candidates, then hire the first record that appears. The open question is how large r should be. (Step 6 comes back to why a single cutoff is the right form.)

You win if no record turns up between the cutoff and the best

Suppose you skip the first r candidates, and the best candidate overall, ★ (star), is at position k. There are two ways to lose.

1. ★ is in the skipped group. You passed on them before you started hiring.
2. ★ comes after the cutoff, but you never get that far. Some other record shows up first, between the cutoff and ★, and you hire that person.

If neither happens, the first record you meet after the cutoff is ★, and you win.

To see how often the second problem happens, take everyone you interview before ★ and pick out the strongest of them. Call that person ◆ (diamond). Where ◆ stands settles everything.

◆ (the strongest candidate you meet before ★) is equally likely to be in any of the k−1 positions before ★. You win when ◆ lands in one of the r skipped ones.

So you are safe if ◆ happens to be among the first r of the k−1 candidates you meet before reaching ★ at position k. Each of those k−1 positions is equally likely, so the chance is r out of k−1.

You do not know where ★ is, so average over every position

Step 3 gives your chance of winning if you know ★ is at position k. In a real round you do not know where ★ is. Rather, ★ is equally likely to be at each position, so your overall chance is the average of the Step 3 answers.

Here it is for ten candidates. Each bar is one possible position of ★, and its height is the Step 3 chance of winning in that case.

Written as a formula, the average is the sum of the bar heights divided by the number of bars. Call it P(r): your overall chance of hiring the best candidate when you skip the first r. Start with the average itself, then put in the Step 3 formula for each bar. The skipped positions add nothing, so the second sum starts just after the cutoff.

With many candidates the bars become a curve, and the average becomes x · ln(1/x)

Here are the same bars as Step 4, now with a slider for the number of candidates. As n grows the bars get thinner, and their tops trace out a smooth curve.

Now measure positions as fractions of the way through the line-up. As a fraction, the cutoff is at x = r/n, and ★ comes after a fraction t = (k−1)/n of the line-up. Divide the top and bottom of the bar height by n and it is written in those fractions:

The bar height x/t is the dashed curve, and the average becomes the area under that curve from the cutoff to the end.

Now plot that win probability against the cutoff, together with the two ways of losing. Every round ends in one of three ways, so the three bands always fill the box.

Flat tangent means zero derivative:

Hire at the moment a record is worth as much as the future

Suppose you are at fraction x of the way through, facing a record. You have two options, and Steps 2 and 5 already priced both.

Hire now. A record at x is the best with probability x (Step 2). Pass and take the next record. That is the cutoff rule started from here, which wins with probability −x ln x (Step 5).

The figure below plots both options against how far through the line-up you are. The horizontal axis is x, your position as a fraction from 0 (the start) to 1 (the end). The vertical axis is your chance of ending up with the best candidate.

• The straight crimson line is "hire now." It climbs steadily, because a record is more believable the later it appears.
• The black curve is "pass and take the next record." It is the same hump as in Step 5. Early on it is low, because the next record will probably turn up too soon to be the best. Near the end it drops to zero, because there may be no next record at all.
• Whichever is higher is the better choice at that point. In the teal region the curve is on top, so passing wins. In the amber region the line is on top, so hiring wins.
• The dot is where they cross. To its left you should pass on every record. To its right you should hire the first one you see.

If you have met decision analysis, this is a one-way sensitivity analysis. There are two strategies, hire now and pass. The payoff of each, your chance of getting the best candidate, is plotted against your position x. At every x the better strategy is the one whose line is higher, and the point where the lines cross is the threshold at which the best choice switches.

Early on, the future is worth more than any record in hand, so you keep looking. The lines cross where the two are equal:

The crossing point sits on the line y = x, so its height equals its position. That is why the fraction you skip and the chance you win are the same number.

Simulated hiring with 100 candidates

Each round shuffles 100 candidates and scores every possible cutoff on that same shuffle. Dots are observed win rates. The line is the exact sum from Step 4.

Assumptions

• You know n in advance, and the order is random.
• You learn only relative ranks. If you could see scores on a known scale, you could do better.
• Only the best counts as a win. If second best were nearly as good, the right cutoff would be earlier.
• No going back to someone you passed on.

For finite n the best cutoff is the whole number that maximizes the Step 4 sum. It is close to n/e: skip 3 of 10, 7 of 20, 37 of 100.

A compact proof

Here is the whole argument again without the pictures, with each claim stated exactly. There are candidates in uniformly random order. is the rule "pass on the first , then hire the first record," and is the probability that hires the best candidate.

1. Two facts about a random order

Let be the position of the best candidate. Every order is equally likely, so

Given , the candidates before the best are themselves in uniformly random order. Let be the position of the strongest of them. Then

2. When the rule wins

If , the best is passed over and the rule loses. If , the rule hires the best exactly when no record appears at positions . If , every candidate at those positions is beaten by the one at , so none is a record. If , the candidate at is a record at one of those positions. So the rule wins exactly when :

3. The exact win probability

Sum over the position of the best. For ,

With no skipping, the rule hires the first candidate, so .

4. The best cutoff for a finite line-up

Compare neighboring cutoffs. For ,

The bracket shrinks as grows, so rises and then falls. The best cutoff is the first at which the bracket is no longer positive:

For : , while . So , and .

5. Large line-ups

Let with , where . The sum in step 3 is a Riemann sum for :

Therefore

Differentiate twice:

The curve is concave with a single stationary point, which is its maximum:

The same approximation applied to the condition in step 4 gives , that is, .

6. Why no other strategy does better

A strategy sees only relative ranks. Hiring a candidate who is not a record never wins, so the only real decision comes when a record appears at some position . The relative order of the first candidates says nothing about whether the best overall is among them, so whatever has been seen,

That is the value of hiring. Let be the best win probability any strategy can achieve after passing on the first candidates. Two properties of settle the question.

• cannot increase with . Anything you can do after passes you can also do after passes, by passing once more.
• Later on, . Work backward from the end. Suppose hiring is optimal at every record after position . Then the best continuation after passing candidates is "hire the next record," which is , so . At a record at position , hiring is then optimal when
  which by step 4 holds for every . So hiring is optimal at every record after position , and for all .

Now take a record at an early position . Because is the first cutoff satisfying the condition in step 4, the cutoff fails it, which says . Hence

Hiring is worth and passing is worth , so passing is strictly better at every record up to position , and hiring is optimal at every record after it. The optimal strategy is : pass on the first candidates, then hire the first record. It wins with probability .