Soft Optimal Stop For 99% Guarantee

By Guillaume Lathoud, August 2025 (glat@glat.info) Github web PDF

The present document and all accompanying files are covered by the Boost License, as described in ./LICENSE (unless precised otherwise).

Work inspired by the peculiarities of the Parisian real estate market.

This article proposes a variation of the Secretary Problem that ensures high reliability of the result, i.e. maximizes the worst-case result.

Starting point: Secretary Problem
The rest of the present article assumes the reader to know the Secretary Problem. If not, please read it first.

250px_secretary_problem.png

(illustration by cmglee - Own work, CC BY-SA 4.0, original)

Secretary Problem Strategy:

In the Secretary Problem, the goal is "to have the highest probability of selecting the best applicant of the whole group". The best applicant is marked with a white star in the above figure.

For that goal, it is shown that the cutoff N_EXPLORE is optimal at around 37% of the total number of candidates.

Issue

Such a goal, and its optimal stop solution (37%), sound nice ; however 37% also means that one has a 37% chance to end up with the fallback solution - i.e. to pick the last candidate.

Indeed, if - like in case 3 in the above figure - one already saw the best possible candidate (white star) before the 37% cutoff, then one mechanically ends up picking the last candidate (marked in yellow), which gives a pretty random result. The output can be pretty bad, so the reliability is not guaranteed, at least not over a single pass.

And in life, there are quite a few single pass situations.

A different goal

Let us look at a slightly different problem: guarantee with 99% chance that we'll pick a "pretty good" candidate (not targetting the best one).

Then we need a strategy to maximize the worst case. To that effect, we choose to maximize the score of the 1% lowest percentile across the results of many simulations.

I have not found existing literature examining that "reliability" goal, see the review in Annex E.

Proposed strategy: very similar to the Secretary Problem strategy, just a bit softer:

So the differences with the Secretary Problem are:

One possible implementation: uniform use case

We don't know anything about the target market, so let's assume that the scores of the candidates are uniformly distributed, from worse (0.0) to best (1.0). (See Annex B for an adaptation to non-uniform score distributions).

For a relatively small total number of candidates LENGTH=100 (for many scenarios, of a realistic order of magnitude), and various soft_factor values, here are the corresponding implementations:

Figure: score at the lowest 1% percentile for various soft_factor values and various cutoff (N_EXPLORE) values:

good_stop_other_strategy_less_demanding_prctile1_simul_length100.png

In all cases, increasing too much the cutoff N_EXPLORE leads to failure.

My favorite would be soft_factor=80% and cutoff threshold N_EXPLORE around 40/100, which gives a score of 0.68 at the lowest 1% percentile.

When accepting the 1% risk, that result is a pretty good guarantee, and most likely in practice we'll end up with a better pick, as shown below.

For soft_factor=80% and cutoff threshold around 40/100:

Values around 0.72 can be judged as "pretty good" - our objective.

Figure: for soft_factor=80% and various cutoff values, score at the lowest 1% percentile, and median score of the top 99% percentiles:

good_stop_other_strategy_less_demanding80pct_prctile1_and_median_top99prctile__simul_length100.png

General Observation

Changing the order of magnitude of LENGTH can possibly change quite a bit the shape of the results. However, a common behaviour emerges, similar to what the above pictures show: with increasing N_EXPLORE, the score increases, then shows a plateau ; then when further increasing N_EXPLORE, the score abruptly falls down to zero.

In other words, about N_EXPLORE: to get a "pretty good" result and guarantee 99% success, one should "explore" long enough (the score increases), but not too long either (abrupt fall to zero).

Conclusion

By not targetting the best candidate, but rather a "pretty good" candidate, we built a strategy that guarantees 99% success - in fact 99.99% (Annex C below). Incremental improvements can be obtained with a 2-step selection approach (Annex D below).

Acknowledgments

Thanks to Julien Bourgeois for his comments.

Annex A: Without scores

As pointed out by user "barely_sentient" on r/math, in the original Secretary Problem, the candidates are ranked in a total order, but there is no score value attributed to them. It is still possible to apply the strategy proposed here:

Annex B: With scores following a non-uniform distribution

One could in practice "uniformize" the distribution by simply dropping the scores and applying Annex A. This should be roughly equivalent to having a function that maps scores to another space where the candidates are uniformly distributed.

Annex C: Lowering the percentile from 1% down to 0.1% and 0.01%

The approach appears to be pretty robust, in fact guaranteeing 99.99% success. See the figure below.

Figure: score at the lowest 1% resp. 0.1% and 0.01% percentile for various soft_factor values and various cutoff (N_EXPLORE) values:

good_stop_other_strategy_less_demanding80pct_prctile1_and_median_top99prctile2__simul_length100.png

Annex D: Incremental improvement with a 2-step selection strategy

Reasoning & 1st (additional) step: during the exploration phase, when we have already explored enough, e.g. at a "pre-cutoff point" at about 66% of the cutoff point, we can already estimate "top-tiers" to be above (1+soft_factor)/2 of the candidates seen so far - i.e. 90% for a soft_factor of 80%, and then, during the rest of the exploration, select such "top-tier", if any.

2nd step: If no such "top-tier" is selected, then after the cutoff point, we pursue the selection phase unmodified (see soft_factor in the text above, e.g. 80% in the present example).

Such a 2-step selection strategy permits to reasonably use higher cutoff values while also permitting to select "top-tiers".

For a soft_factor of 80% and a cutoff threshold around 60/100

Figure: for soft_factor=80% and various cutoff values, score at the lowest 1% percentile, and median score of the top 99% percentiles:

good_stop_other_strategy_twostep_less_demanding80pct_prctile1_simul_length100.png

Percentile analysis: lowering down from 1% to 0.1% and 0.01% (similarly to Annex C): the 2-step strategy appears very slightly less robust than the originally proposed one, but still very much guaranteeing 99.9% and 99.99% success for reasonable cutoff values (say between around 40/100 and 60/100 for the present example).

Figure: score at the lowest 1% resp. 0.1% and 0.01% percentile for various soft_factor values and various cutoff (N_EXPLORE) values:

good_stop_other_strategy_twostep_less_demanding80pct_prctile2_simul_length100.png

Annex E: Comparision with existing literature

The goal of the proposed approach is "reliability": to optimize the worst-case scenario, by maximizing the score of the 1% lowest percentile.

In the existing literature, the two closest works I found are the following:

– 1

https://scholarworks.indianapolis.iu.edu/server/api/core/bitstreams/ad0bc930-ec29-4915-80ac-16843de42988/content

Excerpt:

"Score-Based Secretary Problem: In the context of the Secretary Problem, suppose that the employer, after interviewing the candidates, can assign absolute scores X1, X2, . . ., which are assumed to be drawn independently from the same known continuous distribution function F . What is the employer’s best strategy to maximize the chance of winning (that is, hiring the candidate with the highest score among all n candidates)? What is the maximum probability of winning?"

=> still trying to maximize the same criterion as in the original Secretary Problem.

– 2

https://as.nyu.edu/content/dam/nyu-as/politics/documents/faculty/brams/Secretary%20Problem.pdf

Excerpt:

"We compare three methods—Standard, Reserve (variants A and B), and Score according to three criteria:

(1) Probability of selecting the best candidate;

(2) Expected number of candidates to be interviewed; and

(3) Expected quality of the candidate selected."

=> The criterion (3) is closer to what I'm talking about, but still not maximizing the worst-case scenario - which would however probably be more relevant to a real-life scenario, i.e. an employer trying to absolutely avoid a bad match, and satisfied with a "pretty good" match.

Created: 2025-12-07 Вс 22:05

Validate