Giving up on the best

The rung below optimises a peculiar objective. Its rule is built to land the single best candidate and treats every other outcome as an equal failure: the second-best counts exactly as badly as the worst, and a rule that reliably delivered the third-best would score nothing at all.

Nobody wants that. Ask for the smallest average rank instead — one for the best, two for the second, and so on — and the answer changes shape entirely.

Fourth-best out of a million. That is the fact worth carrying, and it is not obvious that any such bounded answer should exist.

Why a bounded answer is surprising #

With $n$ candidates a rule that chooses at random gets an expected rank of $(n+1)/2$, which grows without limit. A rule that always takes the first gets the same. So the naive expectation is that the answer grows with the field, slowly perhaps, but without bound.

It does not. The expected rank climbs — $1.25$, $1.5$, $1.71$, $1.90$ at two, three, four and five candidates — and then flattens, reaching $2.40$ at ten, $3.35$ at fifty, $3.70$ at two hundred, and $3.83$ at a thousand. The limit is $3.8695$.

A larger field makes the problem harder in one sense and easier in another, and the two cancel. Harder, because the best is one in more; easier, because there are more chances to see something excellent early and more information about where the field stands by any given point. The second effect wins asymptotically and the two balance at a constant.

The balance can be seen in the recursion. The expected final rank of a candidate of relative rank $r$ at position $i$ is $r(n+1)/(i+1)$, and both the numerator and the denominator scale with $n$ — so at a fixed fraction of the way through, the expected rank of the current leader is a number that does not depend on $n$ at all. The problem at a fixed fraction of the way through is the same problem whatever the size, which is why the answer converges, and the convergence is the statement that the discrete recursion approaches a continuous one.

That is the same reason the rung below’s optimum is a fraction rather than a count, and it is worth noticing that the two problems converge for the same structural reason and to completely different kinds of answer — a probability there and a rank here.

That is a genuinely different situation from the rung below’s, where the probability of landing the best also converges — to $1/e$ — but converges to something that gets worse as the objective becomes harder to satisfy. Here the objective is stable and the answer is stable with it.

The recursion #

The computation is exact and needs no values, which is the reassuring part: it works in the relative-ranking setting the rung below assumes.

At position $i$, a candidate’s relative rank among the first $i$ is all that is known about them. If that rank is $r$, the expected rank among all $n$ is

$$\frac{r(n+1)}{i+1},$$

because the remaining $n - i$ candidates are, conditionally, uniformly spread among the possible positions. So a candidate of relative rank $r$ arriving late has a low expected final rank and one arriving early has a high one — which is why the rule accepts more freely as the field runs out.

The value of continuing is computed backwards. At the last position, taking whatever arrives has expected rank $(n+1)/2$. At position $i$, the value is the average over relative ranks of the better of accepting and continuing:

$$V_{i-1} = \frac{1}{i}\sum_{r=1}^{i}\min\!\left(\frac{r(n+1)}{i+1},\; V_i\right).$$

The figures run that recursion for each field size and check the two cases where the answer is known exactly.

The rule that comes out is a list of acceptable ranks, one per position: at position $i$ accept anything of relative rank at most some $r_i$, and $r_i$ grows as the end approaches. Early on only a leader will do; near the end the third or fourth-best so far is taken.

Two features of that list are worth extracting, because together they describe the rule completely.

It starts at one and it starts immediately. Unlike the rung below’s rule there is no initial period of pure observation: a leader arriving first is accepted, because a leader at position one has expected final rank $(n+1)/2$ — no better than a random draw — and the recursion nonetheless finds it worth taking when $n$ is small, and not when $n$ is large. So for a large field the early positions do have an effective observation period, and it arrives as a consequence rather than as part of the rule’s design.

It ends at everything. At the last position every relative rank is acceptable, since the alternative is nothing at all. The list therefore runs from one to $n$, and where it climbs is what the recursion computes.

The rule is a curve rather than a switch, and that is the shape difference from the rung below. One number tunes the best-only rule and $n$ numbers tune this one, which is why the first has an intuitive statement and the second does not.

What the two objectives disagree about #

Running each rule under the other’s objective is the clean way to see the difference, and the disagreement is not marginal.

The best-only rule, judged on rank, is poor. It rejects everything for the first third and then insists on a leader, so it frequently reaches the end with nothing and has to take the last candidate — whose expected rank is $(n+1)/2$, which grows. About a third of the time it takes the best; the rest of the time it often takes something very bad.

The rank rule, judged on landing the best, is also poor. It accepts a third-best-so-far near the end rather than gambling, so it misses the best far more often than the other rule does.

Neither is a compromise and neither dominates. They are the optimisers of two different things, and the objective is a choice that has to be made before any optimisation is meaningful. That is a fact about decision problems and not about this one.

The rung below stated the same point as a caution — it does not maximise the expected rank — and this rung is what the alternative actually is.

Where the constant comes from #

$3.8695$ has a closed form and it is worth having because the shape says what is going on:

$$\prod_{j=1}^{\infty}\left(\frac{j+2}{j}\right)^{1/(j+1)} = 3.8695\ldots$$

An infinite product of terms each slightly above one, with exponents shrinking. Nothing in it resembles $e$ or any other named constant, and it is not known to be anything but its own value.

The product comes out of the limiting form of the recursion, where the acceptable rank at a given fraction of the way through the field settles to a function of that fraction. The rule in the limit is: at a fraction $t$ of the way through, accept anything whose relative rank is at most a number growing like $1/(1-t)$ — so the standard relaxes hyperbolically towards the end.

Chow, Robbins and Moriguti computed the constant in 1964, with Samuels; the paper is the reason the problem has a name and the constant has a value.

The product converges, and slowly. Its first few factors are $3^{1/2}$, $2^{1/3}$, $(5/3)^{1/4}$, $(3/2)^{1/5}$ — each above one and each contributing less — and multiplying the first ten gives about $3.65$, the first hundred about $3.85$. The infinite product’s slow convergence is the same slowness the recursion shows, which is reassuring rather than coincidental: the product is what the recursion becomes in the limit, so the two approach their common value at the same rate.

That also explains why no field size anybody would draw reaches the constant. Six thousand candidates gives $3.862$, and closing the remaining gap of $0.008$ takes an order of magnitude more. A quantity converging like the reciprocal of a logarithm is a quantity whose limit is never observed, only inferred.

The rule the rung below optimises does not converge in the same way, and putting the two convergences side by side says what is different about them.

Both rules run on the same object — a list of arrival orders — and it is worth seeing that object once, because the two objectives read it completely differently.

The two rules, side by side #

Writing the two rules out at a small size makes the disagreement concrete, and seven candidates is small enough to state and large enough to differ.

The best-only rule passes over the first three and then accepts the first leader. It wins $35.4$ per cent of the time; the rest of the time it takes whatever is left at the end, which is a uniformly random rank.

The rank rule accepts a leader at any position, accepts a second-best-so-far from about the fourth position on, and accepts a third-best-so-far near the end. It almost never reaches the last position without having accepted, which is where its advantage comes from.

The difference is entirely in what happens when nothing excellent arrives early. The best-only rule keeps holding out, on the grounds that only a leader scores; the rank rule takes something respectable, on the grounds that a respectable outcome is worth more than a small chance of a perfect one.

So the two rules differ most on the runs where the field is mediocre, and agree on the runs where an outstanding candidate arrives late. That is why the disagreement grows with the field: a larger field has more mediocre runs in proportion, and more positions in which the two rules give different instructions.

What the objective still does not capture #

Expected rank is a better objective than “the best or nothing” and it is not the last word, and the reasons are worth listing because they are the reasons any single objective is a choice.

Rank is ordinal and the values may not be, in the way a ranking of candidates is a different object from a scoring of them. If the best candidate is far better than the second and the rest are indistinguishable, expected rank treats a near-miss as a small loss when it is a large one. The full-information version uses the values and would answer differently.

The average hides the spread. A rule achieving an average rank of $3.87$ may reach it by usually landing second and occasionally landing five-hundredth, or by landing fourth almost every time. Those are different outcomes and the objective cannot distinguish them.

And rank grows linearly while dissatisfaction may not. Being handed the thousandth-best is not a thousand times worse than being handed the best in any setting anybody would describe; a rule minimising expected rank is optimising a scale nobody chose.

The general form of all three is one observation: an objective is a modelling decision, and optimising the wrong one perfectly is a familiar way of getting a bad answer. Every voting rule satisfies some conditions and fails others for the same reason — the conditions are the objective and choosing them is the whole question.

Where the account needs care #

The recursion assumes a known field size. The value at the last position is $(n+1)/2$, which needs $n$ — an expectation over a uniform draw and the one place the field’s size enters directly. A version where the number of candidates is random has a different answer and a different constant.

The relative rank is all that is used. No values are needed anywhere, which is what makes the rule implementable in the same setting as the rung below’s. A version using values would be a different problem again.

The convergence is slow. At a thousand candidates the answer is $3.83$ against a limit of $3.8695$, and at six thousand it is $3.862$. Any claim about “the answer” for a modest field should quote the computed value rather than the limit.

And the arithmetic is exact but the constant is not. Every value in the figures comes from an exact rational recursion; $3.8695$ is an infinite product evaluated numerically, and the figures compare against it rather than deriving it.

The expected rank is finite and the variance is not bounded in the same way. A rule with an average rank near four still, occasionally, ends at the last position and takes whatever is there — whose rank is uniform over the field. So the worst case grows with $n$ even though the average does not, and a reader taking “about the fourth-best” as a description of what happens has taken a description of a mean.

That distinction is the same one Chebyshev’s inequality is about, and it bites here in the direction that matters: the distribution of outcomes has a heavy tail by construction, since the fallback is a uniform draw.

Robbins’ problem, which is still open #

There is a fourth version of this problem, and its status is worth knowing because it is unusual.

Suppose the values are shown, drawn from a known distribution, and the objective is the expected rank. That combination — full information and the rank objective — is Robbins’ problem, and it is unsolved. The optimal rule is not known, and the limiting value is known only to lie between about $1.908$ and $2.327$.

What makes it hard is that the optimal rule is not a threshold rule of any simple kind: the decision at a given position depends on the whole history of values seen, not just on the current one and the best so far. So the backward induction has no finite-dimensional state to summarise, and the methods that answer the other three versions do not apply.

Three of the four combinations are settled and the fourth is open, and the open one is the combination that uses the most information. That is worth registering: more information makes the rule better and can make the analysis impossible, and the two are not in tension because they are statements about different things.

What the pictures cannot show #

The curve is a set of computed points and the claim is about a limit. At six thousand candidates the value is $3.862$ and the limit is $3.8695$; the figure shows a curve that has nearly flattened, which is evidence and not proof.

The rule itself is not drawn. It is a list of acceptable ranks, one per position, and a plot of it would be a second figure whose whole content — the list grows towards the end — is a sentence.

And nothing here shows the spread of outcomes. The vertical axis is an average, and a rule achieving it consistently and a rule achieving it by mixing excellent and terrible outcomes would produce identical figures.

The ladder from here #

Rungs above: the prophet inequality, where the objective becomes the expected value and the comparison is against an oracle. Robbins’ problem, and the bounds that are all anybody has for it. The multiple-choice version, where several candidates may be accepted and the acceptable ranks nest. The random-horizon version, where the field’s size is unknown. And the connection to optimal stopping in continuous time, where the same questions are asked of a process that never stops arriving.

Optimising the objective before optimising the rule #

The habit is worth stating because the rung below’s result is so often quoted without it.

The secretary problem’s $1/e$ is the answer to “maximise the chance of landing the single best”. That objective was chosen because it makes a clean problem, and it is a strange thing to want; the number is famous and the objective is rarely examined.

Changing it to something a person would actually want changes the answer from a probability to a rank, from $0.368$ to $3.87$, and from a rule with one threshold to a rule with a list of them. None of that is a refinement of the original result — it is a different result about a different question.

The recommendation is the obvious one and it is constantly ignored: before optimising, check that the thing being optimised is the thing wanted. The test is to ask what the optimum does in the cases the objective treats as equivalent, and here it is stark — the famous rule is indifferent between the second-best and the worst, and any reader would not be.