原文: http://talkupday.com/海盜分配金幣的博奕難題/ 原文作者: I.T.人 Facebook 專頁: Talkupday 圍講噏Day 博奕論 (Game Theory) 是一門應用數學, 其應用範疇甚為廣泛, 包括經濟學﹑生物演化﹑社會行為﹑國家外交及軍事戰略等數之不盡的領域。我們在日常生活中需要作出不同的抉擇, 而我們往往在不知不覺間運用了博奕的思考模式。因此, 博奕論並不是驚天的大發明, 只是有系統地以數學解釋我們在博奕中的思考過程, 從而預測我們在一項博奕中最合理的選擇。進階的博奕理論可以十分複雜, 容許我們以後慢慢為大家介紹, 今次筆者想分享一個博奕論的問題, 讓大家體驗一下博奕論的預測與我們的直觀其實可以截然不同。 問題 從 前有五名海盜, 稱呼他們為 A, B, C, D, E。海盜們的階級觀念很重, A 是海盜大王, 其次是 B, 之後是 C, 之後是 D, 最低級的是 E, 以數學的方式表示即是 A > B > C > D > E。一天, 海盜們找到 100 枚金幣, 他們決定以下列的規則分配金幣: 由海盜王首先提出一項分配方案, 然後大家 (包括倡議方案者) 進行投票, 假如多數人支持方案, 將會以此方案分配金幣。假如方案沒有被通過, 倡議方案者將會被殺, 然後到下一個地位最高的海盜再次提議分配方法, 如此類推。在票數相同的情況下, 倡議方案者有最終的決定權。 假設五名海盜皆非常聰明﹑非常理性﹑非常明白博奕論及非常冷血殘暴, 他們在分配金幣的投票過程中會以下列三點作考慮: 1. 自己不能被殺掉 2. 要得到最多的金幣 3. 在上述條件能達到的情況下, 假設條件相同, 優先考慮殺掉倡議方案者 (例如海盜 E 無論如何都只拿到 N 枚金幣, 他會優先考慮否決方案殺掉上級。) 你能否以博奕論預測金幣將會如何分配? <博奕論分析> 假如不用博奕論的思考模式, 大家可能直觀地覺得海盜王為了保命, 一定會把金幣全部給其他人換取贊成票, 但是這結果卻與博奕論的預測相差很遠。 首 先, 我們把整個博奕由結尾開始看, 即是假設只剩下 D 和 E 的情況。由於只有兩個人投票, 而在票數相同下, D 擁有決定權; 因此, D 一定是提出由他自己拿下所有金幣。亦由此得出結論, 儘管 E 一直否決方案, E 最終還是一無所有, 而 D 則最希望能夠達到只剩下 D 和 E 這個投票環境。 結論: D, E -> D (100), E (0) 我們再看假如剩下 C﹑D 和 E, 情況又會怎樣。在 C 提出方案的回合, D 是一定會否決的。而假如不分金幣給 E , E 雖然在下一回合也是一無所有, 但基於在條件相同也選擇優先殺上級的情況下, E 也會否決。因此, C 只要給 E 一枚金幣, E 便會投贊成票。 結論: C, D, E -> C (99), D (0), E (1) 現在看 B﹑C﹑D﹑E 的情況, 由於 C 的最理想環境是剩下 C﹑D 和 E, 因此 C 一定投反對。因為 B 只需多一票的支持, 而 D 知道假如剩下 C﹑D 和 E, 他將會如上述分析得不到金幣, 因此 B 只需給一枚金幣給 D, D 便會投贊成票。 結論: B, C, D, E -> B (99), C (0), D (1), E (0) 最後, 我們看看 A﹑B﹑C﹑D﹑E 的初始情況, 由於 C 跟 E 知道假如進入 B﹑C﹑D﹑E 的回合, 他們將一無所有, 因此, 只要海盜王 A 各給一枚金幣給 C 和 E, 他們將會贊成海盜王的方案。 結論: A, B, C, D, E -> A (98), B (0), C (1), D (0), E (1) A: 98 枚 B: 0 C: 1 枚 D: 0 E: 1 枚 這便是博奕論得出最優化的策略, 亦是金幣分配方案的預測。 <博奕論的延伸> 英國數學家 Ian Stewart 以上述邏輯繼續延伸, 結果發現一個有趣的現象。假設有 N 個海盜同樣分 100 枚金幣, N 是海盜王, 1 是最低級海盜, 在 N ≤ 200 的情況下, 分配方式將如下: 海盜王: 枚金幣 假如 N 是單數, 所有單數海盜均能得到一枚金幣; 假如 N 是雙數, 所有雙數海盜均能得到一枚金幣。 假如再繼續延伸到 N > 200, 我們可以得出以下結果: 201 必須以 101: 100 的投票結果才能保命,因此他不能拿金幣, 只能把金幣全部發給 1 - 199。而 1 - 199 中單數的海盜每人各得一枚金幣,因此, 他才能從 1 - 199 號的單數海盜中拿到 100 贊成票, 加上自己的一票, 剛好 101票通過方案。 202 與 201 情況相似, 需要自己放棄金幣,而給 2 - 200 中的雙數號每人一枚金幣。 到了203號,情況變得有趣。因為 203 需要102票才可通過方案,但他只有 100 枚金幣去收買 100 人, 加上自己的一票, 僅有 101 票, 他的方案是註定不能通過的。 204 情況卻比 203 好一些,因為 203 要保命, 他一定要支持 204 的方案才有機會, 因此 204 可以給 1 - 199 中單數海盜每人一枚金幣, 收賣 100 人, 加上 203 及自己一票, 將會得到 102 票以 102:102 通過方案。 205 不能指望 203 與 204 支持他, 因此方案註定不能通過。 206 也是一樣,需要 103 票通過方案,就算 205 會因為希望保命而支持他,206 還是差一票。 207 需要 104 票,但是他最多也只能得到 103 票(207, 205, 206, 1-200 中的100人),所以方案註定不能通過。 208 則跟 204 相似,他可以給 2 - 200 中的雙數每人金幣一枚,得到 100 票支持,同時他自己跟 205, 206, 207 也會投贊成票,剛好 104:104 票通過方案。 我 們繼續以上述邏輯分析, 將會發現當 N > 200, 只有 201, 202, 204, 208, 216, 232, 264, 328, 456, 712, 1224... 可以生存, 而他們依次序把金幣分給單數然後雙數。而以上的序列是根據下列公式形成: 201 + 1 = 202 202 + 2 = 204 204 + 4 = 216 216 + 16 = 232 232 + 32 = 264 264 + 64 = 328 328 + 128 = 456 456 + 256 = 712 712 + 512 = 1224... 因此, 假如你問我有 1500 名海盜, 他們的下場是怎樣, 我很快可以告訴你, 頭 276 名海盜方案一定被否決, 第 1224 海盜可以活下來, 1-199 中單數的人全數得一枚金幣, 其他海盜一無所有。 經過思考以上的問題, 希望大家對博奕論多一點認識, 並體驗到博奕論可以幫助我們理性地分析出最好的策略, 並預測對手的抉擇。希望日後可以為大家介紹更深入的博奕理論。