文/葉茲(Kit Yates)

最佳停止時機

上面提到的某些最佳化演算法,都是以大規模施行的方式來取得商業利益,似乎會讓人覺得,只有科技龍頭才有辦法使用那些背後的數學道理。但也有一些更直接簡單的演算法(雖然隱藏的數學原理很複雜),可以為日常生活帶來一些微小但重要的改善。其中一類稱為「最佳停止策略」(optimal stopping strategy),能讓人知道在決策過程中何時該停止選擇,開始實際行動。

比方來說,假設你和另一半在陌生的地方逛街,正在想該去哪裡吃晚餐。雖然你們都很餓,但你不想隨便遇到一間餐廳就進去,寧願再走走,挑間好的來吃。你自認眼光精準,一看就能知道這家餐廳的品質如何,還可以跟其他餐廳比較。你更判斷出在另一半不耐煩之前,大概有時間逛到最多十間餐廳。而且,因為你不想留下優柔寡斷的印象,所以決定只要走過,絕不回頭。

遇到這樣的問題,最好的策略是先瞭解一下大致的狀況,也就是前幾間餐廳都只是觀察,卻不走進去。其實你也可以隨便遇到一間餐廳就走進去,但既然你完全不知道這個環境的情況,能夠挑到最佳餐廳的機率就只有1/10。所以,最佳的做法是先看過幾間,接著在剩下的選擇當中,只要看到「比先前幾間都好」的選擇,就決定是它了。

圖21正是說明這樣的餐廳挑選策略。前三間餐廳是做為品質判斷的基準,單純觀察品質如何,而不會進去用餐。當你逛到了第七間餐廳,發現它比過去幾個選擇都優秀,那麼就可以在這裡停下,進去用餐。

然而,選前三間做為基準,這個數字正確嗎?在這種最佳停止時機的問題裡,重點在於到底該先觀察幾間餐廳(而不進去用餐),才能瞭解這個環境大致的情況?如果看得不夠多,就無法充分瞭解環境,但如果觀察(並排除)了太多間,可能剩下來的選擇就十分有限。

這項問題背後的數學原理十分複雜,總而言之就是:你應該觀察前37%的餐廳(在只有十間的時候,捨去算成三間),接著只要遇到比先前都優秀的餐廳,就以此為最後決定。

說得更精確一點,就是先拒絕所有可得選項個數的1/e,這裡的e是歐拉數(Euler’s number)的簡寫,[105]因為歐拉數大約是2.718,所以1/e大約是0.368,或是寫成大約37%。

圖22所說明的是:如果要從一百間餐廳當中挑選,到底該先觀察幾間餐廳,能夠讓選到最佳餐廳的可能性達到最高。我們可以料想到,如果太早做出決定,等於是盲目選擇,所以能選到最佳餐廳的機率很低;同理,如果太晚做出決定,很有可能已經錯過最佳的選擇。倘若你觀察的是前三十七個選項,就能把挑到最佳餐廳的可能性提升到最高。

只不過,如果最佳餐廳就在前37%裡怎麼辦?那不就錯過了嗎?在此要提醒各位,這種「37%」的規則本來就不是成功的保證,它只是一個機率法則,告訴你有37%的時候能夠挑出最好的餐廳。37%已經是這種情況下的最高機率,高於有十間餐廳可選而隨便選的10%,更遠遠高於有一百間餐廳可選而隨便選的1%。在選項個數愈多的時候,相對成功率也會愈高。

最佳停止時機的規則並不只適用於挑餐廳。事實上,數學家一開始是把這套規則用在「雇用問題」上。[106]假如你得依序面試一定數量的應徵者,並在面試每個人後立刻告知是否錄用,那就該採用37%的規則。先面試37%的應徵候選人(但都不錄用),以此做為基準。而在接下來,只要出現比先前都優秀的應徵者,就直接錄用。

我家附近的超市有十一個結帳台,我也會先走過前37%(四個)結帳台,觀察現在的隊伍有多長,接著只要看到更短的隊伍,就排那一排。

如果我和朋友出門夜歸,打算趕上最後一班列車,但乘客似乎不少,而我們又希望能找到空位最多的車廂,好讓我們坐在一起;這時也可以運用37%的規則。要是遇到的列車總共有八節車廂,我們就會先走過前三節,觀察空位的狀況,接著在空位比先前都多的車廂坐下來。

活用37%法則

以上的場景雖然已經盡量舉實際的例子,但還是有一部分略為牽強,再修正一下或許會更加貼近現實。例如在觀察餐廳的時候,如果發現有一半都沒有空桌了,你該怎麼辦?在這種時候,很顯然該減少拒絕的餐廳。所以,不要再堅持觀察完前37%,而是觀察了前25%之後,一出現比先前都優秀的選項時,就該做出決定。

像是在搭上末班列車的時候,如果有時間可以回頭走進剛才經過的車廂,但車廂有50%的機率坐滿了乘客,那又該怎麼選擇?可以回頭,代表選項變多、也有餘裕可以挑久一點,所以此時就可以先觀察並拒絕前61%的車廂,接著選擇下一節最空的車廂。當然,你得在列車跑掉之前上車才行。

此外,不管是想知道賣房的最佳時機,或是該離電影院多遠才最有機會找到不必走太久的車位,這些問題都有相關的最佳停止時機演算法。只不過,隨著條件愈來愈貼近現實,相關的數學也會愈來愈複雜,無法再用一個簡單的百分比來表示。

甚至,還有一套最佳停止時機演算法,算的是你應該先跟多少人約會,再決定你的最佳終生伴侶。首先,你得判斷在自己定下來之前,大概可以交幾個男女朋友。假設你大概一年交一個,那麼從十八歲到三十五歲之間,就有十七人可供選擇。這時,根據最佳停止時機法則,你應該先遊戲人間六年到七年(大約是十七年的37%),觀察自己可以遇上怎樣的對象。接著,只要出現比過去都優秀的選擇,你就該認定這是今生的伴侶。

對於像這樣由一套預定規則來支配自己的愛情生活,很多人都會感到懷疑。如果在那前37%裡,真的有很合得來的人怎麼辦?難道真的要為了執行這套求愛演算法,就狠心放下對方嗎?如果你自己遵守了一切規則,但認定是最佳選項的對方卻不認為你是最佳選項,又該怎麼辦?如果走到一半,發現自己喜歡的條件不一樣了,又要怎麼辦?

還好,講到內心、或是其他更明顯的數學最佳化問題時,我們並不一定需要找到絕無僅有的真命天子/天女、最好的解決方案。世界上可能有很多人都會跟我們處得不錯,能讓我們有幸福的一生。最佳停止時機的策略,並不會提供所有人生問題的答案。

雖然演算法潛力無窮,能夠協助我們處理日常生活的許多面向,但絕不是所有的問題都能用演算法找出最佳解答。

我們雖然可以利用演算法來簡化、加速單調乏味的任務,但風險也常常伴隨而來。因為演算法包含輸入、規則和輸出這三個面向,也就代表有三個可能出錯的地方。就算使用者確信所用的規則完全符合自身需求,只要輸入不小心,或是輸出不合規範,就有可能造成災難。

美國的網路商場賣家福勒(Michael Fowler)身受其害,他曾在演算法的啟發之下推出一項爆紅的零售企畫,卻在2013年遭受重挫。追根究柢來說,整件事可以追溯到第二次世界大戰時的英國。

註釋
[105] 歐拉數起源於十七世紀,提出這項概念的是瑞士數學家雅各.白努利(Jacob Bernoulli),當時他正在研究複利問題。(第7章曾談到一位數學生物學家丹尼爾.白努利在流行病學上的成就,而雅各就是丹尼爾的伯伯。)我們曾在第1章談過複利的概念,也就是會把利息加回本金,以利滾利。雅各.白努利想知道計息頻率會如何影響每年利息的總額。
為了計算簡單,假設我們在新年元旦將1英鎊存進銀行,年利率100%。每經過固定期間,銀行就會將利息撥入帳戶,並轉為下一期的本金。在這個條件下,如果銀行決定一年計息一次,利息會有多少?到了年底,我們會收到1英鎊的利息,但已經沒有時間再以利滾利,所以最後結果就是2英鎊。但如果改成每六個月計息一次,在年中就會以50%的年利率計息一次,於是帳戶裡共有1.5英鎊。等到年底會再重複一次這個過程,於是帳戶裡的1.5英鎊再以50%的年利率計息一次,總額來到2.25英鎊。
計算複利的頻率愈高,帳戶到年底的總額就會愈高。舉例來說,如果是每季計息、共4次,最後將會有2.44英鎊;每月計息、共12次,最後將會有2.61英鎊。白努利指出,如果以持續複利計算(也就是讓計息期數頻率幾乎無窮高,但除以期數後的利率幾乎無窮低),年底帳戶能得到的最高值是2.72英鎊,也就是剛好有歐拉數「e」這麼多。
[106] Ferguson, T. S. (1989). Who solved the secretary problem? Statistical Science, 4(3), 282–89. https://doi.org/10.1214/ss/1177012493
Gilbert, J. P., & Mosteller, F. (1966). Recognizing the maximum of a sequence. Journal of The American Statistical Association, 61(313), 35. https://doi.org/10.2307/2283044

※ 本文摘自《攸關貧富與生死的數學》,摘自第六章〈永不停歇的改善:從演化到電子商務,展現演算法的無限潛力〉,立即前往試讀►►►

  • 用Line傳送