在面試的過程中，除了正常的算法題目，我們經常也會被問到一些趣味題型來考察思維，而這類問題中，很多都有博弈論的影子存在。這些公司裡以FLAG（Facebook, LinkedIn, Amazon, Google）為典型，特别喜歡考察本類題型。同時，本系列将不一定都是算法問題，不是IT行業的小夥伴也可以進行學習，來提高分析問題的能力~
另外對于Acmer的同學附上 ACM博弈論基本算法入門文章
1、什麼是“博弈論”
古語有雲，“笑人情似紙，世事如棋”。生活中每個人如同棋手，其每一個行為如同在一張看不見的棋盤 上布子，精明慎重的棋手們互相揣摩、牽制、争赢，下出諸多精彩紛呈、變化多端的棋局。而什麼是博 弈論？就是研究棋手們 的“出棋” 過程，從中抽象出可邏輯化的部分，并将其系統化的一門科學，也是運 籌學的一個重要學科。 我們從最簡單的一道“囚徒困境”來進行學習~
2、囚徒困境
| 囚徒困境 |
|---|
| 一件嚴重的縱火案發生後，警察在現場抓到兩個犯罪嫌疑人。事實上，正是他們一起放火燒了這座 倉庫。但是，警方沒有掌握足夠的證據，隻得把他們分開囚禁起來，要求他們坦白交代。 |
在分開囚禁後，警察對其分别告知：
- 如果你坦白，而對方不坦白，則将你釋放，判對方8年。
- 如果你不坦白，而對方坦白，則将對方釋放，而判你8年。
- 如果你兩都坦白了，則判你兩各自4年。
那麼兩個囚犯應該如何做，是互相背叛還是一起合作？
題目分析： 從表面上看，其實囚犯最應該的就是一起合作，都不坦白，這樣因為證據不足，會将兩人都進行釋放。 但是！因為事實确實是兩人放的火，是以他們不得不進行思考，另一人采取了什麼樣的行為？
犯人甲當然不傻，他根本無法相信同夥不會向警方提供任何資訊！因為如果同夥一旦坦白，而自己這邊 如果什麼都沒說的話，就可以潇灑而去。但他同時也意識到，他的同夥也不傻，也會同樣來這樣設想他。
是以犯人甲隻會有一種結論：唯一理性的選擇就是背叛同夥，把一切都告訴警方！這樣的話，如果他的同夥笨 得隻會保持沉默，那麼他就會是那個離開的人。而如果他的同夥也根據這個邏輯向警方交代了，那麼也 沒有關系，起碼他不必服最重的刑！
2.1、 囚徒困境與納什均衡
這場博弈的過程，顯然不是顧及團體利益的最優解決方案。以全體利益而言，如果兩個參與者都合作保 持沉默，兩人都可以無罪釋放，總體利益更高！但根據假設（人性），二人均為理性的個人，且隻追求 自己的個人利益。均衡狀況會是兩個囚徒都選擇背叛，這就是“困境”所在！
事實上，這種兩人都選擇坦白的政策以及是以被判4年的結局被稱作“納什均衡”（也叫非合作均衡），換 言之，在此情況下，無一參與者可以“獨自行動”（即單方面改變決定）而增加收獲。
我們看一下官方釋意是多麼難懂“所謂納什均衡，指的是參與人的一種政策組合，在該政策組合上，任何參與人單獨改變政策都不會得到好處。”簡單點講，如果在一個政策組合上，當所有其他人都不改變 政策時，沒有人會改變自己的政策，則該政策組合就是一個納什均衡。
3、辛普森悖論
| 辛普森悖論 |
|---|
| 羊羊醫院裡統計了兩種膽結石治療方案的治愈率。在統計過程中，醫生将病人分為大膽結石和小膽 結石兩組。統計結果如下： |
- 對于小膽結石而言，手術A的治愈率（93%）高于 手術B（87%）
- 對于大膽結石而言，手術A的治愈率（73%）高于 手術B（69%）
羊羊醫院的醫生得出結論：
無論是對于大小膽結石，手術A的治愈率都勝過手術B。
但是真的是這樣嗎？當然不是，我們根據樣本統計出大小膽結石總計的治愈率，發現手術B(治愈率 83%)其實是要高于手術A(治愈率78%)。
為什麼會出現這樣的結果？這就是著名的辛普森悖論。
3.1、直覺的缺陷
得到了結論，我們來思考背後的東西。在我們的直覺裡有這樣一個邏輯：如果一個事物的各部分都分别 大于另一個事物的各部分，那麼這個事物大于另一個事物。比如：我們的直覺告訴我們如果手術A在兩 組病人中都更好，那麼在所有病人中也應該更好。
我們可以将其公式化（該公式錯誤），假設：
博弈論經典模型解析（入門級）
乍一看，我們覺得該公式沒有問題~是以這個公式也就代表了我們大部分人的思維工作。其實在這個公 式中，隐藏掉了一個很重要的條件：A1、A2、An 以及 B1、B2、Bn 并不能簡單的通過“加”來得到 A 或者 B。這就是可加性的前提。在大腦的思維過程中，因為我們很難直接看到這個前提，進而就導緻了 我們錯誤的思考！
3.2、辛普森悖論舉例
下面我們舉一些在生活中常見的辛普森悖論例子：
- 打麻将的時候，把把都赢小錢，造成赢錢的假象，其實不如别人赢一把大的。
- 在蘋果和安卓的競争中，你聽見身邊的人都在逃離蘋果，奔向安卓。但是其實蘋果的流入率還是要 高于安卓。（有資料證明，很經典的案例）
- 你男票，這裡比别人差，那裡比别人差，但是其實他真的比别的男生差嗎？（這個純屬本人胡扯 了..）
4、紅眼睛和藍眼睛
| 紅眼睛和藍眼睛 |
|---|
| 一個島上有100個人，其中有5個紅眼睛，95個藍眼睛。這個島有三個奇怪的宗教規則。 |
- 他們不能照鏡子，不能看自己眼睛的顔色。
- 他們不能告訴别人對方的眼睛是什麼顔色。
- 一旦有人知道了自己是紅眼睛，他就必須在當天夜裡自殺。
某天，有個旅行者到了這個島上。由于不知道這裡的規矩，是以他在和全島人一起狂歡的時候，不留神 就說了一句話：【你們這裡有紅眼睛的人。】
問題：假設這個島上的人每天都可以看到其他所有人，每個人都可以做出缜密的邏輯推理，請問島上會 發生什麼？
4.1、題目分析
題目乍看之下，沒有任何邏輯可言！以目測條件，基本無法完成任何正常的推理。但是在仔細推敲之 後，我們可以将問題簡化，從假設隻有1個紅眼睛開始分析。
我們假設島上隻有1個紅眼睛的人，還有99個都是藍眼睛。因為這個旅行者說了“這裡有紅眼睛的人”， 那麼在第一天的時候，這個紅眼睛會發現其他的人都是藍眼睛（與此同時，其他人因為看到了這個紅眼 睛的人，是以都确認了自己的安全）那麼這天晚上，這個紅眼睛的人一定會自殺！
繼續分析，假設這個島上有2個紅眼睛，那麼當旅行者說“這裡有紅眼睛的人”之後的第一天，這兩個紅眼 睛分别發現還有别的紅眼睛存在，是以他們當天晚上認為自己是安全的。但是到了第二天，紅眼睛驚訝 的發現，另一個紅眼睛的人竟然沒有自殺（說明島上有不止一個紅眼睛），并且當天他們也沒有發現有 别的紅眼睛存在（說明另一個紅眼睛就是自己）WTF，那肯定另一個紅眼睛就是自己了，是以在第二天 夜裡，兩個紅眼睛的人會同時自殺！
繼續分析，假如島上紅眼睛有3個。那麼在第一天，紅眼睛發現了島上還有另外兩個紅眼睛，紅眼睛呵 呵一笑，“反正不是我”。到了第二天，紅眼睛仍然看到了另外兩個紅眼睛，紅眼睛心想，"這下你兩該完 蛋了吧"，畢竟你兩都知道了自己是紅眼睛，晚上回去統統自殺吧！（根據上面的推論得出）但是驚奇 的是，到了第三天，紅眼睛發現另外兩個紅眼睛竟然都沒有自殺。（說明島上紅眼睛的人不止兩個）并 且當天紅眼睛也沒發現新的紅眼睛（說明還有一個紅眼睛就是自己）是以在第三天的夜裡，三個紅眼睛 會同時自殺。
根據上面的推論，假設有N個紅眼睛，那麼到了第N天，這N個紅眼睛就會自殺。是以最終這個島上紅 眼睛的人會統統自殺！這就是答案，生活就是這麼樸實無華，且枯燥。
4.2、旅客的挽回
上面的分析大家應該都看懂了。但若是在旅客說完這句話後，其并沒有離開這個島。同時他也看到了周 圍人眼裡的驚慌和失措，這個時候，旅客為自己的行為感到了懊惱和悔恨！旅客決定對自己的話進行挽回，旅客又該怎麼做呢？
這裡我提供一種思路，旅客可以在第N次集會上殺掉N個紅眼睛，讓這N個紅眼睛 “GO TO SLEEP”，就 可以中斷事件的推理。事實上，基于人道主義，旅客并不需要手動殺人，她隻需要在第N天的時候告訴 這N個人，你們是紅眼睛，那麼這天晚上，這N個人就會自殺。"All RETURN"，一切将回歸秩序~
5、海盜分金币
| 海盜分金币 |
|---|
| 在大海上，有5個海盜搶得100枚金币，他們決定每一個人按順序依次提出自己的配置設定方案，如果 提出的方案沒有獲得半數或半數以上的人的同意，則這個提出方案的人就被扔到海裡喂鲨魚。那麼 第一個提出方案的人要怎麼做，才能使自己的利益最大化？ |
海盜們有如下特點：
- 足智多謀，總是采取最優政策。
- 貪生怕死，盡量保全自己性命。
- 貪得無厭，希望自己得到越多寶石越好
- 心狠手辣，在自己利益最大的情況下希望越多人死越好。
- 疑心多慮，不信任彼此，盡量確定自身利益不寄希望與别人給自己更大利益。
5.1、題目分析
首先我們很容易會覺得，抽簽到第一個提方案的海盜會很吃虧！因為隻要死的人夠多，那麼平均每個人 擷取的金币就最多，而第一個提方案的人是最容易死的。但是事實是，在滿足海盜特點的基礎上，第一 個提方案的海盜是最賺的（也就是我們常說的先手優勢），我們一起來分析一下。
假如我們設想隻有兩個海盜。那麼不管第一個說什麼，隻要第二個人不同意，第二個人就可以得到全部 的金币！是以第一個海盜必死無疑，這個大家都能了解。（當然，這樣的前提是一号提出方案後不可以 馬上自己同意，不然如果自己提出給自己全部金币的方案，然後自己支援，這樣就是二号必死無疑）
假如現在我們加入第三個海盜，這時候原來的一号成為了二号，二号成為了三号。這時候現在的二号心 裡會清楚，如果他投死了一号，那麼自己必死無疑！是以根據貪生怕死的原則，二号肯定會讓一号存 活。而此時一号心理也清楚，無論自己提出什麼樣的方案，二号都會讓自己存活，而這時隻要加上自己 的一票，就有半數通過，是以一号提出方案：把金币都給我。
現在又繼續加入了新的海盜！原來的1,2,3号，成為了現在的2,3,4号。這時候新的一号海盜洞悉了奧 秘，知道了如果自己死了，二号就可以擷取全部的金币，是以提出給三号和四号一人一個金币，一起投 死2号。而與此同時，現在的3号和4号擷取的要比三個人時多（三個人時自己擷取不了任何金币），所 以他們會同意這個方案！
現在加入我們的大Boss，最後一個海盜。根據分析，大Boss海盜1号推知出2号的方案後就可以提出 (97,0,1,2,0)或者(97,0,1,0,2)的方案。這樣的配置設定方案對現在的3号海盜相比現在的2号的配置設定方案還多了 一枚金币，就會投贊成票，4号或者5号因為得到了2枚金币，相比2号的一枚多，也會支援1号，加上1 号自己的贊成票，方案就會通過，即1号提出(97,0,1,2,0)或(97,0,1,0,2)的配置設定方案，大Boss成功獲得了 97枚金币。
5.2、思考
最終，大Boss一号海盜得到97枚金币，投死了老二和老五，這竟然是我們分析出的最佳方案！這個答 案明顯是反直覺的，如果你是老大，你敢這樣分金币，必死無疑。可是，推理過程卻非常嚴謹，無懈可 擊，那麼問題出在哪裡呢？
其實，在"海盜分贓"模型中，任何"配置設定者"想讓自己的方案獲得通過的關鍵是，事先考慮清楚"對手"的 配置設定方案是什麼，并用最小的代價擷取最大收益，拉攏"對手"配置設定方案中最不得意的人們。1号看 起來最有可能喂鲨魚，但他牢牢地把握住先發優勢，結果不但消除了死亡威脅，還收益最大。而5号， 看起來最安全，沒有死亡的威脅，甚至還能坐收漁人之利，卻因不得不看别人臉色行事而隻能分得一小 杯羹。
不過，模型任意改變一個假設條件，最終結果都不一樣。而現實世界遠比模型複雜。因為假定所有人都理性，本身就是不理性的。回到“海盜分金”的模型中，隻要3号、4号或5号中有一個人偏離了絕對聰明 的假設，海盜1号無論怎麼分都可能會被扔到海裡去了。是以，1号首先要考慮的就是他的海盜兄弟們的 聰明和理性究竟靠得住靠不住，否則先分者必定倒黴。
如果某人和一号本身不對眼，就想丢他喂鲨魚。果真如此，1号自以為得意的方案豈不成了自掘墳墓。 再就是俗話所說的“人心隔肚皮”。由于資訊不對稱，謊言和虛假承諾就大有用武之地，而陰謀也會像雜 草般瘋長，并借機獲益。如果2号對3、4、5号大放煙幕彈，宣稱對于1号所提出任何配置設定方案，他一定 會再多加上一個金币給他們。這樣，結果又當如何？
通常，現實中人人都有自認的公平标準，因而時常會嘟嚷：“誰動了我的奶酪？”可以料想，一旦1号所提 方案和其所想的不符，就會有人大鬧。當大家都鬧起來的時候，1号能拿着97枚金币毫發無損、鎮定自 若地走出去嗎？最大的可能就是，海盜們會要求修改規則，然後重新配置設定。當然，大家也可以講清楚下 次再得100枚金币時，先由2号海盜來分…然後是3号……
頗有點像美國總統選舉，輪流主政。說白了，其 實是民主形式下的分贓制。（僅吐槽）
最可怕的是其他四人形成一個反1号的大聯盟并制定出新規則：四人平分金币，将1号扔進大海。這就頗 有點阿Q式的革命理想：高舉平均主義的旗幟，将富人扔進死亡深淵。
最後，這裡也提供一份代碼實作，供有興趣的同學參考（該代碼我大概看了一下，但是因為時間的關 系，沒有跑單測進行驗證，特此說明！）
以上代碼輸出：5人時配置設定方案：[97, 0, 1, 0, 2]
看懂了嗎？如果看懂了，這裡提出一個問題：假如我們将人性考慮在内，同時也進行理性的分析，如果 你是老大，又該如何提出這個方案呢？大家在留言區留下自己的回答吧
6、結語
好啦，這篇内容就到這裡了，你學會了嗎？另外經典博弈論還有很多模型，如：以牙還牙、手表定律、槍手博弈 之類的。這裡就先不展開論述了，有興趣的話可以自行Google。