決斷的演算（三版）

名人推薦：▎推薦人士與各界好評——

洪士灝／台灣大學資訊工程系教授 　
賴以威／數感實驗室共同創辦人
林錦宏／高醫大心理系助理教授 　
鄭國威／泛科知識公司知識長
▎推薦人士與各界好評——

洪士灝／台灣大學資訊工程系教授 　
賴以威／數感實驗室共同創辦人
林錦宏／高醫大心理系助理教授 　
鄭國威／泛科知識公司知識長
黃貞祥／清華大學生命科學系助理教授　
雷浩斯／專職投資人及投資講師
（「得到」說書App萬維鋼老師書評介紹《指導生活的算法》 ）

►我一直期待有書能把運算模型和人類心理學結合起來，這本...

◎第十一章　賽局理論

►奈許，就是賽局達到均衡
你知道規則，我也知道……　我們了解這個遊戲，我們準備參與。
──英國歌手瑞克．艾斯里（Rick Astley），上文引自〈Never Gonna Give You Up〉一曲

賽局理論涵括各種合作與競爭情境，但這個領域的起源相當類似撲克牌手對決：兩方互相角逐，一方的獲益就是另一方的損失。分析這些賽局的數學家試圖從中找出均衡（equilibrium），也就是一套可供雙方遵循、並且讓雙方知道對方的行動後，也不想改變本身行動的策略。
這種狀態稱為「均衡」是因為它很穩定，也就是雙方即使再怎麼考慮，都不會改變自身選擇。我用你的策略考慮後，很滿意我自己的策略；你用我的策略考慮後，也很滿意你自己的策略。
舉例來說，在剪刀石頭布中，均衡的意思是完全隨機從這三種
手勢出一種，出每種手勢的機率大約是 1/3。使這個均衡穩定的因素是，如果雙方都採取這種1/3-1/3-1/3策略，那麼對雙方而言，除了堅持下去之外別無更好的方法（如果我們試著多出幾次石頭，對手很快就會注意到，開始經常出布，這樣又會使我們多出幾次石頭，如此不斷循環，最後雙方都會回歸原本的1/3-1/3-1/3策略）。
數學家約翰．奈許（John Nash）於1951年證明，所有雙人賽局至少有一個均衡狀態。這項重大發現在賽局理論領域影響深遠，也讓奈許獲頒1994年諾貝爾經濟學獎（並促成《美麗心靈》〔A Beautiful Mind〕這部講述奈許生平的小說和電影問世）。現在這樣的均衡經常被稱為奈許均衡，也就是前述的撲克牌手丹．史密斯想追求的狀況。
從表面上看來，雙人賽局一定存在奈許均衡這一點，似乎可以讓我們擺脫撲克牌和許多類似競爭中，常見的鏡廳遞迴現象。我們感到自己捲入遞迴漩渦時，一定有機會脫離對手的掌控，尋求均衡，發現最佳策略，採取合理的行動。在剪刀石頭布中，如果你知道隨機出拳其實就是長期而言的不敗策略，就不用花力氣觀察對手的表情，猜測對手下一手可能出什麼拳了。
更籠統地說，奈許均衡能夠預測任何一組規則或誘因的穩定長期結果，因此它能做為預測和擬定經濟政策及一般社會政策的重要工具。諾貝爾獎得主羅傑．麥爾森（Roger Myerson）曾說，奈許均衡「在經濟學和社會科學領域擁有基本且廣泛的影響力，相當於DNA雙螺旋的發現在生物學領域中的影響力。」
然而，電腦科學把這件事變複雜了。大致上說來，數學研究的是事實，電腦科學研究的是複雜性。而我們已經知道，如果一個問題是難解問題，那麼單單取得解答是不夠的。
賽局理論雖然讓我們知道有均衡存在，卻未說明這個均衡是什麼，也沒有說明如何達到均衡。加州大學柏克萊分校電腦科學家克里斯托斯．帕帕迪米崔歐（Christos Papadimitriou）曾在作品中提到，賽局理論「通常會預測參與者的均衡行為，但沒有說明要怎麼達到這狀態，但這通常是電腦科學家最看重的事。」史丹佛大學的提姆．羅夫加爾登（Tim Roughgarden）同樣不滿意奈許僅是證明均衡必定存在。他說：「好。不過我們是電腦科學家，對吧？給我們一些可以運用的東西。不要只是告訴我們有這東西，請告訴我們如何找到它。」因此原本的賽局理論衍生出演算法賽局理論，也就是說，研究賽局的理論性理想策略，轉變成研究機器（和人）如何擬定賽局策略。
思考太多關於奈許均衡的問題，其實很快就會讓我們陷入運算困難。二十世紀末，判斷某個賽局是否具有一個以上的均衡，或某個均衡是否給某個參與者特定報酬，或是某個均衡是否必須採取某個行動等，都已經確定是難解問題。然後從2005年到2008年，帕帕迪米崔歐等人證明，純粹尋找奈許均衡同樣是難解問題。
剪刀石頭布這類簡單賽局乍看之下，或許有明確的均衡，但現在已經知道，在複雜程度接近真實世界的賽局中，我們不能認為參與者理所當然一定能發現或達到賽局的均衡。因此這也表示，賽局設計者不
一定能藉助均衡來預測參與者的行為。這個嚴酷的結果涵括的範圍相當廣：奈許均衡是經濟學理論建立模型及預測市場行為的重要方法，因此擁有崇高地位，但這個地位可能名過其實。帕帕迪米崔歐解釋：「如果一個均衡概念無法有效運算，那麼它預測理性參與者行為的可信度，將會大打折扣。」MIT的史考特．艾隆森（Scott Aaronson）也同意這一點，他說：「就我看來，如果奈許均衡存在的定理，被視為和自由市場與政府介入的爭議有關，那麼尋找這類均衡的定理（難解）也應該視為有關。」參與者找得到奈許均衡時，奈許均衡的預測能力才會造成影響。eBay前研究長卡馬爾．簡恩（Kamal Jain）曾說：「如果你的筆記型電腦找不到（奈許均衡），那麼整個市場也都找不到。」
不採取「均衡」作法的代價就算是我們能達到均衡的時候，單單只是穩定還不夠好。這點看來或許有點自相矛盾，但均衡策略（也就是所有參與者都不願意改變行動的狀態），不一定是可讓所有參與者獲得最佳結果的策略。說明這點的絕佳範例，是賽局理論中最著名、最刺激，也最惹爭議的雙人賽局：囚徒困境（prisoner’s dilemma）。
囚徒困境的狀況是這樣的：假設你和另一個共犯搶銀行後遭到逮捕，被關在不同牢房，現在你必須決定是要彼此「合作」，也就是保持緘默、打死不認，還是要背叛同伴，向警方告發對方。你知道如果你們彼此合作，保持緘默，警方沒有足夠證據可以判你們有罪，因此兩人都可以平安離開，瓜分贓款，可能是每人50萬美元。但如果你們其中一人背叛並告發對方，而對方沒有招供，則告密者就可以平安離開，獨吞100萬美元，拒絕招供的一方則會成為這樁案子唯一的罪犯，遭判 10年徒刑。如果你們互相告發，那麼兩人將共同承擔罪名和刑期，每人坐牢5年。
問題就在於：無論你的共犯怎麼做，你都應該背叛對方。如果你的共犯告發你，那麼你告發共犯將可少坐5年牢，因為有人可以跟你分攤刑期，你不用自己承擔所有罪刑（坐牢10年）。如果你的共犯保持緘默，那麼告發他將可讓你獨吞這100萬美元，不用跟對方分贓。無論如何，不論你的共犯怎麼做，你背叛都比合作來得有利，不這麼做的話，無論對方怎麼做，都一定會使你的處境更糟。
事實上，這使得背叛不僅成為均衡策略，還成為「主導策略」（dominant strategy）。主導策略是因應對手各種可能策略，從而脫離對方的掌控，完全避免遞迴的最佳手段。主導策略的力量非常強大，但現在我們遇到了矛盾。如果每個人都很理性，採取主導策略，那最後你們兩人都會坐五年的牢。跟逍遙法外和白花花的 50萬美元相比，這個結果對每個人而言都差了很多，這到底是怎麼回事？
這是傳統賽局理論中的重要見解之一：對一群依據自身利益採取理性行動的參與者而言，「均衡」或許不是最好的結果。演算法賽局理論依據電腦科學的原理，採用了這個見解並加以量化，創造出「自主行為代價」（price of anarchy）這種度量。自主行為代價可衡量合作和競爭兩者間的差距（合作指集中設計或協調的解決方案，競爭指所有參與者各自試圖取得對自己最好的結果）。在囚徒困境這樣的賽局中，這個代價其實是無限大：提高贓款金額和拉長刑期，可能會使兩種結果間的差距變得更大，即使主導策略不變也一樣。對於參與者而言，不合作所造成的痛苦沒有極限。但演算法賽局理論學者發現，在另一些賽局中，自主行為代價其實沒有那麼糟。
流量就是個不錯的例子。流量可以指每天通過擁擠車流到公司上班的通勤者，也可以指在網際網路上不斷收發TCP封包的路由器，系統中的每個成員只想取得對自己最有利的結果。駕駛人不在乎路線，只要最快到達就好；路由器也只想花最少的力氣收發封包，但在這兩種狀況中，這種想法都可能造成重要通道過度壅塞，進而影響所有人。不過影響程度究竟有多大？提姆．羅夫加爾登和康乃爾大學的伊娃．塔爾多斯（Éva Tardos）於2002年證明，這種「自私路徑」法的自主行為代價居然只有4/3 。也就是說，各行其是只比毫無阻礙地順利行進慢33%。
羅夫加爾登和塔爾多斯的研究成果，對有形車流的都市規劃和網路基礎建設，都造成深遠的影響。舉例來說，自私路徑規劃的自主行為代價很低，或許可以解釋為什麼網際網路沒有中央主管機關負責管理個別封包路徑，也能順利運作。即使可能執行這樣的協調，狀況也好不了多少。
在人類的交通方面，自主行為代價甚低有好處、也有壞處。好處是缺少中央協調最多只會讓通勤時間增加 33%。而另一方面，如果你期待有網路連線的自動駕駛汽車可以帶你進入交通的天堂，那你可能要失望了，因為現在自私駕駛人各行其是的情形，其實已經相當接近最佳狀態。自動駕駛汽車確實應該能減少行車事故，或許也能讓汽車行駛得更近，兩者都可加快車流。不過說到壅塞程度，自主行為的壅塞程度只有經過完美協調後的4/3，這代表經過完美協調後的壅塞程度只有現在的 3/4。這有點像是詹姆士．布蘭齊．卡貝爾（James Branch Cabell）的著名詩句：「樂觀的人說，我們生活在最好的時代，悲觀的人則害怕這句話是真的。」由規劃專家和整體需求來解決壅塞問題，一定比依據人類或電腦、自私或合作的個別駕駛人來決定更好。
量化自主行為代價讓這個領域擁有具體及嚴密的方法，來評估非集中系統的優缺點，這對人類本身參與賽局的許多領域造成廣泛影響（參與者可能知道、也可能不知道）。自主行為代價很低，代表這個系統無論是否細心管理，運作狀況都和放任不管差不多。另一方面，自主行為代價很高，則代表如果細心協調，狀況就可能好轉，但如果沒有任何介入，就可能造成災難。囚徒困境顯然就屬於後者。可惜的是，世界上的許多重要賽局都是這樣的。

►公有地悲劇
1968年，生態學家賈瑞特．哈定（Garrett Hardin）研究雙人囚徒困境，把規模擴大到涵括一個農莊中的所有成員。哈定請讀者想像農莊裡有一塊「公有地」，這片草地可讓每個人放牲口吃草，但容量有限。
理論上，所有村民只能放一定數量的牲口，讓每個人的牲口都有草可吃。但實際上多放一點牲口對自己有利，影響則似乎很小，不會造成嚴重後果。然而如果每個人都這麼想，都多使用一點點公有地，就會造成可怕的均衡：草地完全遭破壞，使大家的牲口都沒草可吃。
哈定把這種狀況稱為「公有地悲劇」（tragedy of the commons），後來這成為經濟學家、政治學家以及環境運動，用於觀察汙染和氣候變遷等大規模生態危機的主要工具。卡內基美隆大學電腦科學家及賽局理論學者艾弗瑞姆．布魯姆（Avrim Blum）說：「我小時候有一種汽油叫做含鉛汽油。含鉛汽油便宜了一角左右，但它會汙染環境⋯⋯如果每個人都這麼做，那麼你使用有鉛汽油對你個人（健康）造成的影響，會增加多少？其實沒有很多。這就是囚徒困境。」對企業和國家而言，這類狀況同樣成立。日前有個新聞標題一語道破了這個問題：「少用化石燃料才能維持氣候穩定，但應該叫誰少用？」每個企業（某個程度上也包括每個國家）最好都能比其他企業或國家不顧後果一點點，以便維持競爭力。但如果大家都不顧後果，就可能破壞地球，最後討不到便宜：大家都無法取得想攫取的經濟優勢。
這類賽局的想法非常普遍，我們不需要特別觀察不當行為，也能發現它舉目可見。我們只要一不留意，就很容易形成惡性均衡。怎麼會這樣呢？只要看看公司的休假規定就好。美國人的工時是全世界最長的。經濟學家曾說：「在美國，工作的價值最高，但休閒的價值最低。」美國很少有法律規定雇主必須提供休假，甚至有些美國員工即使有假也不想用。近年一項研究指出，美國員工平均只用掉一半假期，更有15%完全沒有休假。
目前（兩個作者居住的）舊金山灣區正在對休假規定進行根本的典範轉移，試圖改變令人遺憾的現狀。這個轉移用意良好，但是徹底失敗。它的前提聽起來很正常：與其給予每個員工固定天數的假期，又要浪費人資的人力確認每個人的休假是否超過限制，何不讓員工自由管理？何不給員工無限的假期？目前為止的個案報告褒貶不一，但從賽局理論的觀點看來，這種作法是個惡夢。理論上，所有員工都希望盡量多休假，但也希望比其他人少休一點假，以便獲得忠誠、認真、負責的評價（這樣比較容易升遷）。每個人都以其他人為基準，比這個基準少休一點。
這個賽局的奈許均衡是0。軟體公司Travis CI執行長馬希亞斯．梅耶爾（Mathias Meyer）寫道：「許多人不敢休假，是因為不想被視為休最多假的人，這是少者獲勝的比賽。」
這是公有地悲劇發展到極致的結果。這類狀況在組織間的殺傷力，與在組織內部不相上下。假設某個小鎮上有兩家小店，兩位店東可以任意決定每天都開店，或是一星期只開六天，星期天休息，跟朋友和家人共度。如果兩人都選擇休息一天，就可以維持原本的市場占有率，壓力也比較小。然而如果有一位店東決定每天開店，就會招來更多顧客，這其實是從對方手中搶來客戶，因此會威脅到對方的生計。這時奈許均衡是每個人每天都工作。
2014年年底，這個問題在美國引發熱戰。當時許多零售商不想把市占率拱手讓給在感恩節後的購物季搶先開店的對手，因此相繼破壞這個糟糕的均衡。當時《國際財經時報》報導：「商店比以往更早開門。」梅西百貨決定比前一年提早兩個小時開店，Target隨之跟進。Kmart在感恩節當天早上六點就開店，而且連續營業42小時。
那麼，如果我們發現自己身陷這類狀況（無論是雙人的囚徒困境，或是多人的公有地悲劇），該怎麼辦？就某種意義而言，應該什麼都不做。令這類惡性均衡維持穩定（使它們均衡）的，正是最糟糕的特質。
基本上我們無法從內部改變主導策略，但這不表示這類惡性均衡無法矯正，只表示我們應該朝外尋求解決方案。

►機制設計：改變賽局
不要氣參加者，要氣就氣比賽。──饒舌歌手 Ice-T
不要再聯合外人對付家人，絕對不要。──電影《教父》

在許多關於人類合作天性的辯論和爭議中，囚徒困境都是焦點，但倫敦大學學院賽局理論學家肯．賓摩爾（Ken Binmore）認為，這類爭議有許多已經走偏。他認為，「說囚徒困境證明人類合作有多重要是完全錯誤的。相反地，在它呈現的狀況中，人類完全不應該合作。」〔36〕、〔37〕
如果賽局規則迫使我們提出不好的策略，或許我們不應該試圖改變策略，而應該試圖改變賽局。如此一來，我們將進入賽局理論的另一個分支：「機制設計」（mechanism design）。賽局理論探討在一定規則下會出現什麼行為，機制設計（有時也稱為「逆向賽局理論」）則反其道而行，探討什麼規則會產生我們希望看到的行為。如果說賽局理論呈現的結果違反直覺（例如均衡策略或許對參與者而言合理，但對所有人都不好），則機制設計呈現的結果可能更是如此。
我們把你和搶銀行的同夥放回牢房，再次經歷囚徒困境，但增加一個重要條件：教父。現在你跟同夥都是某個犯罪集團的成員，而且集團老大已經明講，誰敢告發同伴他就做掉那個人。這個賽局報酬變更限制了你能採取的行動，但反而使結果更可能朝對你和同夥都好的方向發展。由於背叛現在變得比較不吸引人（這是客氣的說法），所以兩個囚徒都傾向合作，而且雙方都能帶著 50萬美元逍遙法外，不過當然得上繳一部分給老大。
此時我們可以採取一個違反直覺、但效果極佳的作法：惡化所有結果（一是死掉，一是損失部分錢財），但最後讓各方都過得更好。

◎第十一章　賽局理論

►奈許，就是賽局達到均衡
你知道規則，我也知道……　我們了解這個遊戲，我們準備參與。
──英國歌手瑞克．艾斯里（Rick Astley），上文引自〈Never Gonna Give You Up〉一曲

賽局理論涵括各種合作與競爭情境，但這個領域的起源相當類似撲克牌手對決：兩方互相角逐，一方的獲益就是另一方的損失。分析這些賽局的數學家試圖從中找出均衡（equilibrium），也就是一套可供雙方遵循、並且讓雙方知道對方的行動後，也不想改變本身行動的策略。
這種狀態稱為「均衡」是因為它很穩定，也就是雙方即使再怎麼考慮，...

◎前言：為什麼我們能跟電腦學決策？

想像你正在舊金山找房子。這城市可說是全美最難找到房子的地方，有繁榮的高科技業，加上嚴格的分區使用法規，因此房價跟紐約一樣昂貴，很多人認為甚至不輸給紐約。新物件出現沒多久就下架，房地產公開說明會人山人海，往往得私下先塞訂金支票給屋主才買得到。
由於市場如此熱絡，很難容許理性消費者先蒐集資料，深思熟慮後才下決定。四處閒逛或透過網路買屋的人，可以比較許多選擇後再下決定，但想在舊金山買房子的人，要不就買下眼前這棟房子，拋下其他選擇，要不就馬上走人，不再回頭。
為了簡化起見，我們姑且假設你只想盡可能提高買到最好房子的機率。你的目標是把在「錯過好機會」和「說不定還有好機會」之間徘徊的機率降到最低。你立刻發現自己陷入兩難：如果沒有判斷基準，要怎麼知道某棟房子是不是最佳選擇？但如果看過的房子不夠多，又怎麼知道判斷基準在哪？你取得的資訊越多，越能掌握真正的好機會，但在此之前錯過好機會的機率也越高。
那麼你該怎麼做？倘若蒐集資訊反而可能不利，那麼該如何做出明智決定？這種狀況十分殘酷，簡直可以說是矛盾。
大多數人面臨這類問題時，直覺上通常認為必須在取捨間取得某種平衡，得看過夠多的房子才能建立標準，再依據標準找出想要的房子。這種權衡概念非常正確，然而大多數人沒辦法明確說出平衡點在哪。所幸這確實有明確答案：
是37％。
如果你希望達成買到最佳房子的最佳機率，請把總時間的37％拿來看房子（如果打算花一個月找房子，那就是十一天）。把清單留在家裡，單純用來設定標準。但是花了37％的時間後，就要準備出手，只要一發現比已經看過的房子更好的選擇就買下來。這不只是尋找和放棄之間的平衡點，也是經過驗證的最佳解決方案。
我們之所以知道答案，是因為找房子屬於數學中的「最佳停止問題」。37％法則定義出一連串解答這類問題的簡單步驟，電腦科學家稱之為演算法。其實最佳停止問題可以用來解決生活中的許多狀況，找房子只是其中一例。生活中我們經常遇到選擇或放棄一連串選項的情形，比方說：要在停車場繞幾圈才找得到車位？投資高風險事業要多久才會開始回收？賣房賣車時要忍耐多久才能等到更好的價錢？
還有一種更難抉擇的狀況亦屬此類問題，那就是約會。最佳停止是連續單偶制的科學原理。
簡單的演算法不僅能協助你找到好房子，還適用於遭遇最佳停止問題的各種狀況。
我們每天都在跟這類問題纏鬥不休（只不過比起停車，詩人花比較多墨水描述愛情的磨難），有些狀況也真的很折騰。但其實沒必要這麼糾結，有些問題數學已經解決了。心急如焚的房客、駕駛人和忐忑不安的求婚者，其實都沒必要煩惱；他們不需要治療師，只需要演算法。治療師可以教他們如何避免過於衝動和過度思考；演算法則能明確告訴他們，這個平衡點就是37％。

＊＊＊＊＊＊

由於我們生活的空間和時間都有限，每個人都遭遇到一類問題。在一天或十年中，我們應該做什麼、或應該不做什麼？應該容忍什麼程度的混亂？什麼樣的秩序算是過度？新事物和心頭好各佔多少比例，才能使生活最讓人感到滿足？
似乎只有人會面臨這類問題？其實不然。半個多世紀以來，電腦科學家一直在探究這類日常困境，有時還試圖解決，像是：處理器該如何分配它的「注意力」，以最少時間執行使用者要它做的工作，同時盡量少做白工？它什麼時候應該轉而處理不同工作，一開始又應該接受幾項任務？怎麼運用有限的記憶體資源最好？它應該蒐集更多資料，或是依據已有的資料採取行動？
人類要把握每一天已經很不容易，電腦卻能輕鬆寫意地把握每一毫秒。電腦的工作方式可以帶給我們許多啟發。
討論演算法對人類生活有何助益似乎有點奇怪。說到「演算法」，許多人想到的是大數據、大政府和大企業神祕難解的算計，這類算計在現代世界基礎建設中的比重越來越大，但稱不上實用智慧或人生指南。不過演算法其實是解決問題的一連串步驟，而且範圍比電腦更廣，歷史也更悠久。早在機器使用演算法之前，人類就開始使用它們了。
「演算法」這個詞，源自撰寫手算數學書的九世紀波斯數學家阿爾花拉子模（al-Khwārizmī）。他寫的書名為《還原和對消的規則》（al- Jabr wa’l-Muqābala），其中的al-jabr後來演變成代數（algebra）。然而目前已知最古老的數學演算法，其實早於花拉子模的著作。有一塊巴格達附近出土、歷史長達四千年的蘇美黏土板，上頭就記載了長除法。
不過用得上演算法的領域不只數學。你參考食譜做麵包、依照圖樣打毛衣，或是以一定方式用鹿角末端敲擊燧石，在燧石上形成尖銳邊緣（這是製作精細石器的重要步驟），都是依循演算法在做事。早從
石器時代開始，人類科技中就蘊含著演算法。

＊＊＊＊＊＊

本書將探討人類演算法的設計概念，也就是：針對每天面臨的挑戰尋找更好的解決方案。把電腦科學解決問題的方法套用到日常生活上，會影響許多層面。首先，演算法能提供實用且具體的建議，協助解決特定問題。最佳停止問題告訴我們，何時該大膽跳過、何時又該留意機會。開發與利用取捨告訴我們，如何在嘗試新事物和享受喜愛的事物間找到平衡點。排序理論教我們如何（以及是否應該）整理辦公室。快取理論教我們如何把物品收進櫥櫃。排程理論則教我們如何安排工作。
到了下一個階段，電腦科學告訴我們一套字彙來了解這些領域中更深入的原理。卡爾．薩根（Carl Sagan）曾說：「科學不只是知識，更是一種思考方式。」即使是混亂得難以進行嚴謹數值分析或有現成答案的狀況，運用直覺和化簡問題後加以思考所得到的概念，也能讓我們了解關鍵問題並獲得進展。
更廣泛地說，以電腦科學的眼光看問題，有助於我們了解人類心智的特質、合理性的意義，並且探究一個最古老的問題：人類如何求生。把認知當成「解決環境造成的基本運算問題的方法」仔細探討，可能徹底改變我們對人類理性的看法。
就算電腦科學真能教我們如何思考以及該怎麼做好了，但我們想照著做嗎？看看科幻片裡的人工智慧和機器人，你該不會真的想要像它們那樣過活吧？說到研究電腦內部運作可能教我們如何思考、下決定、該相信什麼以及怎麼做好，許多人不只會把它想得太簡單，實際上是會想錯方向。
部分原因是，說到電腦，我們想到的是冰冷的機械化確定性系統——機器套用死板的演繹邏輯，點滴不漏地羅列所有選擇，琢磨出正確答案，無論必須思考得多久、多辛苦。的確，最早構思出電腦的人就希望電腦是這樣：艾倫．圖靈（Alan Turing）定義中的運算就像數學家一樣，仔細執行一連串冗長運算，得出萬無一失的正確解答。
因此說來你或許會驚訝──現代電腦面臨難題時，其實不是這麼做的。當然，直截了當的計算對現代電腦而言輕而易舉。跟人類交談、修復損壞的檔案或下贏一盤圍棋等，這類沒有明確規則、缺少必要資料，或是必須考慮多如繁星的可能才能找出正確解答的問題，才是電腦科學最大的挑戰。研究人員為了解決極端困難的問題而開發的演算法，已經使電腦不再需要依賴繁重的計算。相反地，執行實際工作必須接受機率，以時間換取精確性，還要懂得運用近似法。
電腦解決真實世界問題的能力越來越強，不僅提供演算法給人運用到生活上，還定下更好的標準讓我們得以比較人類認知本身。近十幾二十年，行為經濟學主張：人類既不理性又容易犯錯，主因是人類大腦結構缺陷重重且各不相同。這個妄自菲薄的說法日益流行，但仍有些問題有待探討。舉例來說，為什麼即使是四歲小孩，執行視覺、語言和因果推論等認知任務時，
依然能超越超級電腦？
電腦科學衍生的日常問題解決方案，則對人類心智提出完全不同的看法。它們認為生活本就困難重重，人們犯下的錯誤透露的，是問題本身的困難之處，而非人類大腦不可靠。用演算法思考世界，學習我們所面
臨的問題的基本結構、以及其解決方案的屬性，能讓我們了解人類其實已經很了不起，同時更加理解我們所犯的錯。
事實上，人類經常面對電腦科學家傷透腦筋的許多難題。我們經常得克服不確定性、時間限制、資訊不足和變動快速的世界，做出決定。對於當中的某些情況，即使是最尖端的電腦科學，也還沒找出高效率又永遠正確的演算法；而某些情況則根本不存在這樣的演算法。
然而即使在尚未找到完美演算法的領域，一代代電腦科學家和棘手真實世界問題纏鬥多年後，也得出了許多心得。這些得來不易的規則違反我們心目中的合理性，聽起來也不像數學家描述世界的那些條理分明的嚴密規則。這些規則說：不一定要考慮所有選擇，不一定非得追求看來最好的結果，偶爾可以製造混亂。看到紅綠燈就等一下。相信直覺，別思考太久。放鬆，拋個硬幣。寬恕，記住這個教訓就行。誠實對待自己。
依據電腦科學知識過生活說來沒那麼糟，何況它有證據支持─許多忠告可是無憑無據呢

＊＊＊＊＊＊

設計供電腦使用的演算法，原本就是介於兩個學科之間的專業──它是數學與工程學的奇特混合體，因此設計供人類使用的演算法自然也沒有明確隸屬哪個學科。今天，演算法設計不僅必須藉助電腦科學、數學和工程學，還要藉助統計學和作業研究等。我們思考為機器設計的演算法與人類心智的關聯時，也需要參考認知科學、心理學、經濟學和其他學科。
我們作者都很熟悉這個跨學科領域。布萊恩念過電腦科學和哲學，念研究所時主修英文，後來的工作則跨這三個領域。湯姆念的是心理學和統計學，後來成為加州大學柏克萊分校教授，花很多時間研究人類認知和運算間的關係。不過沒有人通曉為人類設計更佳演算法的所有相關領域，因此我們在尋找過好生活的演算法時，訪問了近五十年來最知名演算法的設計者。他們個個頭腦頂尖，我們問他們，他們的研究對自己的人生有何影響，例如尋找配偶到整理襪子等等。
從下一章開始，我們將探討電腦和人類面臨的最大挑戰：如何運用有限的空間、有限的時間、有限的注意力、未知的事物、不完整的資訊，以及無法預知的未來，並且如何輕鬆而自信地做到；以及如何在此同時
與其他目標相同的人溝通。我們將會了解這些難題的基本數學結構，以及工程師如何教電腦發揮最大效用（他們的方式往往出乎意料）。我們還將了解人腦如何運作，了解它如何處理相同問題和克服相同限制，這些方法與電腦的方法不同卻關聯極深。最後，我們不僅將深入了解各類日常問題、以全新方式觀察人們遭遇的各種困境背後的美麗結構、認識人類和電腦的解決方式融合程度極高，還將獲得更深刻的東西──我們會有描述周遭世界的新語彙，並且有機會重新認識自己。

◎前言：為什麼我們能跟電腦學決策？

想像你正在舊金山找房子。這城市可說是全美最難找到房子的地方，有繁榮的高科技業，加上嚴格的分區使用法規，因此房價跟紐約一樣昂貴，很多人認為甚至不輸給紐約。新物件出現沒多久就下架，房地產公開說明會人山人海，往往得私下先塞訂金支票給屋主才買得到。
由於市場如此熱絡，很難容許理性消費者先蒐集資料，深思熟慮後才下決定。四處閒逛或透過網路買屋的人，可以比較許多選擇後再下決定，但想在舊金山買房子的人，要不就買下眼前這棟房子，拋下其他選擇，要不就馬上走人，不再回頭。
為了簡...

◎前言：為什麼我們能跟電腦學決策？
演算法的本質是「解決問題的一連串步驟」，人類面臨的許多挑戰跟電腦是一樣的：如何運用有限的空間、有限的時間、有限的注意力、未知的事物、不完整的資訊，以及無法預知的未來，並且如何輕鬆而自信地做到；以及如何在此同時與其他目標相同的人溝通。人類和電腦的解決方式融合程度極高，電腦科學不只能協助我們簡化問題以取得進展，甚至能提供具體的解決方法。本書將介紹前述難題的基本數學結構，以及工程師如何教電腦發揮最大效用，並了解人腦如何克服相同限制。作者訪問了近五十年來最知名演算法的設計者，談談他們的研究對自己的人生有何影響，以及他們怎麼將所學用於生活。

◎第一章　最佳停止點——什麼時候該見好就收？
►祕書問題　►為什麼是37％？　►把握最佳伴侶
►孰優孰劣一目了然──完全資訊賽局　►什麼時候賣出房子最好？
►什麼時候該停車？　►何時應該見好就收？　►隨時準備停止
盡量羅列選項，小心權衡後選出最好的一個，才是理性決策？實際上由於時間有限，決策過程最重要的面向是：何時應該停止。聘人、租屋、找車位、賣房子，以及尋覓伴侶和投資獲利時見好就收等，都是要在選項逐一出現時做出最佳選擇，它們真正困擾人的是可以考慮的選項有多少。依各狀況條件不同（比如能否吃回頭草、是否有明確標準），這章解釋了37％法則、思而後行法則、臨界值法則等，教你如何避免太早決定或找太久，以及何時該降低或提高標準、還有標準該調整多少……

◎第二章　開發與善用——嘗試新歡？還是固守舊愛？
►開發與善用　►把握時間　►贏錢繼續玩、輸錢換一台
►吉廷斯指數　►遺憾與樂觀　►網路上的土匪
►用演算法審視臨床試驗　►變化不定的世界
►開發……　►……以及善用
開發是蒐集資料，它能提高發現最佳選擇的機會；善用則是運用現有資訊，取得已知的良好結果，兩者各有利弊。人們大多把決策視為彼此孤立，每次分別尋找期望值最高的結果。其實決策極少是孤立的，如果你思考的是日後面對相同選項時要怎麼做，那麼權衡是要開發還是善用，就非常重要。本章以電腦科學中最能體現這兩者之矛盾，名稱取自吃角子老虎機的「多臂土匪問題」，闡述應該如何隨時間而改變目標，並且說明為何合理的行動過程多半未必會選擇最好的目標。

◎第三章　排序——依照順序排列
►排序的大用處　►排序的苦惱　►大O記號──衡量最差狀況的標準
►兩種平方：氣泡排序和插入排序　►破除平方障礙：各個擊破
►比較之外：贏過對數　►亂得有理─照順序排好之後，要幹嘛？
►名次未必反映實力──運動賽事裡的演算法
►排序效率差的價值──穩固　►血腥排序：啄序和優勢階級
►以競賽取代打鬥
排序對於處理各種資訊都十分重要。電腦科學家經常要權衡「排序」和「搜尋」兩者，這項權衡的基本原則是：花心力排序資料，目的是讓我們日後不用花費心力搜尋資料。於是這個問題變成：如何事先評估資料未來的用途？電腦科學指出，混亂和秩序造成的危險都可以量化，它們的成本都能以「時間」這個基準來呈現。Google搜尋引擎之所以強大，其實是拜預先排序之賜；但對於另外一些狀況，保持混亂往往更有效率。另外討論演算法的最差情況表現（以排序而言是「最差完排時間」），可以讓我們確定某個程序能在期限內完成，排定運動賽程便是一例。

◎第四章　快取——忘掉就算啦！
►把常用的東西放在手邊──記憶體階層
►把隔最久才會再用的資料剔除──貝雷迪演算法
►把圖書館內外翻轉　►街底的那片雲──距離非常重要
►家中的快取──收納空間
►關於書面資料怎麼歸檔，收納專家大多說錯了
►為最可能用到的東西騰出空間──遺忘曲線　►經驗的反效果
你的收納問題其實與電腦管理記憶體時面臨的挑戰類似：空間有限，要如何既省荷包又省時間？快取的概念是把常用資料放在手邊備用，快取裝滿時為了騰出空間放新資料，得剔除一些舊資料——但剔除哪些好呢？電腦科學家探究了「隨機剔除」、「先進先出」（先剔除最舊的）以及「最近最少使用法」等，甚至發展出能預測未來並執行已知最佳策略的演算法。這方面的研究啟發了亞馬遜書店的「預測包裹寄送」專利，還扭轉了心理學家對於人類記憶的看法。

◎第五章　排程——優先的事情優先處理
►「花時間」如何成為一門科學　►如果「在期限內完成」最重要
►要是「劃掉待辦清單上越多項目越好」
►先搞清楚用什麼標準來評量成果
►腳麻掉是要怎麼逃！──優先權反轉與優先權約束
►第一道障礙　►先擱下手上的事──占先與不確定性
►讓其他工作插隊的代價──上下文交換
►忙到變成在空轉──往復移動
►錯過這次，就等待下回─中斷接合
重要且緊急、重要但不緊急、不重要但緊急、不重要但不緊急……，時間管理大師總教人照這順序處理事情，但電腦科學家會要你先搞清楚「用什麼標準來評量成果」。是在期限內完成最重要？還是盡量縮短讓客戶等待的時間？抑或劃掉待辦清單上越多項目越好？不同的評量標準得採用不同的作業策略。本章還用電腦的「上下文交換」探討讓其他工作插隊的代價，用「往復移動」提醒忙到變成在空轉的徵兆；並告訴你如何在「反應能力」和「處理能力」間取捨，為何有時完成工作的最佳策略反而是慢下來。

◎第六章　貝氏法則——預測未來
►與貝斯牧師一起逆向推理　►拉普拉斯定律
►貝氏法則和事前看法　►哥白尼原理　►當貝斯遇見哥白尼
►真實世界的事前機率……　►……以及預測它們的規則
►小數據與心靈　►我們的預測如何讓我們認識自己
►機械複製時代中的事前分布
十八世紀的英國，賭博這個領域不僅深深吸引傑出數學家，也吸引了牧師湯瑪斯．貝斯，他由於研究彩券的中獎率，而對於「在不確定下進行推測」的歷史帶來重大影響。他認為由過去的假設狀況進行正向推理可提供基礎，讓我們逆向推出最可能的答案。其他科學家繼續研究預測事情的各種方法，像是：如何把各種可能假設狀況濃縮成單一期望值、根據事件類型提供適當的事前機率。其實我們腦中已儲存許多精確的事前分布，因此經常可由少量觀察結果做出不錯的預測，換句話說，小數據其實是偽裝的大數據。

◎第七章　過度擬合——少，但是更好
►考慮得更複雜，卻預測得更不準　►資料的偶像崇拜
►舉目所見盡是過度擬合　►揪出過度擬合─交叉驗證
►如何對抗過度擬合──懲罰複雜　►少就是好─試探法的優點
►歷史的權重　►什麼時候應該少想一點？
談到思考，我們往往覺得想得越多越好：列出的優缺點越多，做出的決定越好；列出的相關因素越多，越能精準預測股價。實際上統計模型倘若太過複雜，使用過多參數，會太容易受我們取得的資料影響，可能隨參與者不同而出現大幅差異。這就是統計學家說的過度擬合（又譯為過度配適）。機器學習的一大重要事實是：考慮因素較多、比較複雜的模型，未必比較好。這章演示了過度擬合如何扭曲我們對資料的解讀，點出日常生活中俯拾皆是的過度擬合事例，並且教你如何藉由交叉驗證等方法揪出過度擬合（像是怎麼分辨真正的人才和僅是懂得揣摩上意的員工？）並且對抗它。

◎第八章　鬆弛——放鬆點，不求完美才有解
►最知名的最佳化問題─業務員出差問題
►量化難度──用「不可能程度」來解答
►放鬆問題，提供解題的起點　►無限多的灰階：連續鬆弛法
►拉氏鬆弛法──只要你願意付出點代價　►學習放鬆
過去幾十年來電腦科學家發現，無論使用多快的電腦，或程式設計得多厲害，有一類問題就是不可能找出完美解方。面對無法解決的挑戰時，你毋須放棄，但也別再埋頭苦幹，而該嘗試第三種作法。電腦科學會界定問題是「可解」還是「難解」，遇到難解問題時會先「放鬆問題」：也就是先去除問題的某些限制，再著手解決它。最重要的放鬆方法比如「限制鬆弛法」、「連續鬆弛法」，以及付出點代價、改變規則的「拉氏鬆弛法」……

◎第九章　隨機性——什麼時候該讓機率決定
►抽樣　►隨機演算法　►禮讚抽樣
►取捨「確定程度」──電腦給的答案不一定對　►山丘、山谷和陷阱
►離開局部最大值　►模擬退火　►隨機性、演化和創造力
乍看之下，隨機性似乎和理性正好相反，它代表我們放棄這個問
隨機性乍看之下似乎和理性相反，代表我們放棄這個問題，採取不得已的手段。但你若是知道隨機性在電腦科學中扮演多吃重的角色，可能會非常驚訝。面對極為困難的問題時，運用機率可能是審慎又有效的解決方法。隨機演算法未必能提出最佳解，但它不用像確定性演算法那麼辛苦，前者只要有計畫地丟幾個硬幣，就能在短短時間內提出相當接近最佳解的答案，它解決特定問題的效果，甚至超越最好的確定性演算法。這章將要告訴你依靠機率的時機、方式，以及仰賴的程度。

◎第十章　網路——我們如何互通聲息
►封包交換──為了非連續交談而創
►應答─怎麼知道訊息有沒有送達？
►指數退讓──寬恕的演算法　►控制流量和避免壅塞
►祕密管道：語言學中的流量控制
►緩衝爆滿──笨蛋，問題出在延遲！　►既然遲了，不如就別做了
人類互通聲息的基礎是「協定」，也就是程序和預期的共通慣例，例如握手、打招呼和禮貌，以及各種社會規範。機器間的聯繫也不例外。在人際關係中，這類協定是微妙但長久存在的焦慮來源。我前幾天傳了個訊息，從何時開始我會懷疑對方根本沒收到呢？你的回答怪怪的，我們之間是不是有什麼誤會？網際網路問世後，電腦不僅是溝通管道，也是負責交談的聯絡端點，因此它們必須解決本身的溝通問題。機器與機器間的這類問題以及解決方案，很快便成了我們借鏡的對象。

◎第十一章　賽局理論——別人是怎麼想的？
►遞迴　►奈許，就是賽局達到均衡　►不採取「均衡」作法的代價
►公有地悲劇　►機制設計：改變賽局　►演化進行的機制設計
►資訊瀑布：悲慘的理性泡沫　►忠於自己
賽局理論廣泛影響經濟學和社會科學領域，然而除非賽局參與者找得到奈許均衡，它的預測能力才會造成影響，但是電腦科學家已經證明，純粹尋找奈許均衡是難解問題……
另外傳統賽局理論有個見解：對一群依據自身利益採取理性行動的參與者而言，「均衡」或許不是最好的結果。「演算法賽局理論」依據電腦科學原理，採用了這個見解並加以量化，創造出「自主行為代價」這個度量，結果發現某些賽局中，自主行為的代價其實沒有很高，這意謂著該系統不論細心管理或放任不管都差不多。

◎結語：運算的善意
對於人類的某些問題，如今已經找到解決的演算方法；即使尚未得到所需結果，但知道自己使用最佳演算法，也會讓人感到放心。此外電腦科學還能協助我們，清楚劃分哪些問題有明確解答、哪些問題則無，從而選擇要面對什麼——包括自己要面對什麼，以及要讓別人面對什麼，其原則便是運算的善意。現今的電腦做的，並非「盡量羅列選項，找出最好的一個」。有效的演算法會做出假設，偏向選擇較簡單的解答、權衡誤差代價和延遲代價，接著冒險一試。這些都不是我們難以理性面對時的讓步，它們本身就是理性的方法。

◎前言：為什麼我們能跟電腦學決策？
演算法的本質是「解決問題的一連串步驟」，人類面臨的許多挑戰跟電腦是一樣的：如何運用有限的空間、有限的時間、有限的注意力、未知的事物、不完整的資訊，以及無法預知的未來，並且如何輕鬆而自信地做到；以及如何在此同時與其他目標相同的人溝通。人類和電腦的解決方式融合程度極高，電腦科學不只能協助我們簡化問題以取得進展，甚至能提供具體的解決方法。本書將介紹前述難題的基本數學結構，以及工程師如何教電腦發揮最大效用，並了解人腦如何克服相同限制。作者訪問了近五十年來最知名演算法的...