【洛穀日報#18】簡單食用的博弈論

來自專欄演算法與開發筆記53 人贊了文章

博弈論又被稱為對策論（Game Theory），既是現代數學的一個新分支，也是運籌學的一個重要學科。學習博弈論，可以指導我們這個充滿競爭的世界中，我們要怎麼做才能讓自己（或者自己的集體）利益最大化。（《百度百科》）

博弈時往往有三種結果：負和博弈、零和博弈與正和博弈，用通俗的話解釋就是兩敗俱傷、一方獲利一方虧損和雙贏。正和博弈當然是最好的結果，但是往往無法達成。

博弈論有很多的種類，我們介紹其中的幾種。

一. 囚徒博弈論——為何走向窮途末路？

有一個廣為流傳的故事：兩個罪犯甲、乙入室盜竊並將屋子的主人殺害，被捕後分別審訊，他們都只承認盜竊罪，不承認故意殺人罪，這樣他們都會被判處1年有期徒刑。這似乎對他們來說是最好的情況，但是後來他們卻紛紛承認故意殺人罪，為什麼呢？

原因很簡單：他們是分開審訊的。

假設盜竊罪判刑1年，故意殺人罪判刑8年，被別人揭穿會加刑1年，坦白減刑2年，那麼就可以繪製一個簡易的博弈論模型：

圖真是太不美了(●—●)

明明可以少坐6年牢，為什麼要招供呢？不妨從甲和乙的角度來考慮：由於不知道對方的消息，甲會認為，我不知道能不能相信乙，萬一他先招供了，我就會坐10年的牢，為了不引起最壞的後果，還能夠釋放，我必須先招認！同樣的，乙的想法和甲類似，再加上警察煽風點火，於是便紛紛招供，最後的結果是兩人一起坐7年的牢。

這就呈現了所謂博弈論中的「納什均衡」，簡單來說是如果參加博弈的一方不改變策略，另一方就無法得到更好的結果，往往走向負和博弈，有興趣的小夥伴可以點進去了解一下 qwq

這就是最經典的囚徒博弈論。

二.槍手博弈論——弱者的生存法則

故事是這樣的：三個槍手（大佬，蒟蒻，我）積怨已久，決定進行一場決鬥。當然，他們不是機器人，槍法有一定的差別（即使是大白也不會百發百中的），大佬是個神槍手，命中率是80%，蒟蒻差一些，命中率是60%，我最菜了。。。???????命中率只有40%（這是不是和我不常刷題有關(；д；)），如果在每人只有1顆子彈，且擊中必殺，大家都保持絕對理性的前提下，出現了兩個問題：

1.如果我們三個人同時開槍，誰活下來的概率會最大？ 2.如果我們輪流開槍，採用什麼策略活下來的概率會大？

首先討論第1個問題，如果我們同時開槍，大佬一定是會把槍口對準蒟蒻的（他都是大佬了，不可能出現低級失誤233），因為蒟蒻的命中率要比我高，他一定要先殺死對自己威脅大的那一個人。而蒟蒻會向大佬開槍，道理和大佬相同，我呢，自然把槍對準了大佬。這時來看一下3人的存活率，大佬是24%，蒟蒻是20%，至於我呢，因為沒有人瞄準我，所以我的存活率是100%。這時，最菜的我反而成了存活率最高的人呢。( ? ?ω?? )?

好了，現在討論第2個問題，如果我們輪流開槍呢？

1. 大佬先開槍
   依照「先殺死威脅大的目標的原則」，大佬自然要把槍口對準蒟蒻，如果殺死了……（此處省略血腥內容）如果沒殺死呢，蒟蒻自然會向大佬開槍，全程我可以毫髮無塤。這時，我再拿起槍，瞄準剩下的一個目標，（或者兩個目標都活著的話就朝天）開一槍，娛樂一下，勝率我仍然是最大的。so easy！媽媽再也不用擔心我打不準了
2. 蒟蒻先開槍
   蒟蒻會把槍口對準對他更具有威脅的大佬，我不會有危險，如果它命中了，我就向蒟蒻開槍，沒打中就朝大佬開槍，最後我的存活率仍然是最大的。(　 ′-ω ?)▄︻┻┳══━一
3. 我先開槍
   這是一個很讓我糾結的問題，我該先向誰開槍呢？打大佬？沒打中還好，會轉化成大佬先開槍的情況（也難保他不記仇呀），萬一RP不足手抖打中了呢，那就只剩下我和蒟蒻兩人了，他一定會朝我開槍了,那我可就很危險了呀！不行不行，我可不能這麼草率。那麼如果朝蒟蒻開槍呢？那也是一樣的，打中了反而會使自己置於更加危險的境地，因為大佬的命中率更高。打誰都不是，那麼該怎麼辦呢？結論是：朝天開槍。Σ(?д?lll)這確實很滑稽，但也是最有效的方法，能夠讓情況變為大佬先開槍。所以博弈時往往要出奇策才能夠取勝。

不信的話大家可以試一下，三個砝碼，一個骰子（雖然無法得到80%，60%和40%，但是可以先用一下），開槍時轉動骰子，如果大佬轉到1,2,3,4,5，那麼他殺死了他的目標，蒟蒻轉到1,2,3，那麼他殺死了他的目標，如果我菜雞轉到1，那麼我殺死了我的目標。

多試幾次，看看誰的存活率大！

好了，我們繼續狗血劇情，我們突然握手言和了，決定改日再戰……（劇本太狗血，我編不下去了。。。）啊，反正就是這次我們沒有決鬥，然後呢，大家都想在下一次的決鬥中把對方打趴下，回家苦練槍法，大佬的命中率提升到了100%（蒟蒻知道了嚇得瑟瑟發抖），蒟蒻不甘落後命中率提高到80%，我太懶了也太菜了，命中率毫無提升，還是40%（我是一個比蒟蒻還弱的人）＼( ′?∧?｀)／ ，於是，按照領錯了的劇本，我們又相遇了，又要決鬥，那麼按照剛才的情況推理，大佬向蒟蒻開槍，蒟蒻向大佬開槍，我向大佬開槍，大佬的存活率是12%，蒟蒻的存活率是0%（快給他準備一份便當！），我的存活率是100%，依然是最高的ヽ(≧?≦)?，但是其餘兩人的存活率卻發生了變化，這說明，只要任何數據發生變化，存活率都會發生巨大的變化。

本來故事要結束了，突然，導演（我怎麼會告訴你那就是我？！）認為蒟蒻還應該有戲份，於是又讓他們握手言和了（什麼鬼？！）。這會大家（包括我啦）都意識到了槍法的重要性，開始苦礪槍法，命中率都提升到了100%，後來（你已經猜到了），我們又一次相遇了。每人同樣只有一顆子彈，再一次問兩個問題：

1. 同時放槍，你會選擇打人還是放空槍？
2. 由我先開始放槍，我該打人還是放空槍？

先討論1，結束後無非4種情況：

(1) 自己活著，另外兩個人去領盒飯了；

因為別人指向誰開槍是無法預測的，所以每個人的存活率是相等的，這時如果放棄開槍，就會讓另外兩人的存活率提高，所以這時應該朝任何一個人開一槍，至少不減小對他人的威脅，因為大家命中率都是100%，所以這時打誰就顯得不那麼重要了，朝一個人放一槍，聽天由命吧。

再來討論2，那就會有很大的不同，分情況討論一下：

(1) 朝人開槍：必定殺死一人，然後場上變為兩人，另外一人開槍，那麼他必定會朝我開槍，然後就沒有然後了。。。

不可取不可取，我還沒演完呢，不能去領盒飯|。?ω?)っ

(2) 於是乎應該考慮另一種方法：放空槍。

一旦我打出了僅有的一顆子彈後，我對於另外兩人便變得沒有威脅了，這樣輪到下一個人開槍時，他一定會朝另外一個人開槍，因為如果第二個人不打死他而是選擇放空槍，下一回合他就會有50%的概率被幹掉，這是不可取的。

這樣就變成了一個另外兩方自相殘殺的局面，從而最後兩個人活下來。

但是如果他識破了我的計謀要朝我放槍呢？那樣他就一定會被第三個人打掛，還不如放空槍的存活率，他一定會打死第三個人。

綜上所述，放空槍是最有利的選擇。

講了這麼多，大家心裡應該有個疑問：

這講的都是模型，有應用價值嗎？

其實大家耳熟能詳的歷史中就有呀(～￣▽￣)～

三方對立，有強有弱，互相牽制，大家想到了什麼？

對，是三國！

三國時期的赤壁之戰，劉備最弱，孫權其次，曹操最強，曹操要和孫權干架，諸葛亮的想法是：二虎相爭，必有一傷，如果曹操輸了必定一蹶不振，孫權就會向劉備開刀，如果孫權被滅，曹操也必定會攻打劉備。這時劉備幫助較弱的孫權，將曹操打敗，但是又「一不小心」讓關羽把曹操在華容道放掉了，以達到制衡的目的。節省篇幅，這裡戰爭細節就不扯了。這就是槍手博弈論的應用。

那麼為啥不幫曹操呢？

這是因為魏國實力更強，如果聯曹攻吳，東吳很可能會被滅掉，蜀國為了避免不利情況出現，應該聯吳抗曹，這樣不足以將魏國消滅。

好了，導演要逃殺青了，下一集海盜分金見！ qwqqwq

這一集真的要劇終了

三.海盜分金博弈論——倒推取勝

這一講跟海盜打仗無關！！！

故事是這樣的：

5個海盜搶了100個金幣（我說過跟打仗無關），準備分，但是他們分的方法非常奇特（為什麼不平分？）他們準備了5個簽，分別寫上1,2,3,4,5，然後抽籤，按抽籤順序（從小到大）輪流制定方案，從1號開始，他制定了分金方案後大家需要立即表決（該海盜也表決），如果有半數以上（含半數）的人支持，則方案通過，按此方案分金，否則（重口味的來了！）就會被扔到海里喂鯊魚。

我們做如下假設：

1. 每一個海盜都是絕對理性的，且思考周全，智商極高，不會做出錯誤判斷。
2. 不存在某些海盜私下結夥或有仇的情況。
3. 海盜不會因為通過的提案對自己不利而大打出手。
4. 所有海盜都不想去喂鯊魚。
5. 所有海盜都想獲得更多的金幣。

好了，現在如果你是1號海盜，你該如何使自己獲得最大利益？

表面上看1號海盜是最不利的，因為他最有可能去喂鯊魚，因為參與分金的海盜越少，越能獲得更多利益，即使自己分文不取將金幣全分給另外四個海盜，他們也仍然有可能會把他扔給鯊魚。

怎麼辦？怎麼辦？怎麼辦？現在好慌呀！我不想喂鯊魚！

別急，咱冷靜一下，再看一遍規則，你會發現一個突破點：

如果有半數以上（含半數）的人支持，則方案通過

欸，也就是說不需要獲得所有人的支持呀？我只要籠絡2個處於劣勢的海盜就可以不喂鯊魚了！不慌了！

可是，應該籠絡誰呢？又該如何籠絡呢？

這時往往會三等分，但是這對分到金幣的另外兩個海盜顯然不是最佳方案，行不通呀。

這時大家可能會嫉妒5號，既安全又能分錢。

別急著嫉妒，請大家回去看一遍本小節的標題。

看完了嗎？倒推取勝對不對？那我們就從簡單的情況想起：

5號明顯是最安全的，因為他沒有喂鯊魚的危險，但是他真的能分到錢嗎？[?_??]

倒推舉例證明：

假設只剩4號，5號兩人，你、2號和3號都喂鯊魚了（當然你不想這樣），這時4號分金，他會怎麼辦呢，肯定會是100:0，表決時4號一定贊成，5號即使反對，支持人數也過了半數，表決結果是5號無法改變的，這樣5號就會顆粒無收，這時他處於劣勢，所以3號的提案里只要給他1枚金幣，他就一定會贊成來避免自己的劣勢情況，同樣的，按照籠絡劣勢海盜原則，3號海盜指定的方案應該是99:0:1，放棄4號，籠絡5號，這樣3號，5號贊成，提議通過，5號獲利1金幣，不再處於劣勢，處在劣勢的變成了4號。

是不是有頭緒了？我們再加上一個海盜，2號制定方案，應該籠絡處於劣勢的4號海盜，方案為：99:0:1:0（當然也可以籠絡5號，方法不止一種），2號、4號海盜贊成，提議通過。劣勢海盜為3號。

最後加上1號海盜，也就是我們，應該籠絡誰呢，首先要籠絡劣勢的3號，放棄優勢的2號，再在4號、5號之間任選一個，制定方案（一種例子，大家可以再想其他的）為：98:0:1:1:0，就可以通過。

沒想到吧，看似最危險的1號可以化險為夷還能瘋狂斂財，最安全的5號卻可能顆粒無收，如果正思入手，很容易卡住，倒推卻容易多了，大家要學會用。

當然，現實生活中大家或多或少都是非理性的，海盜往往寧可同歸於盡也不會讓1號拿走98枚金幣的，所以這個模型僅供分析

博弈論的幾個分支就講到這裡，希望對大家有所幫助！

拜拜咯！

本文發佈於洛穀日報，特約作者：蒟蒻煙雨平生

原文地址：簡單食用的博弈論 - 蒟蒻煙雨平生 的博客 - 洛谷博客

歡迎向洛穀日報投稿：洛穀日報徵稿中

推薦閱讀：