- 算法之美
- (美)布萊恩·克里斯汀 湯姆·格里菲思
- 2119字
- 2019-01-04 21:35:09
掌握候選對象的完整信息
經典秘書問題的前提條件是,即時表態一定會被接受,而遲滯表態肯定會遭到拒絕,但是我們在前面討論的第一組變量(拒絕與復活)則顛覆了這個前提。在這種情況下,最有效的應對辦法沒有任何變化,仍然是:不要急于表態,觀察一段時間后及時出手。
不過,秘書問題的一個更重要的前提,可能會引起我們的異議。在秘書問題中,除了可以相互比較之外,我們對這些申請者一無所知。對于優秀人員應該具有哪些特點,我們無法參考任何客觀標準或者已有標準,而且在比較這些申請者時,我們只能知道孰優孰劣,但是無法了解彼此之間的確切差距。正因為如此,“觀望”階段是不可避免的。在前期階段,我們冒著與優秀人選失之交臂的危險,不斷調整我們的期望值與權衡標準。數學家把這種最優停止問題稱作“無信息博弈”。
這種情境可能與大多數尋租公寓、尋覓伴侶和招聘秘書的情況有天壤之別。假設我們可以參考某種客觀標準。例如,安排所有秘書參加打字考試,然后像美國高考(SAT)、研究生入學考試(GRE)或者法學院入學考試(LSAT)那樣按照百分制統計成績。也就是說,根據得分,我們可以知道每名申請者的打字水平在所有人選中的位置。如果申請者得了51分,則表示她的打字水平略高于平均水平,如果得了75分,則表示她的水平高于3/4的申請者,以此類推。
假設所有申請者可以代表全體人口樣本,而且所有數據沒有受到任何傾向性或者自選擇的影響。同時,假設打字速度是我們判斷申請者是否合適的唯一條件。此時,情況就完全不同了,因為我們擁有數學家所謂的“全信息”。1966年的那篇秘書問題研討會論文指出:“不需要根據積累的經驗設定判斷標準。有時,我們可以立刻做出一個有益的選擇。”換言之,即使得95分的申請者第一個接受評判,我們也可以信心滿滿地立刻與她簽約。當然,前提是我們認為所有申請者中沒有得96分的。
問題來了。如果我們的目標是找到最適合這份工作的優秀人選,那么我們仍然需要小心斟酌,因為其余的申請者當中可能還有更加優秀的人選。不過,既然我們掌握了全信息,就可以直接計算這種可能性到底有多大。例如,下一個申請者得到96分或者更高分的可能性一定是1/20。因此,是否立刻停止的決定取決于還剩下多少申請者沒有接受面試。全信息的意義在于我們無須觀望就可以直接出手。此時,我們可以運用閾值準則,一旦發現某位申請者的分數高于某個值,就立刻接受她,而不需要先考察一批候選人并確定閾值。但是,我們需要密切關注可供選擇的人還有多少。
數學計算表明,如果還有很多人等待面試,那么你就不應該接受當前正在面試的那名申請者,即使她非常優秀,因為你有可能找到一個更優秀的人選。但是,隨著可供選擇的人數不斷減少,你就應該做好準備,隨時準備與優于平均水平的申請者確立雇傭關系。有一句我們都比較熟悉(盡管不是那么鼓舞人心)的話說得好:面對花哨的包裝,還是降低你的期待吧。我們還可以找到另外一句話,用以說明與之相反的情況:天涯何處無芳草,何必單戀一枝花!重要的是,無論是哪種情況,數學都可以告訴我們臨界點到底在哪兒。
在這種情況下,最簡單的方法是從后往前,反過來理解這些數字的含義。如果你一直面試到最后一名申請者,那么你就別無選擇,只能接受他。如果你一直在觀望,那么在面試倒數第二名申請者時你需要考慮的問題就變成了:他的分數是否高于50呢?如果是,就雇用她;如果不是,那么你可以考慮把寶押在最后一名申請者身上,因為她的分數高于50的可能性是50%。同理,如果倒數第三名申請者的高于69,倒數第四名的分數高于78,以此類推,那么你就應該立刻選擇這名申請者。也就是說,剩余的申請者越多,在評判時就應該越挑剔。無論如何,你都不應該選擇低于平均水平的申請者,除非你已經別無選擇。(此外,既然你一定要在這些申請者當中挑出最優秀的,那么如果某名申請者不是目前為止最優秀的人選,就一定不要雇用他。)
在這種全信息版本的秘書問題中,選中最優秀申請者的可能性是58%。這個概率遠談不上十拿九穩,但是已經大大優于無信息博弈中根據37%法則得到的37%的成功率。如果你掌握了所有信息,那么即使申請人數非常多,你多半也會取得成功。

全信息秘書問題中的最優停止閾值
因此,全信息博弈往往會產生令人意想不到,有時甚至會讓人感到奇怪的結果。如果追求的目標是金錢,而不是愛情,則成功的可能性更高。在根據某種客觀標準(例如收入排名情況)評判合作伙伴時,可供使用的信息比較多。如果評判標準是模糊不清的情感反應(“愛情”),則可能需要我們根據經驗以及比較結果不斷做出調整,同時可供使用的信息也相對較少。
當然,選擇對象的“資產凈值”與我們權衡的標準不一定一致。任何標準,只要可以全面反映申請者與其他人對比的情況,就會導致我們棄用摸清情況再行動準則,轉而采用閾值準則,同時我們成功找出最優秀申請者的可能性也會大大增加。
此外,人們還經常修改秘書問題的其他前提條件,使之與現實生活中尋覓愛情(或挑選秘書)等難題更為相似,結果形成了更多的秘書問題變種。不過,最優停止問題給我們的啟發不僅限于約會與招聘這兩個方面。事實上,在租房子、找停車位、見好就收的時機選擇等問題中,我們同樣需要面對一個又一個的可選方案,做出最有利的選擇。從一定程度上說,這些問題已經得到了解決。