最優停止理論：如何選擇停止觀望的時機？（文後留言送書）

如果採用最優停止理論，在100人當中選中最優秀申請人的可能性是37%。

而總人數是100萬時，無論你相信與否，你得到理想結果的可能性仍然是37%。

因此，申請人 ... 程式語言前端開發IOS開發Android開發雲端運算人工智慧伺服器搜尋資料庫軟體開發工具最優停止理論：如何選擇停止觀望的時機？（文後留言送書）2018.07.17程式語言HOME程式語言最優停止理論：如何選擇停止觀望的時機？（文後留言送書）Advertisement本文節選自《演算法之美：指導工作與生活的演算法》中信出版集團，2018年05月出版約翰尼斯·開普勒所有的基督徒都會在結婚請柬的最前面鄭重宣佈，他們走進婚姻的殿堂是遵從上帝的特別安排。

但是，我要站在哲學的角度，詳細地探討這個問題…… 簡·奧斯汀，《愛瑪》如果你覺得馬丁先生是最優秀的人選，如果你覺得與他相處最為融洽，那麼你還猶豫什麼呢? 對於在中學時代就建立了戀愛關係的大一新生而言，感恩節就是一個嚴峻的考驗:因為回家度過短短4天的假期之後，很多戀人就勞燕分飛了。

大學輔導員把這個普遍現象稱作“放棄火雞”。

 大一新生布萊恩就面臨著這個問題。

他中學時的女友在另外一所大學，天各一方的兩個人不僅需要解決空間距離造成的麻煩，還需要認真思考一個問題:他們兩人之間的感情到底有多深?他們從來沒有考慮過這個具有哲學深度的問題。

由於沒有類似的感情可以參考，他們無從回答這個問題。

於是，焦慮不安的布萊恩找到輔導員，向她尋求幫助。

輔導員知道這是新生經常遭遇的一個典型難題，所以她用一種極其冷淡的語氣給出了自己的建議:“先收集一些資料吧。

” 顯而易見，在連續性單配偶的生活方式中，人們不可避免地會遇到一個非常重要的問題:接觸多少人之後，才可以確定自己的理想伴侶?如果在收集資料的過程中與自己的“真命天子”失之交臂，那該怎麼辦?這似乎成了感情問題上無解的“第22條軍規”。

 我們知道，這個令大一新生憂心忡忡、牢騷滿腹的“第22條軍規”其實就是數學界的“最優停止問題”，它的答案其實很簡單，就是37%。

 當然，前提條件是你願意在愛情問題上做出各種假設。

 祕書問題在所有最優停止問題中，最大的難點不在於選擇哪一種可選方案，而是確定自己需要考慮多少種可選方案。

這些問題往往會引發不同的後果，不僅陷入愛河的人和需要租房的人必須慎重考慮，司機、房主、入室行竊者等也常常面臨同樣的抉擇。

 “37%法則”源於所謂的“祕書問題”——最優停止問題中最著名的一類難題。

祕書問題的情境與我們前面考慮過的租房難題十分相似。

假設一堆人申請一個祕書崗位，而你是面試官，你的目標是從這堆申請人中遴選出最佳人選。

你不知道如何給每一名申請人評分，但是可以輕鬆地判斷哪一名申請人更加優秀。

(用數學語言來表述，就是說你只能看到序數，即申請人相互比較的排名，但是無法看到基數，即在一般性評分標準下的得分。

)你按照隨機順序，每次面試一名申請人。

你隨時可以決定將這份工作交給其中一人，而對方只能接受，於是面試工作就此結束。

但是，一旦你否決其中一名申請人，就不能改變主意再回頭選擇他。

 普遍認為，祕書問題第一次出現在出版物中是在1960年2月，那一期的《科學美國人》雜誌在馬丁·伽德納最喜歡的欄目——“趣味數學”專欄中刊登了幾個難題，其中之一就是祕書問題，不過當時沒有明確地提到“祕書”這個詞。

但是，這個問題到底從何而來，這是一個非常神祕的謎。

除了一些推測以外，初期的調查沒有任何確鑿的結論。

隨後，我們風塵僕僕地趕到斯坦福大學，查閱伽德納的文書檔案。

伽德納在20世紀中期留下來的那一盒盒書信，出乎意料地把我們的調查變成了偵探工作。

閱讀書信有點兒像偷聽別人打電話，你只能聽到通話一方所說的話，因此需要推斷另一方到底說了什麼。

從這些回信看，大約50年前，伽德納本人似乎正在調查祕書問題的來源。

但是，看完這些書信，我們更是一頭霧水了。

 哈佛大學數學家弗雷德裡克·莫斯特勒回憶說，1955年，他聽同事安德烈·格里森提到過這個問題，而格里森又是從其他人那裡聽說的。

阿爾伯塔大學的里奧·莫澤在信中說，他曾經在波音公司R.E.加斯克爾的“筆記”中看到過這個問題，而加斯克爾本人則說他是從一位同事那裡聽說這個問題的。

羅格斯大學的羅傑·平克漢姆稱，他是1955年從杜克大學數學家J.舍恩菲爾德那裡第一次聽說祕書問題的，他還說:“我記得，他說他是從密歇根大學的某個人那裡聽說的。

” 幾乎可以肯定，“密歇根大學的某個人”其實就是梅里爾·弗拉德。

儘管在數學界以外幾乎沒有人知道弗拉德，但是他對電腦科學的影響很難被忽略。

他把“旅行商問題”(我們將在第8章深入討論)變成了一個廣為人知的內容，還設計了“囚徒的困境”，甚至“軟體”一詞也可能是他造出來的。

1958年，他成了已知的第一個發現37%法則的人，同時他宣稱，他從1949年就開始考慮這個問題了。

但是，在說到最初來源時，弗拉德本人提到了另外幾名數學家。

 祕書問題是一個近乎完美的數學難題:問題本身表述簡單，解題難度非常高，答案簡潔明瞭，而影響力又足以讓人產生濃厚的興趣。

因此，通過人們的口口相傳，這個問題以燎原之勢在20世紀50年代的數學界迅速蔓延開來。

1960年，在伽德納專欄的推波助瀾之下，它又大大地激發了普通大眾的想象力。

至20世紀80年代，祕書問題已經變成了一個研究分支，無數人撰文討論這個問題及與其相關的變體。

 至於這個問題是如何與祕書產生聯絡的，這是一個非常有意思的過程——每種文化的社會偏愛都會對社會的形式系統產生影響。

例如，在我們的心中國際象棋是中世紀歐洲人的象徵，但是實際上國際象棋起源於8世紀的印度。

15世紀，粗暴的“歐洲化”過程把沙阿(即國王)變成了王，維齊爾(即高官)變成了王后，而大象則成了基督教主教的形象。

最優停止問題同樣有多種不同化身，每種化身都是當時關注熱點的某種反映。

19世紀，最優停止問題的典型形式是巴洛克彩票和女性挑選求婚者的行為;20世紀初，常見的表現形式是駕車度假的人挑選賓館、男性選擇約會物件;在官僚作風盛行、男性占主導地位的20世紀中葉，最典型的最優停止問題是討論男性老闆如何挑選女性助手的問題。

第一次明確提出“祕書問題”的是發表於1964年的一篇論文，自此之後，這個名稱就再也沒有發生變化。

 37%從何而來?在選擇祕書時，遴選程式停止過早或者過晚都會導致不理想的結果。

停止過早，最優秀的申請人還沒有得到亮相的機會;停止過晚，就說明你在為一位根本不存在的更優秀的申請人保留這份工作。

要取得最理想的結果，顯然需要在兩者之間找到最合適的平衡點，在甄選時既不可遲遲不決，又不可草草收手。

 如果找到最優秀申請人是你追求的唯一目標，那麼在整個面試過程中，只要不是已有申請人當中的最優秀人選，你都不會接受。

但是，僅僅達到“目前最佳”這個條件，還不足以說服面試官。

比如說，第一名申請人毫無疑問就符合這個條件。

一般而言，我們有理由相信，隨著面試程式不斷進行下去，出現“目前最佳”申請人的概率將不斷下降。

例如，第二名申請人是截至目前最優秀申請人的可能性是50%，第五名的可能性只有1/5，第六名的可能性只有1/6，以此類推。

因此，隨著面試工作的深入，目前為止最優秀申請人一旦出現，必然會令人眼前一亮(別忘了，根據定義，這名申請人比之前所有申請人都更加優秀)，不過，這種可能性在不斷降低。

 所以說，看到第一個目前最優秀申請人就欣然接受(也就是說，面試第一名申請人之後就結束面試程式)，顯然是過於草率了。

在一共有100名申請人時，也不能因為第二名申請人比第一名申請人更優秀就迫不及待地選擇他，因為這種做法同樣有些操之過急。

那麼，我們到底該怎麼辦? 憑直覺，我們可以找到幾種應對的辦法。

例如，當第三次(或者第四次)出現勝過前面所有的申請人時，就把工作機會交給他。

或者，在連續多個申請人都不理想的情況下，一旦出現一名目前為止最優秀的人選，就毫不猶豫地接受他。

但是，事實證明，所有這些相對來說似乎有道理的策略都算不上是最明智的做法。

事實上，效果最佳的做法是接受所謂的“摸清情況再行動準則”(look-then-leaprule):事先設定一個“觀察”期，在這段時間裡，無論人選多麼優秀，都不要接受他(也就是說，你的任務就是考察目標，收集資料)。

“觀察”期結束之後，就進入了“行動”期。

此時，一旦出現令之前最優秀申請人相形見絀的人選，就立即出手，再也不要猶豫了。

 考慮申請人數極少時的祕書問題，“摸清情況再行動準則”就會自動顯露出來。

如果只有一名申請人，這個問題就非常簡單——接受她的申請!如果有兩名申請人，無論你如何選擇，你成功選到優秀人選的概率都是50%。

你可以接受第一名申請人(此時，她是半程最優秀申請人)，或者拒絕她，而拒絕第一名申請人就意味著接受第二名申請人(她也是半程最優秀申請人)。

 如果有第三名申請人，情況就一下子變得有意思了。

如果隨機選擇一名申請人，得到理想結果的概率是1/3，也就是33%。

有兩名申請人時，我們沒有辦法取得比碰運氣更好的結果。

那麼，在有三名申請人時，會怎麼樣?事實證明，我們可以取得更理想的結果，而其中的關鍵就在第二場面試。

在面試第一名申請人時，我們沒有任何資訊——她肯定是目前最優秀的申請人。

在面試第三名申請人時，我們沒有任何能動性——我們只能將工作機會交給這名申請人，因為我們已經拒絕了其他人的申請。

但是，在面試第二名申請人時，我們既掌握了一些資訊，又有一定的能動性——我們知道她與第一名申請人相比孰優孰劣，同時我們既可以接受她，也可以拒絕她。

如果她比第一名申請人優秀，我們接受她，反之就拒絕她，那麼會產生什麼樣的結果?事實上，在有三名申請人時，這是最理想的方案。

令人吃驚的是，在有三名申請人時採用這個方法，與有兩名申請人時選擇半程最優秀人選的方法相比，效果不相上下。

 在有4名申請人時，窮舉所有可能的情況之後就會發現，我們仍然應該在面試第二名申請人時採取行動;如果一共有5名申請人，我們應該等到面試第三名申請人時才採取行動。

 隨著申請人數不斷增加，觀察與行動之間的分界線正好處在全部申請人37%的位置，從而得出了37%法則:在考察前37%a的申請人時，不要接受任何人的申請;然後，只要任何一名申請人比前面所有人選都優秀，就要毫不猶豫地選擇他。

  事實證明，利用這種最優方案，我們選中最優秀申請人的概率為37%。

方案本身與出現理想結果的概率正好相等，這是這類問題表現出來的令人奇怪的數學對稱性。

上表列出了申請人數不同時的祕書問題最優解決方案。

從中可以看出，隨著申請人數不斷增加，取得理想結果的概率(以及從觀察期切換到行動期的時間點)在37%左右。

 採用最理想的方案也會有63%的失敗率，這是一個令人警醒的事實。

在面對祕書問題時，即使我們採取了最理想的行動方案，在大多數情況下也會遭遇失敗，也就是說，大多數情況下我們都無法選中所有人選當中最優秀的那名申請人。

對於把愛情視為尋覓“真命天子”的人來說，這確實是一個壞訊息。

不過，也不完全都是壞訊息。

直覺告訴我們，隨著申請人數的不斷增加，選中最優秀申請人的可能性將穩步下降。

例如，如果採用隨機選擇的方式，在申請人總數為100時，我們得到理想結果的可能性是1%，在總人數為100萬時，可能性就會降到0.0001%。

但是，令人意想不到的是，祕書問題的計算結果不會發生變化。

如果採用最優停止理論，在100人當中選中最優秀申請人的可能性是37%。

而總人數是100萬時，無論你相信與否，你得到理想結果的可能性仍然是37%。

因此，申請人總數越多，最優演算法理論就越有價值。

的確，在大多數情況下，大海撈針都會無功而返，但是，無論“海洋”多麼遼闊，最優停止理論都是最理想的工具。

 情場上的出手時機托馬斯·馬爾薩斯兩性之間的情慾幾乎不會隨著時代的變遷而發生改變。

在代數學上，我們可以稱之為給定量。

 芭芭拉·布什奪走我的初吻的男人後來成了我的丈夫。

我把這些告訴孩子們時，他們的反應十分強烈。

 卡內基–梅隆大學的運籌學教授邁克爾·特里克也曾經為尋覓真愛而苦惱，當時他還是一名研究生。

他回憶說:“我突然想起來，人們研究過這個問題，這不就是祕書問題嗎?我身邊有一個空缺，現在有若干人提出了申請，而我的目標就是從中選出最優秀的申請者。

”於是，他進行了量化分析。

他不知道他一輩子可以結識多少名女性，但是37%法則有一定的靈活性，既可以表示申請者的人數，也可以表示遴選過程持續的時間。

假設遴選過程從18歲開始，至40歲結束，那麼根據37%法則，在26.1歲時他就應該結束觀察期，隨時果斷出手。

碰巧的是，當時的特里克正好處於這個年齡。

因此，當他發現某一名女性比之前所有約會物件都優秀的時候，他知道機會來了，於是他果斷行動。

他說:“我不知道她會不會是完美的妻子(模型的各種假設都無法幫助我做出這個判斷)，但是毫無疑問，她符合演算法為這個步驟開出的所有條件。

於是，我向她求婚了。

” “結果，她拒絕了我的求婚。

” 至少從17世紀開始，愛情問題就已經讓數學家頭疼了。

現代人知道約翰尼斯·開普勒這個名字，或許是因為他發現行星軌道是橢圓形的，此外他還是“哥白尼革命”的重要成員，與伽利略、牛頓等人一起，顛覆了人類對自己在宇宙中所處位置的認知。

不過，開普勒也不是不食人間煙火。

1611年，在他的第一任妻子離世後，渴盼重建家庭的開普勒開始了漫長而艱苦的求愛經歷，前後一共交往了11名女性。

在前4名交往物件中，開普勒最喜歡第4個(“因為她身材高挑，英姿颯爽”)，但是他沒有就此打住。

開普勒回憶說:“如果不是愛情和理智把第5名女性強推給我，我應該已經安定下來了。

但是，這名女性對我的愛，她的謙恭忠誠、勤儉持家以及她對繼子繼女的愛，一下子征服了我。

” 他接著說道:“不過，我仍然我行我素，繼續與其他女性交往。

” 親朋好友繼續為開普勒牽線搭橋，開普勒也沒有拒絕，不過興致不是很高，因為他的心仍然被第5名交往物件佔據著。

在一共交往了11名女性之後，開普勒決定收手了。

他回憶說:“就在我準備前往雷根斯堡的時候，我回過頭來去找第5名交往物件並向她求婚，結果她同意了。

”於是，開普勒和蘇珊娜·羅伊特林格舉行了婚禮。

除了第一次婚姻留給他的幾個孩子之外，開普勒和羅伊特林格又生了6個孩子。

據說，開普勒之後的家庭生活十分幸福美滿。

 開普勒和特里克在尋覓愛情上的親身經歷告訴我們(兩者的結局正好相反)，祕書問題把情況想得過於簡單了。

在經典的祕書問題中，申請者肯定希望得到那份工作，像特里克那樣遭遇拒絕的情況絕不會發生。

此外，申請者一旦被否決之後，就不可以“復活”，因此開普勒採取的策略是行不通的。

 在祕書問題首次被提出後的幾十年時間裡，人們研究了各種各樣的情境，並結合不同的條件提出了若干最優停止策略。

例如，針對可能遭到拒絕的問題，他們提出了一個簡單明瞭的數學答案:儘早向多名物件伸出橄欖枝。

假如遭到拒絕的可能性是50%，那麼得出37%法則的那個數學分析過程就會告訴你，遴選過程完成1/4後就應該隨時準備求婚了。

如果遭到拒絕，那麼在發現下一個最佳人選時要再次求婚，直到求婚成功為止。

運用這個策略，獲得成功(即向所有人選中的最佳人選求婚並被接納)的總概率仍然可以達到25%。

根據自己的標準尋覓愛情本身就有難度，再加上遭到拒絕這個不利條件，25%的成功概率可以算是一個還不錯的結果了。

 開普勒把自己沒有及時出手的原因歸咎於“不安現狀、心存疑慮”。

他在一封信中向自己的知己好友哀嘆:“難道非得四處碰壁，所有慾望都落空之後，我的心才會平靜下來，接受命運的擺佈嗎?”在這種情況下，最優停止理論同樣可以起到一定的安慰作用。

事實證明，不安現狀和心存疑慮並不是道德淪喪或者心理退化的標誌，而是在合適情境下捕捉二次機會的最有效策略的一個組成部分。

如果可以復活之前被放棄的人選，最優演算法就會對我們所熟悉的摸清情況再行動準則做一個小的調整:推遲表態時間，制訂備用計劃。

 例如，我們假設即時求婚肯定會被接受，而遲滯求婚則有一半的可能遭到拒絕。

根據數學分析，我們在觀察前61%的人選時都不應該表態，等到剩餘39%的人選中出現目前最優秀人選時再出手。

如果考察完了所有人選之後仍然沒有找到合適物件(開普勒當時就面臨這種情況)，就回過頭，在你淘汰的人選當中選擇最優秀的那個。

在這種情況下，策略與結果之間再次表現出對稱性，在允許二次選擇這個條件下，你最終選中最優秀人選的概率仍然是61%。

 正因為現實與經典祕書問題有所不同，所以開普勒最終還是找到了自己的幸福。

事實上，經典問題發生的那個小變化也沒有導致特里克願望落空。

在遭到拒絕之後，特里克讀完大學並在德國找了一份工作。

特里克回憶說:“我在酒吧裡遇到一位漂亮的姑娘，我們一見鍾情，三週後就同居了。

後來，我邀請她去美國‘暫住一段時間’。

”姑娘接受了邀請。

6年後，他們舉行了婚禮。

  掌握候選物件的完整資訊經典祕書問題的前提條件是，即時表態一定會被接受，而遲滯表態肯定會遭到拒絕，但是我們在前面討論的第一組變數(拒絕與復活)則顛覆了這個前提。

在這種情況下，最有效的應對辦法沒有任何變化，仍然是:不要急於表態，觀察一段時間後及時出手。

 不過，祕書問題的一個更重要的前提，可能會引起我們的異議。

在祕書問題中，除了可以相互比較之外，我們對這些申請者一無所知。

對於優秀人員應該具有哪些特點，我們無法參考任何客觀標準或者已有標準，而且在比較這些申請者時，我們只能知道孰優孰劣，但是無法瞭解彼此之間的確切差距。

正因為如此，“觀望”階段是不可避免的。

在前期階段，我們冒著與優秀人選失之交臂的危險，不斷調整我們的期望值與權衡標準。

數學家把這種最優停止問題稱作“無資訊博弈”。

這種情境可能與大多數尋租公寓、尋覓伴侶和招聘祕書的情況有天壤之別。

假設我們可以參考某種客觀標準。

例如，安排所有祕書參加打字考試，然後像美國高考(SAT)、研究生入學考試(GRE)或者法學院入學考試(LSAT)那樣按照百分制統計成績。

也就是說，根據得分，我們可以知道每名申請者的打字水平在所有人選中的位置。

如果申請者得了51分，則表示她的打字水平略高於平均水平，如果得了75分，則表示她的水平高於3/4的申請者，以此類推。

 假設所有申請者可以代表全體人口樣本，而且所有資料沒有受到任何傾向性或者自選擇的影響。

同時，假設打字速度是我們判斷申請者是否合適的唯一條件。

此時，情況就完全不同了，因為我們擁有數學家所謂的“全資訊”。

1966年的那篇祕書問題研討會論文指出:“不需要根據積累的經驗設定判斷標準。

有時，我們可以立刻做出一個有益的選擇。

”換言之，即使得95分的申請者第一個接受評判，我們也可以信心滿滿地立刻與她簽約。

當然，前提是我們認為所有申請者中沒有得96分的。

 問題來了。

如果我們的目標是找到最適合這份工作的優秀人選，那麼我們仍然需要小心斟酌，因為其餘的申請者當中可能還有更加優秀的人選。

不過，既然我們掌握了全資訊，就可以直接計算這種可能性到底有多大。

例如，下一個申請者得到96分或者更高分的可能性一定是1/20。

因此，是否立刻停止的決定取決於還剩下多少申請者沒有接受面試。

全資訊的意義在於我們無須觀望就可以直接出手。

此時，我們可以運用閾值準則，一旦發現某位申請者的分數高於某個值，就立刻接受她，而不需要先考察一批候選人並確定閾值。

但是，我們需要密切關注可供選擇的人還有多少。

 數學計算表明，如果還有很多人等待面試，那麼你就不應該接受當前正在面試的那名申請者，即使她非常優秀，因為你有可能找到一個更優秀的人選。

但是，隨著可供選擇的人數不斷減少，你就應該做好準備，隨時準備與優於平均水平的申請者確立僱傭關係。

有一句我們都比較熟悉(儘管不是那麼鼓舞人心)的話說得好:面對花哨的包裝，還是降低你的期待吧。

我們還可以找到另外一句話，用以說明與之相反的情況:天涯何處無芳草，何必單戀一枝花!重要的是，無論是哪種情況，數學都可以告訴我們臨界點到底在哪兒。

 在這種情況下，最簡單的方法是從後往前，反過來理解這些數字的含義。

如果你一直面試到最後一名申請者，那麼你就別無選擇，只能接受他。

如果你一直在觀望，那麼在面試倒數第二名申請者時你需要考慮的問題就變成了:他的分數是否高於50呢?如果是，就僱用她;如果不是，那麼你可以考慮把寶押在最後一名申請者身上，因為她的分數高於50的可能性是50%。

同理，如果倒數第三名申請者的高於69，倒數第四名的分數高於78，以此類推，那麼你就應該立刻選擇這名申請者。

也就是說，剩餘的申請者越多，在評判時就應該越挑剔。

無論如何，你都不應該選擇低於平均水平的申請者，除非你已經別無選擇。

(此外，既然你一定要在這些申請者當中挑出最優秀的，那麼如果某名申請者不是目前為止最優秀的人選，就一定不要僱用他。

) 在這種全資訊版本的祕書問題中，選中最優秀申請者的可能性是58%。

這個概率遠談不上十拿九穩，但是已經大大優於無資訊博弈中根據37%法則得到的37%的成功率。

如果你掌握了所有資訊，那麼即使申請人數非常多，你多半也會取得成功。

  因此，全資訊博弈往往會產生令人意想不到，有時甚至會讓人感到奇怪的結果。

如果追求的目標是金錢，而不是愛情，則成功的可能性更高。

在根據某種客觀標準(例如收入排名情況)評判合作伙伴時，可供使用的資訊比較多。

如果評判標準是模糊不清的情感反應(“愛情”)，則可能需要我們根據經驗以及比較結果不斷做出調整，同時可供使用的資訊也相對較少。

 當然，選擇物件的“資產淨值”與我們權衡的標準不一定一致。

任何標準，只要可以全面反映申請者與其他人對比的情況，就會導致我們棄用摸清情況再行動準則，轉而採用閾值準則，同時我們成功找出最優秀申請者的可能性也會大大增加。

 此外，人們還經常修改祕書問題的其他前提條件，使之與現實生活中尋覓愛情(或挑選祕書)等難題更為相似，結果形成了更多的祕書問題變種。

不過，最優停止問題給我們的啟發不僅限於約會與招聘這兩個方面。

事實上，在租房子、找停車位、見好就收的時機選擇等問題中，我們同樣需要面對一個又一個的可選方案，做出最有利的選擇。

從一定程度上說，這些問題已經得到了解決。

  賣房子的時機只需修改經典祕書問題的兩個特徵，就可以從浪漫的愛情跳進不浪漫的房地產領域。

在前文中，我們說過租公寓的過程屬於最優停止問題，但是真的擁有房產之後，你仍然難免要與最優停止問題打交道。

 假設你想賣房子。

在諮詢了幾個房地產中介之後，你將粉刷一新、帶有園林景觀的房子推向市場，然後靜等有意者上門。

每個看房人提出有意購買時，你基本上都要做出決定，要麼接受，要麼拒絕。

但是，拒絕是有代價的，因為在下一個有意購買者上門之前，你需要再支付一週(甚至一個月)的抵押貸款，而且下一個購買者的報價未必更高。

 賣房子與全資訊博弈比較相似。

我們知道有意者願意付出的具體金額，不僅可以看出誰報出的價格更高，而且可以看出彼此之間的具體差額。

此外，我們還掌握有關房地產市場行情的更多資訊，至少可以對預計的報價變化幅度做一個大致的預測。

(有了這樣的預測，就相當於掌握了上述打字測試中的資訊。

)兩者之間的差別在於目標不同。

賣房子時，我們的目標其實不是得到最有利的報價，而是通過整個過程最終獲取儘可能多的錢。

由於等待是有代價的，是要付出真金白銀的，因此當前的有利報價比幾個月之後略高一點兒的報價更有吸引力。

 掌握了這些資訊之後，我們就可以省略確定閾值所需的觀望階段，直接確定一個閾值。

然後，我們可以忽略所有低於這個閾值的報價，直接接受第一個高於閾值的報價。

誠然，如果在某個時間之前不把房子出手，我們有限的積蓄就會消耗殆盡，或者我們只想考慮數量有限的幾個報價，對隨後的報價不感興趣，那麼在快要達到極限時，我們當然應該降低標準。

(購房者喜歡找“積極的”賣主，原因就在這裡。

)但是，如果沒有被這兩種情況逼到牆角，那麼我們就可以通過成本效益分析，確定是否應該繼續觀望。

 接下來，我們分析一種非常簡單的情況:假設我們清楚報價金額的變化幅度，並且在這個變化範圍內各種報價出現的可能性是相同的。

只要報價不會中斷(我們的積蓄也不會花完)，我們就可以單純地考慮我們對收穫或損失的期望值，以決定是否繼續等待更有利的交易。

如果拒絕當前的報價，預計出現更有利報價的可能性是多少?該報價與當前報價之間的差，乘以該報價出現的可能性，乘積是否大於繼續等待的成本呢?數學計算的結果清楚地表明，停止價格是等待成本的一個顯函式。

 無論你出售的是價值高達數百萬美元的豪宅，還是搖搖欲墜的棚屋，對這個數學結果都不會有任何影響。

你唯一需要關心的是你可能接收到的最高報價與最低報價之間的差值。

輸入幾個具體數字，就可以看出這個演算法可以提供給我們大量清楚明瞭的指導意見。

例如，假設我們預計報價金額在400000~500000美元之間。

首先，如果等待成本非常低，那麼在挑選買主時我們幾乎無須有任何顧忌。

如果等待下一個報價的成本僅為1美元，那麼為了賺取儘可能多的錢，我們可以一直等到有人願意支付499552.79美元時才出手。

少一分錢，我們都不會賣給他。

如果每次等待需要付出2000美元的代價，那我們就應該等待480000美元這個報價。

如果面對的是一個不景氣的市場，每次等待需要耗費10000美元時，那麼只要報價高於455279美元，我們就應該立刻出手。

最後，假設等待成本為預計報價範圍的一半(在本例中，報價變化幅度的一半就是50000美元)或更高時，那麼觀望對我們來說不會有任何好處，最有利的做法是直接接受第一個報價，然後立刻成交。

人在屋檐下，不得不低頭。

 在這個問題中，閾值完全取決於搜尋成本，這也是這類問題需要注意的關鍵要點。

下一個報價令人心動的可能性(以及搜尋成本)都不會發生任何變化，因此，無論運氣如何，我們在搜尋過程中都無須降低最優停止價格。

一旦確定最優停止價格之後(即使這是我們在將房子推向市場之前做出的決定)，我們就再也不要有任何動搖。

  威斯康星大學麥迪遜分校的優化專家勞拉·阿爾伯特·麥克萊回憶說，她在賣房子時，就用到了最優停止問題的相關知識。

她說:“我們收到的第一個報價就非常高，但是他們希望我們比預計的搬離日期早一個月搬走。

這個代價太大了。

這時候，又有人報出了一個有競爭性的報價……但是我們一直不為所動，直到最後有人報出了令我們滿意的報價為止。

”對很多賣家而言，建議他們拒絕一兩個優厚的報價都會讓他們神經緊張，如果隨後的報價比不上前者，那麼他們就會更加緊張。

但是，麥克萊很冷靜，堅守立場沒有動搖。

她承認:“如果我不知道數學計算的結果，就很難堅持下來。

” 在任何情況下，只要你可以得到一系列報價，而尋找或等待下一個報價需要付出一定成本時，就可以應用上述準則。

因此，除了賣房子，在很多情況下我們都可以考慮這條準則。

例如，經濟學家利用這個演算法構建的找工作模型，可以輕而易舉地解釋失業工人與空缺崗位並存這個看似矛盾的事實。

事實上，最優停止問題的這些變種還有一個更令人吃驚的特性。

前面說過，在開普勒尋覓愛情的過程中，可以“復活”之前被自己拒絕的機會是一個非常重要的條件。

但是，在賣房子或者找工作時，即使我們可以重新考慮之前的報價或工作邀請，即使我們可以肯定那個報價或工作邀請仍然有效，我們也絕不應該重新考慮它。

如果之前它沒有達到閾值的要求，那麼現在它也不會高於閾值。

在拒絕那個報價或工作邀請之後，我們的付出已經成為已支付成本。

因此，不要妥協，不要試圖亡羊補牢。

堅持住，不要回頭! 最優停車位置克拉克·克爾，加州大學伯克利分校校長(1958—1967年) 我發現，大學校園裡有三個主要的行政管理問題:學生關心性愛，校友關心體育，教職員工關心停車問題。

 最優停止問題經常出現的另一個領域與汽車駕駛有關(在這個領域，回頭同樣是不明智的)。

在某些早期文獻中，祕書問題的主角是駕車者，而汽車只進不退的基本設定把駕車旅行中的所有決策過程(包括尋找飯店、尋找浴室，以及最令城市駕車者頭疼的尋找停車位等過程)全部變成了停止問題。

要討論進出停車場的問題，加州大學洛杉磯分校著名的城市規劃教授、被《洛杉磯時報》稱作“停車場搖滾明星”的唐納德·舒普顯然是最合適的人選。

我們從加州北部出發，駕車前往學校拜訪舒普。

我們告訴舒普，我們為這段行程預留了大量時間，讓他不要擔心我們會因為意外的交通情況而無法按時抵達。

舒普回答說:“說到針對‘意外的交通情況’制訂計劃，我認為你們應該考慮的是預計的交通情況。

”舒普的知名度或許大多歸功於他的著作《免費停車的高昂代價》，此外他還做了大量工作，推動人們討論、瞭解駕車旅行的真實情況。

 我們真應該同情那位可憐的駕駛員。

根據舒普的模型，理想的停車位應該在停車位“標價”、行走所需時間及造成的麻煩、尋找停車位所需時間(隨著目的地、一天中的時間不同而發生顯著變化)以及整個過程所消耗的汽油等方面實現優化並達成精確平衡。

因為車內乘客人數不同，上述等式會發生變化，因為乘客可以分擔停車費用，但是無法分擔搜尋時間，也無法分擔步行的時間與麻煩。

與此同時，駕駛者還需要考慮到的一個問題是:停車位最多的地方可能也是停車需求最大的地方。

停車問題含有博弈論的成分，因為在你算計道路上其他駕車者的時候，他們也在算計你。

話雖如此，停車難題大多歸根於一個數字，即停車位佔用率——目前被佔用的所有停車位佔總停車位的比例。

如果佔用率很低，找到一個好的停車位並非難事;如果佔用率很高，想為你的車找到一席之地就不是那麼容易了。

 舒普認為，停車的很多難題都歸因於城市政策，因為這些政策導致停車位佔用率極高。

如果某個地方的停車費用非常低(更糟糕的是，有的甚至免費)，就會刺激人們把車停在那裡，而不是停到稍遠的位置，然後步行。

於是，大家都想在那兒停車，但是大多數人發現那裡已經停滿了車，因此他們只好開著車四處巡遊，試圖找到一個停車位，結果既浪費時間，又浪費汽油。

 舒普建議的解決辦法是安裝數字停車計時器，根據停車需求自動調整價格。

(舊金山市區已經採用了這種計時器。

)在設定價格時，需要先設定一個目標占用率。

舒普認為，這個目標值應該在85%左右(對於路邊停車率接近100%的大多數大城市而言，這個佔用率已經非常低了)。

舒普指出，當停車位佔用率從90%升至95%時，儘管僅多停了5%的車，但是大家尋找停車位的時間就會翻一番。

 一旦意識到停車其實是一個最優停止問題，你就會發現佔用率對停車策略有著關鍵的影響。

行駛在大街上，每次看到一個空車位時，我們都必須做出決定:是停到這個車位上，還是試試運氣，再往前開一點兒? 假設你行駛在一條無限長的道路上，路邊車位均勻分佈，而你的目標是把車停到儘可能接近目的地的車位上，以便少走幾步路。

那麼你應該採用摸清情況再行動準則。

為了實現最優停止這個目標，在距離目的地一定路程之外，即使看到空車位也不要停車;一旦進入一定距離之內，就應該從觀望階段轉變為行動階段，看到空車位後立刻停車。

這段距離的長短，取決於停車位可能被佔用的百分比，即停車位佔用率。

下表列出了與某些有代表性的停車位佔用率相對應的轉變距離。

  如果這條無限長的街道與大城市一樣，停車位佔用率高達99%，只有1%的停車位是空閒的，那麼在距離目的地大約70個停車位(略多於1/4英里a)處開始，只要看到空車位，就應該停車。

但是，如果舒普的辦法奏效，將佔用率降低到85%左右，那麼在距離目的地半個街區之前，你都無須著急停車。

 我們行駛的道路大多不是筆直的，也不會是無限長的。

因此，同其他最優停止問題一樣，研究人員也在上述基本情況的基礎上做出了各種調整。

例如，他們考慮了若干不同情況，包括允許駕駛者調頭、距離目的地越近停車位越少、駕駛者與目的地相同的其他駕駛者形成競爭關係等。

但是，無論該問題的引數發生哪些變化，增加空閒停車位的數量都可以使我們的生活更加方便。

從某種意義上講，這是提示市政府的政策制定者:停車問題不是單純靠增加資源(停車位)並最大化利用資源(佔用)就可以解決的。

停車還是一個程序(是一個最優停止問題)，消耗注意力、時間、汽油，還會導致汙染和擁堵等後果。

合適的政策可以徹底解決這個問題。

而且，適宜居住的街區周圍有空的停車位，可能是街區執行良好的一個標誌，這正好與我們的直覺相反。

 我們問舒普，他在洛杉磯車流中穿行，前往加州大學洛杉磯分校上班的時候，他的研究是否可以為他提供優化方案。

作為一名全世界頂尖的停車問題專家，他是否有什麼祕密武器。

 舒普還真的擁有一個祕密武器:“我騎車上下班。

” 見好就收的時機1997年，鮑里斯·別列佐夫斯基因擁有大約30億美元的財產，被《福布斯》雜誌確認為俄羅斯首富。

僅僅10年前，他還是蘇聯科學院的一名數學家，靠工資度日。

他利用在研究過程中建立的業界關係，建立了一家公司，幫助外國汽車製造商與蘇聯汽車製造商AvtoVAZ溝通交流。

隨後，他的公司變成了AvtoVAZ汽車的大型經銷商，同時還通過分期付款的方法，利用盧布的惡性通貨膨脹牟利。

他還利用與AvtoVAZ的合作關係套取資金，用來購買這家汽車製造商及俄羅斯公共電視臺、西伯利亞石油公司的部分股份。

最終，他賺得了幾十億美元的身家，成為寡頭階層的新成員。

隨後，他開始參與政治。

1996年，他支援鮑里斯·葉利欽連任;1999年，他又支援弗拉基米爾·普京成為葉利欽的繼任者。

 但是，後來別列佐夫斯基的政治態度開始轉變。

普京當選總統之後不久，別列佐夫斯基公開反對普京提出的旨在擴大總統許可權的憲政改革。

他在公開場合不斷批評普京，導致他與普京的關係開始惡化。

2000年10月，在有人請普京就別列佐夫斯基對他的批評發表評論時，普京說:“政府手持大棒，只需一下，就能擊碎其腦殼。

目前我們還沒有動用大棒……一旦我們真的動怒，就將毫不猶豫地砸下去。

”當年11月，別列佐夫斯基就離開了俄羅斯，再也沒有回來。

流亡到英國之後，別列佐夫斯基繼續批評普京。

 別列佐夫斯基如何做出離開俄羅斯的決定?是否可以通過數學方法考慮“見好就收”這條建議?多年前，別列佐夫斯基本人就是一名數學家，而且他研究的正好就是最優停止問題，他創作的第一本書(當然也是他的唯一一本書)全部關於祕書問題，因此他當時可能也考慮了這個問題。

 人們在分析見好就收這個問題時，為它披上了好幾種偽裝，但是最適合別列佐夫斯基這種情況的可能應該是“竊賊問題”(向俄羅斯寡頭表示歉意)。

在竊賊問題中，竊賊可以實施一系列盜竊活動。

他們的每次盜竊都會有收穫，並且每次都有機會帶著戰利品順利脫身。

但是，一旦被抓住，他們就會失去之前的所有收穫。

竊賊希望收穫最大，那麼什麼樣的演算法可以給他提供合理建議呢? 竊賊問題有解，對於盜竊題材的電影劇本而言不是好訊息。

當盜竊團隊誘惑一位已經金盆洗手的老手，希望他復出並幹最後一票的時候，這位狡猾的竊賊只需要認真分析那些數字就知道該怎麼做了。

憑直覺也可以得出結果。

實施盜竊的次數應該大致等於順利脫身的可能性除以被抓的可能性的值。

如果你是一名有經驗的竊賊，每次盜竊成功的可能性為90%(損失全部身家的可能性為10%)，那麼在盜竊9次(90÷10=9)之後，你就應該洗手不幹了。

如果是一名笨手笨腳、成功率只有一半的生手，情況會怎麼樣?第一次去偷盜時，你本來就身無分文，因此無須擔心有任何損失，但是之後就不要再去碰運氣了。

 儘管別列佐夫斯基是最優停止問題方面的專家，但是他的結局仍然十分悽慘。

2013年3月，一名保鏢在他位於伯克郡的住所裡發現了他的屍體。

他死在鎖著的浴室裡，脖子上繫著繩子。

官方在屍檢之後宣佈他死於自殺。

由於他在一系列高調的訴訟案中輸給了俄羅斯對手，也失去大筆財富，因此他走上了上吊自盡這條不歸路。

或許他抽身而退的時間還應該更早一些，在積累幾千萬美元的財富之後就應該收手，而且不能介入政治。

但是，遺憾的是，那不是他的做事風格。

他在數學界的一位朋友里奧尼德·博古斯瓦夫斯基，曾經講過別列佐夫斯基的一件往事。

當時，他和別列佐夫斯基都還是年輕的研究員。

他們前往莫斯科附近，準備進行湖上滑水活動。

但是，他們計劃使用的那條船出了故障。

戴維·霍夫曼在他的《寡頭》一書中有這樣一段文字: 朋友們都跑上沙灘，點起了篝火，只有博古斯瓦夫斯基和別列佐夫斯基向船塢走去，準備修理那臺發動機……三個小時之後，他們已經把發動機拆裝了一遍，但是發動機仍然無法工作。

儘管已經錯過了聚會的大多數活動，但是別列佐夫斯基仍然堅持說，他們一定要繼續嘗試修理發動機。

博古斯瓦夫斯基回憶說:“我們想盡辦法，試圖修好那臺發動機。

”別列佐夫斯基從來不會輕言放棄。

令人吃驚的是，在最優停止的文獻資料中也曾提到過不放棄(而且是永不放棄)。

有的時序決策問題似乎沒有最優停止準則，儘管從我們前面討論的大量問題看，似乎不應該出現這種情況。

“要麼三倍，要麼賠光”的博弈遊戲就是一個簡單的例子。

假設你帶著1美元去玩這個遊戲。

遊戲規則對輪次沒有限制，但是要求你每次都要押上所有的錢，你有50%的機會贏回三倍的錢，另外50%的機會全部賠光。

那麼你應該參與多少輪呢?儘管這個問題非常簡單，但它沒有合適的最優停止準則，因為每參加一輪遊戲，你的平均收益都會略有增加。

從1美元開始，你有一半機會贏回3美元，一半機會收回0美元，平均而言，第一輪結束之後，你裝進口袋的現金期望值是1.5美元。

那麼，如果你在第一輪遊戲中運氣不錯的話，第二輪遊戲的兩個可能結果就會將你剛剛贏回來的3美元變成9美元或者0美元，也就是說，第二輪的平均收益是4.5美元。

數學計算結果表明，你應該一直玩下去。

但是，果真如此的話，你最終必將輸光所有的錢。

可見，有的問題有解，反而會有損無益。

 隨時準備停止斯蒂芬·格雷列特我的生命只有一次。

因此，如果我能做點兒善事，或者可以向人們表示善意，讓我現在就做吧!別讓我拖延，別讓我疏忽，因為我沒有第二次生命! 安妮·迪拉德用掉這個下午吧。

你不可能把它帶走。

 我們在前文討論了人們在生活中遭遇停止問題的具體例項，很顯然，我們大多數人每天都會遭遇這類問題，只不過表現形式各不相同。

生活中最優停止問題無處不在，有時與祕書有關，有時又與未婚夫(或未婚妻)、公寓有關。

因此我們難免會想到一個問題:進化、教育或者直覺到底能不能為我們提供最有效的策略? 乍一看，答案似乎是否定的。

十幾項研究已經得出了相同的結果，人們往往在更優秀申請者還沒亮相之前就已經草草停止。

為了更深入地瞭解這些研究成果，我們拜訪了加州大學河濱分校的阿姆農·拉波波特。

他在實驗室裡從事最優停止實驗工作已有40多年了。

 20世紀90年代，拉波波特與達里爾·希爾合作，完成了一項與經典祕書問題關係密切的研究。

在這項研究中，人們需要無數次面對祕書問題，每次申請者的人數為40或者80。

結果，人們找到最優秀申請者的總成功率相當不錯，大約為31%，與最理想的37%相去不遠。

大多數人都遵循了摸清情況再行動準則，但是有超過4/5的人出現了出手過早的情況。

 拉波波特告訴我們，他本人在生活中遇到最優停止問題時，都會想到這個現象。

例如，在尋租公寓時，他竭力控制自己希望迅速交易的衝動。

他說:“儘管我天生是一個急性子，看到第一個公寓就想租下來，但是我還是竭力控制自己。

” 但是，這種不耐煩的表現說明經典祕書問題忽略了另外一個需要考慮的因素——時間。

別忘了，在你尋覓祕書的全過程中，你沒有祕書可用。

此外，你把時間都花在面試上，自己的工作就無法完成了。

 在實驗室裡解決祕書問題時，停止時機的選擇往往過早，原因可能就在於這種成本。

希爾和拉波波特認為，如果我們假設面試每名申請者的成本等於發現最優秀祕書所產生價值的1%，那麼最優策略就會與實驗中人們從觀望階段轉變為行動階段的時間選擇正好一致。

 令人難以理解的是，在希爾和拉波波特的研究中，尋覓是不需要付出任何成本的。

那麼，人們在實驗室中的行為為什麼與尋覓需要付出成本時一致呢? 這是因為人們認為時間成本一定是存在的，而且時間成本是在人們的真實生活中產生的，與實驗如何設計沒有關係。

 因此，尋覓活動的“內在”時間成本(在最優停止模型中通常沒有得到體現)也許可以解釋人類做出的決策通常與模型的描述之間存在差異的原因。

研究最優停止的科研人員尼爾·比爾登指出:“在尋覓工作持續了一段時間之後，我們人類通常就會感到厭煩，即使理性的人也難以避免。

但是，模型很難精確地反映出這個變化。

” 不過，這並不意味著最優停止問題的重要性有所降低。

事實上，它的重要性不降反升，因為時間的流逝會把所有決策活動變成最優停止問題。

 最優停止問題的權威教科書開宗明義地指出:“最優停止理論關注的是如何選擇時機以執行特定行動的問題。

”很難想出一種更好的方法，可以簡明扼要地描述人類所面臨的狀況。

顯然，我們需要判斷何時應該買進股票，何時應該將這些股票賣出，我們還要決定何時應該開啟我們已經封藏了一段時間的葡萄酒，何時應該打斷某人，何時應該親吻某人。

 這樣看來，祕書問題最基本同時也最令人難以置信的前提條件——嚴格的連續性，即有進無退的單向行進，正好是時間自身屬性的一個體現。

就此而言，最優停止問題的這個顯性前提正好就是使其充滿活力的隱性前提。

這個前提迫使我們基於還沒親眼看到的可能結果做出決定，迫使我們在採取最優策略之後仍然願意接受非常高的失敗率。

我們永遠沒有二次選擇的機會。

我們有可能得到類似的選擇機會，但是絕不會得到完全相同的選擇機會。

猶豫不決(不作為)與行為一樣不可改變。

困在單行線上的駕車者與空間的相互關係就是我們與第四維度的關係:我們的生命真的只有一次。

 直覺告訴我們，合理的決策需要窮舉所有選擇，逐一權衡，然後從中找出效果最好的那個選擇。

但是實際上，在鐘錶嘀嘀嗒嗒的聲音中，決策活動(或者更具一般性的思維活動)的其他方面都淡化了，進一步凸顯出停止時機選擇的重要性。

∑編輯 | Gemini粉絲福利送書！想獲得此書，文章底部留言，留言點贊前五名的粉絲（24小時計），免費獲得此書！AdvertisementAdvertisement写评论取消回覆很抱歉，必須登入網站才能發佈留言。

近期文章Vue中容易被忽視的知識點2019.12.09if我是前端Leader，談談前端框架體系建設2019.12.09Spark入門（一）用SparkShell初嘗Spark滋味2019.12.08Spark入門（二）如何用Idea運行我們的Spark項目2019.12.08Spark入門（三）Spark經典的單詞統計2019.12.08Spark入門（四）Spark的map、flatMap、mapToPair2019.12.08Spark入門（五）Spark的reduce和reduceByKey2019.12.08Spark入門（六）Spark的combineByKey、sortBykey2019.12.08Spark入門（七）Spark的intersection、subtract、union和distinct2019.12.08Spark實戰尋找5億次訪問中，訪問次數最多的人2019.12.08AdvertisementAdvertisement