5D Library › 未知地形中的贝叶斯搜索、秘书问题与吉廷斯指数 · English

第二章 秘书问题的变体与人的停止行为

第一章的结论依赖一组很窄的条件。本章逐一放宽它们:看得到实际分数;目标换成期望名次;录用可能被拒绝;最后可以回头;人数事先不知道。最后讨论实验中人们实际怎样停下。

看得到分数:完全信息版本

如果每个求职者的水平是一个可以看到的分数,而且知道分数的分布(例如在 0 到 1 之间均匀分布),问题就变成了完全信息版本。这时不需要先「看行情」:第一个人的分数本身就告诉你他大概处在什么位置。

推导

设还剩 kk 人没有面试。如果眼前这个人的分数 xx 是迄今最高的,录用他,成功(他是全体最佳)的概率是 xkx^k;如果放过他、改为录用之后第一个超过 xx 的人,成功概率是 ∑j=1k(kj)xk−j(1−x)j/j\sum_{j=1}^{k}\binom{k}{j}x^{k-j}(1-x)^j/j。两者相等时的 xx 就是阈值 bkb_k:令 z=(1−bk)/bkz = (1-b_k)/b_k,它满足 ∑j=1k(kj)zj/j=1\sum_{j=1}^{k}\binom{k}{j}z^j/j = 1 (Gilbert and Mosteller 1966)。规则是:遇到迄今最高、且不低于 bkb_k 的分数就录用。程序求出阈值,并用 40,000 次模拟估计成功概率;第二部分用逆向归纳计算只看相对名次时最小期望名次(第 1 名记为 1),并与 37% 规则下的期望名次比较。

# (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

阈值随剩余人数增加而升高:只剩 1 人时,分数过半就录用;剩 10 人时要 0.924 以上;剩 100 人时要 0.992 以上。k(1−bk)k(1-b_k) 趋于约 0.804,也就是说阈值大约是 1−0.804/k1 – 0.804/k。成功概率 n=10n = 10 时为 0.607,n=100n = 100 时为 0.579(模拟标准误约 0.0025),与吉尔伯特与莫斯特勒给出的极限 0.5802 一致 (Gilbert and Mosteller 1966)。从约 0.37 提高到约 0.58,衡量的是「知道分数及其分布」这条信息的价值。

目标换成期望名次

只看相对名次时,如果目标不是「选中第一名」,而是让被录用者的期望名次尽量小(第 1 名最好),最优规则就不再是单一阈值,而是一组随时间放宽的阈值:越往后,可以接受的相对名次越宽。周元燊、森口繁一、罗宾斯与塞缪尔斯 1964 年证明,当 n→∞n \to \infty 时,最小期望名次趋于约 3.8695 (Chow et al. 1964)。

程序的逆向归纳给出:n=10n = 10 时最小期望名次为 2.56,n=40n = 40 时 3.33,n=100n = 100 时 3.60,n=1000n = 1000 时 3.83,n=100,000n = 100{,}000 时 3.869,逐渐逼近 3.8695。也就是说,即使有十万名求职者,只靠相对名次,平均也能录用到前四名左右的人。相比之下,37% 规则下被录用者的期望名次在 n=40n = 40 时为 8.9,在 n=100n = 100 时为 19.6(规则失败时被迫录用最后一个人),而且随 nn 增大而变大。两种目标的最优规则差别如此之大,说明在应用秘书问题之前,首先要问的是:失败的代价是什么?第二名与第五十名是否同样糟糕?

录用可能被拒绝

现实中被录用的人可能拒绝。史密斯 1975 年研究了每次录用以概率 pp 被接受、被拒绝后继续面试的情形 (Smith 1975)。

推导

程序的第一部分对 n=200n = 200 用逆向归纳求最优规则与成功概率,并与史密斯的极限 p1/(1−p)p^{1/(1-p)} 比较(它同时是最优的跳过比例与成功概率的极限)。第二部分是本书写的一个简化模型:如果到最后都没有录用任何人,可以回头联系迄今见过的最好的人,他仍然可用的概率为 qq。用阈值 x=(r−1)/nx = (r-1)/n 时,大 nn 下的成功概率为 xln⁡(1/x)+qxx\ln(1/x) + qx,在 x=eq−1x = e^{q-1} 处取得最大值,最大值也是 eq−1e^{q-1}。程序用精确公式计算 n=100n = 100 的情形。第三部分是人数未知的情形:人数 NN 在 1 到 bb 之间均匀分布,只用单一阈值 rr,如果来的人少于 rr 个,就没有录用任何人 (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

录用可能被拒绝时,最优规则更早开始发出录用:p=0.5p = 0.5 时从第 51 位开始(跳过 25%),成功概率 0.251;p=0.25p = 0.25 时从第 32 位开始(跳过 15.5%),成功概率 0.158;都与史密斯的极限 0.25 和 0.1575 接近。直觉是:每一次录用都可能落空,所以需要更多的「出手机会」,学习阶段就要缩短。

最后可以回头

杨 1974 年研究了可以回头联系已被放过的人、但对方可能拒绝的一般情形,并详细讨论了拒绝概率为常数与呈几何形式两种情况 (Yang 1974)。本书的简化模型只允许最后回头一次。它的结论与前一节相反:能回头时应当更晚开始录用。q=0.25q = 0.25 时最优阈值为第 48 位,成功概率 0.475;q=0.5q = 0.5 时为第 61 位、0.609;q=0.75q = 0.75 时为第 78 位、0.780;都与极限 eq−1e^{q-1} 的 0.472、0.607、0.779 接近。道理很简单:最好的人如果被跳过了,还有机会把他找回来,所以多看一些人的代价变小了。q=1q = 1 时问题变得平凡:看完所有人,录用最好的那个。

注

两种放宽,两个方向。 「录用可能被拒绝」使人应当更早出手,「可以回头」使人应当更晚出手。现实中两者常常同时存在(被放过的人可能还在,也可能已经接受了别的机会),所以没有一个比例能够脱离具体条件推荐给所有人。

人数事先不知道

如果人数 NN 在 1 到 bb 之间均匀分布,最佳的单一阈值要大幅提前:b=40b = 40 时只跳过 5 人(12.5%),平均成功概率 0.289;b=200b = 200 时跳过 27 人(13.5%),成功概率 0.274;普雷斯曼与索宁的极限是跳过 e−2≈13.5%e^{-2} \approx 13.5\% 的 bb,成功概率 2e−2≈0.2712e^{-2} \approx 0.271 (Presman and Sonin 1972)。如果误把最大可能人数 bb 当作已知人数、照搬 37% 规则,成功概率只有 0.19 与 0.18:人很可能在学习阶段还没结束时就来完了。图一右图把三种放宽的极限画在一起。

人在实验中怎样停下

证据

停得太早。 西尔与拉波波特 1997 年在实验室中让参与者做经典的秘书问题(只给相对名次),发现参与者倾向于比最优规则更早停止搜索 (Seale and Rapoport 1997);他们用「阈值」与「连续非候选者」等简单启发式描述参与者的行为,后来的研究指出,在最优规则只有一个阈值的问题中,这两种启发式的表现都不错 (Rapoport et al. 2023)。西尔与拉波波特 2000 年又用实验研究了人数未知的版本 (Seale and Rapoport 2000)。比尔登 2006 年指出,如果报酬是被录用者的实际水平而不是「第一名或零」,最优的阈值大约在 n\sqrt{n},远早于 n/en/e,所以实验中「停得太早」部分可能反映了人们自然地关心实际水平,但他把这作为一种推测提出 (Bearden 2006)。

证据

能学会吗。 戈尔德斯坦、麦卡菲、苏里与赖特 2020 年在网上让 6,537 名玩家玩了 48,336 局「重复的秘书问题」:每局 7 个或 15 个盒子,盒子里的数来自三种固定的分布之一,玩家可以在多局中逐渐了解分布 (Goldstein et al. 2020)。玩家一开始既有搜索过少,也有搜索过多;但他们学得很快,拟合得到的阈值在几局之后就接近最优阈值,后期的成功率接近已知分布时的最大值(7 个盒子 0.622,15 个盒子 0.599)。这与西尔和拉波波特只给相对名次的实验形成对比:在那里,参与者无法了解分布,也没有显示出学习。

这两组研究的条件不同,不能简单地放在一起比较:一个只给名次、一局一局独立,一个给数值、而且分布固定可学。第八章的试验要检验的,是在只给相对名次的经典任务中,事先学习一条停止阈值规则能否提高选中最佳者的比例。

假说 · 尚未验证

「过早停止」部分是目标不同的假说(尚未确立)。作者推测,经典任务中的过早停止至少有一部分不是「不懂规则」,而是参与者在心里用的是「选到好的就行」的目标,或者把每多看一个人当作一种成本。如果是这样,教会参与者 37% 规则能提高「选中第一名」的比例,但会降低他们在其他目标上的表现(例如空手而归的比例上升)。如果第八章的试验中,学习规则的一组选中第一名的比例没有提高,或者提高的同时空手而归的比例没有上升,这一假说即失去支持。

本章小结

看得到分数并知道分布时,最优阈值随剩余人数变化,成功概率约为 0.58;以期望名次为目标时,最优规则的期望名次只有约 3.87,而 37% 规则下 n=100n = 100 的期望名次约为 19.6。录用可能被拒绝时应当更早出手,可以回头时应当更晚出手;人数未知时,最佳单一阈值只跳过约 13.5%,成功概率约 0.27。实验中人们在只给名次的任务里倾向于停得太早,而在可以学习分布的重复游戏中很快接近最优。下一章从「何时停」转向「往哪里找」。

参考文献

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).