跳至內容

秘書問題

維基百科,自由的百科全書

機率賽局理論上,秘書問題(Secretary problem),類似的名稱有37%法則[1]麥穗理論[2]相親問題止步問題見好就收問題蘇丹的嫁妝問題挑剔的求婚者問題等,屬於最佳停止問題英語Optimal stopping[3]。內容是這樣的:要聘請一名秘書,有 n 個應聘者。每次面試一人,面試後就要即時決定是否聘他,如果當下決定不聘他,他便不會回來。面試後總能清楚了解應聘者的合適程度,並能和之前的每個人做比較。問什麼樣的策略,才使最佳人選被選中的概率最大。

求解最優策略

[編輯]

這個問題的最優解是一個停止規則。在這個規則里,面試官會拒絕頭 r - 1 個應聘者(令他們中的最佳人選為 應聘者 M),然後選出第一個比 M 好的應聘者。可見最優策略包含於這個系列的策略中。(如果M在所有n個應聘者中也是最好的一個,那麼這個策略將選不出任何人選)對於任意的截斷值 r,最佳人選被選中的概率是:


求和符號內概率的計算是基於:如果應聘者 i 是(所有應聘者中的)最佳人選,他被選中當且僅當頭 i - 1 個應聘者中的最佳人選處在頭 r - 1 個被拒絕的應聘者中。令 n 趨近無窮大,把 x 表示為 r/n 的極限,令 ti/ndt1/n,總和可以近似為如下積分:

令 P(x) 對 x 的導數為 0,解出 x,我們得到最優的 x 等於 1/e。從而,當 n 增大時,最優截斷值趨近於 n/e 最佳人選被選中的概率為 1/e

對於較小的 n 值, 最優的 r 也可以通過動態規劃方法得到。下表給出了一些最優的 r 值:

n 1 2 3 4 5 6 7 8 9
r 1 1 2 2 3 3 3 4 4
P 1.000 0.500 0.500 0.458 0.433 0.428 0.414 0.410 0.406

此問題的變種

[編輯]
  • 選擇者可選多於一人
  • 求職者的數目未知
  • 求職者之間的關係可影響選擇
  • 被拒絕的求職者有一定機率能被叫回來
  • 選擇者滿足於次好的人

參考

[編輯]

譯自本頁英文版

  • T. S. Ferguson. "Who solved the secretary problem?" Statistical science, volume 4, pp.282-296. 1988.
  • 數學傳播第二卷第三期 : 海外學人相親記 [1]頁面存檔備份,存於網際網路檔案館

本版未標示充足內容請見英文版

  1. ^ 葉茲 (Kit Yates). 其實攸關貧富與生死的數學並不難!選擇障礙必備的37%法則 (The Maths of Life and Death). 天下文化. 由林俊宏翻譯 (遠見·天下文化事業群). 2022-08-15. (原始內容存檔於2024-03-10). 
  2. ^ 劉潤. 麥穗理論─如何選擇人生中最大的那支麥穗?. 工商時報. 2020-07-18. (原始內容存檔於2024-03-10). 
  3. ^ 林希陶. 人生大事難以抉擇?用「最佳停止點」來幫助你下決定吧!. PanSci 泛科學. 2019-03-19. (原始內容存檔於2023-03-27).