The thresholds that nest

The secretary problem allows one acceptance. Candidates arrive in a random order, each can be taken or passed on the spot, and the goal is to end up with the best. Passing over about a third and then taking the first candidate who beats all of them succeeds about a third of the time, and nothing does better.

Suppose two acceptances are allowed, or three, and success means that the best is among the ones accepted. The obvious guess is that the rule stays the same and simply fires more than once. It does not.

With several choices the best rule has several thresholds, one for each number of choices still in hand, and they nest: with all $k$ choices available the rule starts accepting early, and each time a choice is used the next threshold is later. The last choice is guarded by the same threshold as the original problem’s single one.

What the rule is allowed to know #

The problem is the same as the original in everything but the number of acceptances. Candidates arrive one at a time in a uniformly random order, each is compared only with those already seen, and an acceptance or a rejection is final.

As before, the only candidates worth accepting are the ones that are best so far. A candidate who is beaten by someone already passed cannot be the best overall, and accepting one wastes a choice. So the whole problem is: when a best-so-far candidate appears at position $i$ with $j$ choices left, accept or not?

Two facts about random orders make that question answerable. A candidate at position $i$ is best so far with probability $1/i$, whatever happened earlier. And a best-so-far candidate at position $i$ is the best of all $n$ with probability $i/n$, since the best of all $n$ lies among the first $i$ with exactly that chance. Neither fact depends on the ranks already seen, so the state of the problem at any moment is just the position and the number of choices left.

Backward induction, one choice at a time #

That small state makes the problem solvable exactly, by working back from the end, as the full-information version was.

Write $V_j(i)$ for the chance of success from just after position $i$ with $j$ choices left, playing optimally. After the last candidate nothing more can happen, so $V_j(n) = 0$, and with no choices left nothing can be gained, so $V_0(i) = 0$. At position $i$ the candidate is best so far with chance $1/i$. If it is, accepting is worth $i/n + V_{j-1}(i)$ — the chance this candidate is the best, plus what the remaining choices can still win — and passing is worth $V_j(i)$. If it is not, there is nothing to decide. So

$$V_j(i-1) = \frac{1}{i}\max\!\left(\frac{i}{n} + V_{j-1}(i),\ V_j(i)\right) + \left(1 - \frac1i\right)V_j(i).$$

The rule accepts exactly when the first option in the maximum is the larger, and for each $j$ that happens from some position on: that position is the threshold for $j$ choices in hand. The figure computes the table for sixty candidates and up to four choices, and requires the one-choice column to reproduce the classical optimum exactly — the best of the chances the single-threshold formula gives, taken over every threshold.

Adding the accepted candidates’ chances is legitimate for a reason worth stating. At most one of the accepted candidates can be the best overall, so the events “the first accepted is the best”, “the second accepted is the best” and so on never happen together, and the chance of success is exactly their sum. That is what lets the value of a remaining choice be added to the value of using one now.

Why the thresholds nest #

The thresholds for sixty candidates are at about 0.37 of the field for the last choice, 0.22 for the last two, 0.13 for three and 0.08 for four. More choices in hand, an earlier start.

The reason is what a choice costs. With one choice left, accepting a best-so-far candidate ends the game; the candidate had better be likely to be the best, which it is only late in the sequence. With two left, accepting uses up one choice and leaves another to cover the possibility that someone better turns up — so a less likely candidate is worth taking, and taking starts earlier. A spare choice is insurance against accepting too soon, and the more insurance there is, the sooner it is sensible to act.

The figure requires the nesting for every number of choices it draws, and it is not a feature of sixty in particular.

As the field grows the thresholds settle at fixed fractions and the chances at fixed values. For one choice the fraction and the chance are both $1/e$, which is the constant that counts arrangements with nothing in its place arriving from a different question. For two choices the chance tends to $e^{-1} + e^{-3/2}$, about 59.1 per cent, and the earlier threshold to $e^{-3/2}$ of the field, about 0.223; John Gilbert and Frederick Mosteller worked out these limits in 1966. The figure requires the two-choice chance at sixty candidates to lie within about a hundredth of that limit, and it does, at 60.0 per cent against 59.1.

Each choice buys less #

The chances with one to four choices are 37.3, 60.0, 74.3 and 83.5 per cent. The gains are 22.7 points for the second choice, 14.3 for the third and 9.2 for the fourth.

Every extra choice helps, and every one helps less than the one before. The figure requires the first of those, and the second is visible in the numbers. The reason is the insurance reading again. The first spare choice protects against the most likely way of failing — accepting someone in the middle of the sequence who is later beaten. The second spare choice protects against failing in that way twice, which is less likely, and so on. The best is increasingly likely to have been caught already, and each new choice is spent on a smaller remaining chance.

That diminishing return has a practical reading that is the opposite of the usual advice to keep options open. The first reserve option is worth a great deal and the fourth is worth little, so a process that can afford one fallback gains most of what flexibility can offer from that one.

The failures shrink by a steady factor #

The same four chances read more regularly as failures. With one choice the rule misses the best 62.7 per cent of the time; with two, 40.0; with three, 25.7; with four, 16.5. Each extra choice leaves behind a nearly fixed share of the failures the previous number left: 40.0 is 0.638 of 62.7, 25.7 is 0.643 of 40.0, and 16.5 is 0.642 of 25.7.

To a good approximation, each additional choice removes about a third of the remaining chance of missing the best. In the limit of a large field the first of those ratios is $(1 - 0.591)/(1 - 0.368)$, about 0.647, so the pattern is not an accident of sixty candidates. It is, though, an observation about the four numbers drawn: nothing on this page proves that the share stays near 0.64 for a fifth or a tenth choice, and the argument that would have to be made is about how the nested thresholds’ limits behave, which the figures do not compute.

The regularity says something the chances alone hide. Going from 74.3 to 83.5 per cent looks like a much smaller improvement than going from 37.3 to 60.0, and in chance of success it is. In chance of failure the two steps are the same size, and a process that cares about how often it misses the best, rather than how often it hits it, gets roughly the same value from its fourth choice as from its second.

Small fields do slightly better #

With one choice the best chance is 41.0 per cent for eight candidates, 39.6 for twelve, 37.3 for sixty and 36.9 for two hundred, approaching $1/e$ from above. With two choices it is 63.5 per cent for twelve, 60.0 for sixty and 59.4 for two hundred, approaching 59.1 from above.

The reason is a comparison between a sum and a logarithm. For one choice, the chance of success when $r$ candidates are passed over is $r/n$ times the sum $\tfrac1r + \tfrac1{r+1} + \cdots + \tfrac1{n-1}$, and the limiting curve replaces that sum by $\ln(n/r)$. Each term $1/i$ is larger than the area under $1/x$ between $i$ and $i + 1$, so the sum is always larger than the logarithm, and the chance in a finite field sits above the limiting curve at every threshold. A smaller field has fewer, larger terms, and the excess is bigger.

That is worth knowing because the limits are what are usually quoted. For a field of a dozen, the practical answer to “how often does one choice catch the best” is two in five, not the $1/e$ of a field without end.

What the rule does with sixty candidates #

The fractions in the first figure translate into a concrete procedure. With four choices in hand, the rule passes over roughly the first five candidates and then accepts the first one who beats everyone seen so far.

If that happens early, three choices remain, and the rule does not accept again until it is past roughly the eighth position — any best-so-far candidate before that is passed over, even though a choice is available. With two left it waits until roughly the thirteenth, and with one left until roughly the twenty-second, which is the single-choice rule’s third of the field. A choice in hand is not a reason to accept; the threshold for the number of choices remaining is.

If no best-so-far candidate appears before the later thresholds, the earlier ones simply pass unused. A run in which the best so far keeps being among the first handful, and nobody beats it until position thirty, reaches position thirty with all four choices and accepts at once. The positions are read from fractions rounded to two places, so they are approximate, and the backward induction in the figure fixes each threshold exactly.

Checked on every arrival order #

Backward induction is a calculation about chances, and a mistake in its bookkeeping — adding values that should not be added, or misreading when the maximum switches — would produce a table that looks entirely reasonable. So the figures do not rely on it.

For a small field they play the rule. Every one of the $8! = 40{,}320$ possible arrival orders of eight candidates is generated; the thresholds computed by backward induction are applied to each, one acceptance used whenever a best-so-far candidate appears past the threshold for the choices still in hand; and the fraction of orders in which the best was accepted is counted. For one, two, three and four choices, the count agrees with the backward induction exactly.

For a single choice the same check is the classical one, and it shows the shape the multiple-choice thresholds generalise.

The thresholds as the field grows #

For a single choice the limiting curve is $x\ln(1/x)$, the chance of success when a fraction $x$ is passed over, and its peak is at $1/e$ with height $1/e$. The logarithm comes from the harmonic sum $\tfrac{1}{r} + \cdots + \tfrac{1}{n-1}$ that the exact chance contains, which grows like the logarithm of $n/r$.

For several choices the limits are no longer a single curve but a family of nested exponentials — each threshold’s position is the previous one’s multiplied by a factor that depends on how many choices are in hand — and the successive limits $e^{-1}$, $e^{-3/2}$ and further ones below them are what the sixty- and two-hundred-candidate figures are already close to. The whole multiple-choice problem is the single-choice problem run backwards through several stages, with the value of the later stages feeding into where the earlier ones start.

Where the account needs care #

Success means the best is among those accepted. Other objectives give other rules. If the goal were to maximise the number of accepted candidates who are best so far, or the average rank of the accepted, the thresholds would be different — the average-rank objective already changed the single-choice answer completely.

The order must be uniformly random. Every calculation above uses the fact that a candidate at position $i$ is best so far with chance $1/i$ regardless of the past. An adversary who chooses the order breaks that, and the comparison that makes sense against an adversary is a competitive one rather than a probability.

Acceptances are final, and there is no cost to accepting. A version in which each acceptance costs something, or in which an accepted candidate can be released later, is a different problem with different thresholds.

And the exhaustive check is at eight candidates. The backward induction is exact for any field size; the independent check by playing every order is exact only where every order can be listed, and the figures use it where they can.

Where the problem came from #

The single-choice problem circulated informally in the 1950s and was solved in print by Dennis Lindley in 1961 and by Eugene Dynkin in 1963, the second as an example of a general theory of optimal stopping for Markov processes. Gilbert and Mosteller’s 1966 paper, Recognizing the maximum of a sequence, treated a whole family of variants in one sweep — known and unknown values, one choice and several — and the nested thresholds and their limiting fractions are among its results.

The multiple-choice version has since become the starting point for problems in which the choices are constrained rather than merely counted. Accepting items subject to a budget, or a set of items that must avoid certain combinations, or one item from each of several groups, all generalise “up to $k$”, and the question in each is how much of the best achievable total an online rule can guarantee.

That is the same step the prophet inequality took for a single choice, extended to many — and it arrives at a question that is still open.

Still open: whether every constraint keeps a constant share #

Choosing up to $k$ candidates is the simplest constraint on a set of acceptances. A more general one allows any family of sets with the exchange property of a matroid: roughly, any acceptable set can be grown by an item from any larger acceptable set. Choosing a set of edges with no cycle in a graph is an example; choosing up to $k$ items is another.

Moshe Babaioff, Nicole Immorlica and Robert Kleinberg conjectured in 2007 that for every matroid there is an online rule, with candidates arriving in random order, that secures a fixed fraction of the best possible total — a fraction that does not shrink as the matroid grows. For the case of up to $k$ choices such rules are known, and for many special kinds of matroid too. For matroids in general the best guarantee known shrinks, though extremely slowly, as the size of the largest acceptable set grows, and whether some rule does better for all of them is not known.

A spare choice changes when to use the first #

The habit is about how an option held in reserve changes a decision made now.

It would be natural to treat several acceptances as several copies of the one-acceptance problem, each solved the same way. The calculation says otherwise: the presence of a later choice moves the threshold for an earlier one, because a choice made now is backed by the chance of correcting it. With a spare, it is right to accept candidates that would be too risky to accept without one.

The same structure appears whenever a decision can be revised a limited number of times. The right moment for the first commitment depends on how many revisions remain, and it is earlier the more there are. Treating each commitment as if it were the last makes every one of them too cautious, and treating the first as if revisions were unlimited makes it too hasty; the nested thresholds are exactly the correction between the two.