5D Library › Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices · 中文

Chapter 2 Variants of the Secretary Problem and How People Stop

The conclusions of Chapter 1 rest on a narrow set of conditions. This chapter relaxes them one at a time: actual scores are visible; the objective becomes the expected rank; offers may be refused; one recall is allowed at the end; the number of applicants is unknown in advance. It closes with how people actually stop in experiments.

Seeing the scores: the full-information version

If each applicant’s quality is a visible score and the distribution of scores is known (say, uniform between 0 and 1), the problem becomes the full-information version. There is then no need to “learn the market” first: the first applicant’s score already says roughly where that applicant stands.

Calculation

Suppose kk applicants remain to be interviewed. If the present applicant’s score xx is the highest so far, hiring now succeeds (the applicant is the overall best) with probability xkx^k; passing and instead hiring the first later applicant who beats xx succeeds with probability ∑j=1k(kj)xk−j(1−x)j/j\sum_{j=1}^{k}\binom{k}{j}x^{k-j}(1-x)^j/j. The xx at which the two are equal is the threshold bkb_k: with z=(1−bk)/bkz = (1-b_k)/b_k, it satisfies ∑j=1k(kj)zj/j=1\sum_{j=1}^{k}\binom{k}{j}z^j/j = 1 (Gilbert and Mosteller 1966). The rule is: hire on a score that is the highest so far and at least bkb_k. The program finds the thresholds and estimates the success probability from 40,000 simulated runs; its second part uses backward induction to compute the minimal expected rank (best = 1) with relative ranks only, and compares it with the expected rank under the 37 % rule.

# (1) Full information (Gilbert & Mosteller): values U(0, 1) are seen; with k to come,
#     take a best-so-far x iff x >= b_k, z = (1 - b_k)/b_k solving sum C(k,j) z^j/j = 1.
# (2) Minimal expected rank with relative ranks only (Chow et al.): backward induction.
import math, random

def threshold(k):
    lo, hi = 0.0, 1.0
    for _ in range(60):
        z, s, t = (lo + hi) / 2, 0.0, 1.0
        for j in range(1, k + 1):
            t *= (k - j + 1) / j * z; s += t / j          # t = C(k, j) z^j
        lo, hi = (lo, z) if s > 1 else (z, hi)
    return 1 / (1 + lo)

def full_info_sim(n, runs, rng):
    b, wins = [0.0] + [threshold(k) for k in range(1, n)], 0
    for _ in range(runs):
        xs, best = [rng.random() for _ in range(n)], -1.0
        for i, x in enumerate(xs):
            if x > best:
                best = x
                if x >= b[n - 1 - i]:
                    wins += x == max(xs); break
    return wins / runs

def expected_rank(n):       # stop at i, relative rank r: expected rank r (n+1)/(i+1)
    v = (n + 1) / 2
    for i in range(n - 1, 0, -1):
        c = (n + 1) / (i + 1); m = min(i, int(v / c))      # accept relative ranks <= m
        v = (c * m * (m + 1) / 2 + (i - m) * v) / i
    return v

def classical_rank(n, r, runs, rng):          # 1/e cutoff rule; last one if nobody
    tot = 0
    for _ in range(runs):
        o = list(range(1, n + 1)); rng.shuffle(o); bar = min(o[:r - 1])
        tot += next((x for x in o[r - 1:] if x < bar), o[-1])
    return tot / runs

if __name__ == "__main__":
    rng = random.Random(1966)
    print("full information: b_k " + "  ".join(f"k={k}: {threshold(k):.4f}"
                                              for k in (1, 2, 5, 10, 100))
          + f"\n   k (1 - b_k) at k = 1000: {1000 * (1 - threshold(1000)):.4f}")
    for n in (10, 40, 100):
        p = full_info_sim(n, 40000, rng)
        se = math.sqrt(p * (1 - p) / 40000)
        print(f"   n = {n:3d}: P(best) = {p:.4f} (SE {se:.4f})")
    print("minimal expected rank: " + ", ".join(f"n={n}: {expected_rank(n):.4f}"
                                                for n in (10, 40, 100, 1000)))
    print(f"   n=100000: {expected_rank(100000):.4f}")
    cr = [classical_rank(n, r, 20000, rng) for n, r in ((40, 16), (100, 38))]
    print(f"expected rank, 1/e cutoff rule: n=40: {cr[0]:.1f}, n=100: {cr[1]:.1f}")
# full information: b_k k=1: 0.5000  k=2: 0.6899  k=5: 0.8559  k=10: 0.9240  k=100: 0.9920
#    k (1 - b_k) at k = 1000: 0.8039
#    n =  10: P(best) = 0.6066 (SE 0.0024)
#    n =  40: P(best) = 0.5941 (SE 0.0025)
#    n = 100: P(best) = 0.5794 (SE 0.0025)
# minimal expected rank: n=10: 2.5579, n=40: 3.3282, n=100: 3.6032, n=1000: 3.8324
#    n=100000: 3.8690
# expected rank, 1/e cutoff rule: n=40: 8.9, n=100: 19.6

The threshold rises with the number of applicants still to come: with 1 left, hire on any score above one half; with 10 left, only above 0.924; with 100 left, only above 0.992. k(1−bk)k(1-b_k) tends to about 0.804, so the threshold is roughly 1−0.804/k1 – 0.804/k. The success probability is 0.607 for n=10n = 10 and 0.579 for n=100n = 100 (simulation standard error about 0.0025), consistent with the limit of 0.5802 given by Gilbert and Mosteller (Gilbert and Mosteller 1966). The rise from about 0.37 to about 0.58 measures the value of one piece of information: knowing the scores and their distribution.

Expected rank as the objective

With relative ranks only, if the objective is not “choose the best” but to make the expected rank of the person hired as small as possible (rank 1 is best), the optimal rule is no longer a single threshold but a series of thresholds that relax over time: the later it is, the wider the range of acceptable relative ranks. Chow, Moriguti, Robbins and Samuels proved in 1964 that as n→∞n \to \infty the minimal expected rank tends to about 3.8695 (Chow et al. 1964).

The program’s backward induction gives a minimal expected rank of 2.56 for n=10n = 10, 3.33 for n=40n = 40, 3.60 for n=100n = 100, 3.83 for n=1000n = 1000 and 3.869 for n=100,000n = 100{,}000, approaching 3.8695. Even with a hundred thousand applicants and only relative ranks to go on, one can on average hire someone around the top four. Under the 37 % rule, by contrast, the expected rank of the person hired is 8.9 for n=40n = 40 and 19.6 for n=100n = 100 (with the last applicant hired when the rule fails), and it grows with nn. The optimal rules for the two objectives differ so much that, before applying the secretary problem, the first question to ask is: what does failure cost? Is the second best as bad as the fiftieth?

Offers that may be refused

In reality, the person offered the job may decline. In 1975 Smith studied the case in which each offer is accepted with probability pp and the search continues after a refusal (Smith 1975).

Calculation

The first part of the program uses backward induction for n=200n = 200 to find the optimal rule and its success probability, and compares them with Smith’s limit p1/(1−p)p^{1/(1-p)} (which is the limit of both the optimal share skipped and the success probability). The second part is a simplified model written for this book: if nobody has been hired when the list runs out, the best applicant seen so far can be called back and is still available with probability qq. With threshold x=(r−1)/nx = (r-1)/n the success probability for large nn is xln⁡(1/x)+qxx\ln(1/x) + qx, maximised at x=eq−1x = e^{q-1}, where the maximum is also eq−1e^{q-1}. The program computes the case n=100n = 100 from the exact formula. The third part is the case of an unknown number of applicants: the number NN is uniform between 1 and bb, a single threshold rr is used, and if fewer than rr applicants arrive nobody is hired (Presman and Sonin 1972).

# Relaxed secretary problems (relative ranks only).
# (a) Offers accepted with probability p, search goes on after a refusal (Smith 1975);
#     backward induction; Smith's limit p^(1/(1-p)).
# (b) Book's simplified model: if nobody is chosen, the best seen so far can be recalled
#     at the end, still available w.p. q; P = x ln(1/x) + q x, best at x = e^(q-1).
# (c) N uniform on 1..b (Presman & Sonin 1972); single cutoff r; too few -> nobody.
import math

def uncertain(n, p):
    v, first = 0.0, n
    for i in range(n, 0, -1):
        if i / n >= v:
            first = i
        v = (1 / i) * max(p * i / n + (1 - p) * v, v) + (1 - 1 / i) * v
    return v, first

def p_cut(n, r):
    if r > n:
        return 0.0
    return 1 / n if r == 1 else (r - 1) / n * sum(1 / (i - 1) for i in range(r, n + 1))

def unknown_n(b, r):
    return sum(p_cut(m, r) for m in range(1, b + 1)) / b

if __name__ == "__main__":
    print("(a) n = 200:  p   first offer at   P(best hired)   limit p^(1/(1-p))")
    for p in (1.0, 0.75, 0.5, 0.25):
        v, f = uncertain(200, p); lim = 1 / math.e if p == 1 else p ** (1 / (1 - p))
        print(f"           {p:4.2f}    {f:4d} ({(f - 1) / 200:.3f})      {v:.4f}"
              f"          {lim:.4f}")
    print("(b) n = 100:  q   best cutoff r   P(best hired)   limit e^(q-1)")
    for q in (0.0, 0.25, 0.5, 0.75):
        pr, r = max((p_cut(100, r) + q * (r - 1) / 100, r) for r in range(1, 101))
        print(f"           {q:4.2f}       {r:4d}          {pr:.4f}"
              f"       {math.exp(q - 1):.4f}")
    print("(c) N uniform on 1..b, single cutoff r")
    for b in (40, 200):
        r = max(range(1, b + 1), key=lambda k: unknown_n(b, k))
        r37 = round(b / math.e) + 1
        print(f"   b = {b:3d}: best r = {r}, (r-1)/b = {(r - 1) / b:.3f},"
              f" P = {unknown_n(b, r):.4f}; 1/e cutoff r = {r37}:"
              f" P = {unknown_n(b, r37):.4f}")
    print(f"   limits (Presman-Sonin): (r-1)/b -> e^-2 = {math.exp(-2):.4f},"
          f" P -> 2 e^-2 = {2 * math.exp(-2):.4f}")
# (a) n = 200:  p   first offer at   P(best hired)   limit p^(1/(1-p))
#            1.00      74 (0.365)      0.3695          0.3679
#            0.75      64 (0.315)      0.3177          0.3164
#            0.50      51 (0.250)      0.2509          0.2500
#            0.25      32 (0.155)      0.1580          0.1575
# (b) n = 100:  q   best cutoff r   P(best hired)   limit e^(q-1)
#            0.00         38          0.3710       0.3679
#            0.25         48          0.4750       0.4724
#            0.50         61          0.6085       0.6065
#            0.75         78          0.7799       0.7788
# (c) N uniform on 1..b, single cutoff r
#    b =  40: best r = 6, (r-1)/b = 0.125, P = 0.2889; 1/e cutoff r = 16: P = 0.1895
#    b = 200: best r = 28, (r-1)/b = 0.135, P = 0.2742; 1/e cutoff r = 75: P = 0.1847
#    limits (Presman-Sonin): (r-1)/b -> e^-2 = 0.1353, P -> 2 e^-2 = 0.2707

When offers may be refused, the optimal rule starts making offers earlier: with p=0.5p = 0.5 from position 51 (skipping 25 %), with success probability 0.251; with p=0.25p = 0.25 from position 32 (skipping 15.5 %), with success probability 0.158 — both close to Smith’s limits of 0.25 and 0.1575. The intuition is that any offer may come to nothing, so more chances to act are needed and the learning phase must be shorter.

One recall at the end

Yang in 1974 studied the general case in which applicants who were passed over can be approached again but may refuse, and examined in detail the cases of a constant and of a geometric refusal probability (Yang 1974). The book’s simplified model allows only one recall at the end. Its conclusion runs opposite to that of the previous section: when recall is possible, one should start hiring later. With q=0.25q = 0.25 the optimal threshold is position 48 and the success probability 0.475; with q=0.5q = 0.5, position 61 and 0.609; with q=0.75q = 0.75, position 78 and 0.780 — all close to the limit eq−1e^{q-1} (0.472, 0.607 and 0.779). The reason is simple: if the best applicant has been skipped there is still a chance to get that person back, so looking at more applicants costs less. With q=1q = 1 the problem becomes trivial: see everyone and hire the best.

Note

Two relaxations, two directions. “Offers may be refused” means one should act earlier; “recall is possible” means one should act later. In reality both are often present at once (the person passed over may still be available, or may have accepted another offer), so no single percentage can be recommended to everyone regardless of the conditions.

An unknown number of applicants

If the number NN is uniform between 1 and bb, the best single threshold comes much earlier: for b=40b = 40 it skips only 5 applicants (12.5 %), with average success probability 0.289; for b=200b = 200 it skips 27 (13.5 %), with success probability 0.274. Presman and Sonin’s limits are a skip of e−2≈13.5%e^{-2} \approx 13.5\,\% of bb and a success probability of 2e−2≈0.2712e^{-2} \approx 0.271 (Presman and Sonin 1972). Treating the largest possible number bb as if it were the known number and applying the 37 % rule gives a success probability of only 0.19 and 0.18: applicants may well stop arriving before the learning phase is over. The right panel of Figure 1 shows the limits for the three relaxations together.

How people stop in experiments

Evidence

Stopping too early. Seale and Rapoport in 1997 had participants in the laboratory play the classical secretary problem (relative ranks only) and found that they tended to stop searching earlier than the optimal rule prescribes (Seale and Rapoport 1997). They described participants’ behaviour with simple heuristics such as a “cutoff” rule and a “successive non-candidate” rule; later work points out that in problems whose optimal rule has a single threshold, both heuristics perform well (Rapoport et al. 2023). In 2000 Seale and Rapoport went on to study experimentally the version with an unknown number of applicants (Seale and Rapoport 2000). Bearden noted in 2006 that if the payoff is the actual quality of the person hired rather than “the best or nothing”, the optimal threshold lies near n\sqrt{n}, far earlier than n/en/e, so that “stopping too early” in experiments may partly reflect a natural concern with actual quality — a suggestion he offered as a conjecture (Bearden 2006).

Evidence

Can it be learned? Goldstein, McAfee, Suri and Wright in 2020 had 6,537 players play 48,336 games of a “repeated secretary problem” online: each game had 7 or 15 boxes whose numbers came from one of three fixed distributions, so that players could gradually learn the distribution over many games (Goldstein et al. 2020). At first players both searched too little and searched too much; but they learned quickly, the fitted thresholds came close to the optimal thresholds after a few games, and later win rates approached the maxima attainable with a known distribution (0.622 with 7 boxes and 0.599 with 15). This contrasts with the experiment of Seale and Rapoport, which gave only relative ranks: there participants could not learn the distribution and showed no learning.

The two lines of research used different conditions and cannot simply be set side by side: one gave only ranks, with each game independent, while the other gave values from a fixed distribution that could be learned. The trial in Chapter 8 tests whether, in the classical task with relative ranks only, learning a stopping-threshold rule in advance raises the share of games in which the best option is chosen.

Hypothesis · not established

The hypothesis that “stopping early” partly reflects a different objective (not yet established). The author conjectures that at least part of the early stopping in the classical task is not a failure to understand the rule but reflects an objective such as “a good one will do”, or the treatment of each extra applicant as a cost. If so, teaching participants the 37 % rule will raise their share of “best chosen” but lower their performance on other objectives (for example, the share of games ending with nobody chosen will rise). If in the Chapter 8 trial the group that learns the rule does not choose the best more often, or does so without any rise in the share of games ending with nobody chosen, the hypothesis loses support.

Summary

When scores are visible and their distribution is known, the optimal threshold changes with the number of applicants remaining and the success probability is about 0.58. With expected rank as the objective, the optimal rule achieves an expected rank of only about 3.87, whereas under the 37 % rule the expected rank for n=100n = 100 is about 19.6. When offers may be refused, one should act earlier; when recall is possible, later. When the number of applicants is unknown, the best single threshold skips only about 13.5 %, with success probability about 0.27. In experiments, people tend to stop too early in tasks that give only ranks, but quickly approach the optimum in repeated games in which the distribution can be learned. The next chapter turns from “when to stop” to “where to look”.

References

Bearden, J. Neil. 2006. “A New Secretary Problem with Rank-Based Selection and Cardinal Payoffs.” Journal of Mathematical Psychology 50: 58–59.
Chow, Y. S., S. Moriguti, H. Robbins, and S. M. Samuels. 1964. “Optimal Selection Based on Relative Rank (the ‘Secretary Problem’).” Israel Journal of Mathematics 2: 81–90. https://doi.org/10.1007/BF02759948.
Gilbert, John P., and Frederick Mosteller. 1966. “Recognizing the Maximum of a Sequence.” Journal of the American Statistical Association 61 (313): 35–73.
Goldstein, Daniel G., R. Preston McAfee, Siddharth Suri, and James R. Wright. 2020. “Learning When to Stop Searching.” Management Science 66 (3): 1375–94. https://doi.org/10.1287/mnsc.2018.3245.
Presman, E. L., and I. M. Sonin. 1972. “The Best Choice Problem for a Random Number of Objects.” Theory of Probability and Its Applications 17 (4): 657–68. https://doi.org/10.1137/1117078.
Rapoport, Amnon, Darryl A. Seale, and Leonidas Spiliopoulos. 2023. “Progressive Stopping Heuristics That Excel in Individual and Competitive Sequential Search.” Theory and Decision 94: 135–65. https://doi.org/10.1007/s11238-022-09881-0.
Seale, Darryl A., and Amnon Rapoport. 1997. “Sequential Decision Making with Relative Ranks: An Experimental Investigation of the ‘Secretary Problem’.” Organizational Behavior and Human Decision Processes 69 (3): 221–36.
Seale, Darryl A., and Amnon Rapoport. 2000. “Optimal Stopping Behavior with Relative Ranks: The Secretary Problem with Unknown Population Size.” Journal of Behavioral Decision Making 13: 391–411.
Smith, M. H. 1975. “A Secretary Problem with Uncertain Employment.” Journal of Applied Probability 12 (3): 620–24. https://doi.org/10.2307/3212880.
Yang, Mark C. K. 1974. “Recognizing the Maximum of a Random Sequence Based on Relative Rank with Backward Solicitation.” Journal of Applied Probability 11 (3): 504–12. https://doi.org/10.2307/3212694.

Fan, Y. (2026). Bayesian Search in Unknown Landscapes, Optimal Stopping and Gittins Indices: Exploration–Exploitation Trade-offs and Sunk-Cost Truncation in Statistical Decision Theory [未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23810102 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).