博弈論之囚徒困境
來(lái)源：小浩算法
作者：程序員浩哥
本系列將為大家?guī)?lái)一整套的博弈論問(wèn)題。因?yàn)樵诿嬖嚨倪^(guò)程中，除了常規(guī)的算法題目，我們經(jīng)常也會(huì)被問(wèn)到一些趣味題型來(lái)考察思維，而這類(lèi)問(wèn)題中，很多都有博弈論的影子存在。這些公司里以FLAG（Facebook, LinkedIn, Amazon, Google）為典型，特別喜歡考察本類(lèi)題型。同時(shí)，本系列將不一定都是算法問(wèn)題，不是IT行業(yè)的小伙伴也可以進(jìn)行學(xué)習(xí)，來(lái)提高分析問(wèn)題的能力~
古語(yǔ)有云，“笑人情似紙，世事如棋”。生活中每個(gè)人如同棋手，其每一個(gè)行為如同在一張看不見(jiàn)的棋盤(pán)上布子，精明慎重的棋手們相互揣摩、牽制、爭(zhēng)贏，下出諸多精彩紛呈、變化多端的棋局。而什么是博弈論？就是研究棋手們 的“出棋” 過(guò)程，從中抽象出可邏輯化的部分，并將其系統(tǒng)化的一門(mén)科學(xué)，也是運(yùn)籌學(xué)的一個(gè)重要學(xué)科。
我們從最簡(jiǎn)單的一道“囚徒困境”來(lái)進(jìn)行學(xué)習(xí)~
囚徒困境：一件嚴(yán)重的縱火案發(fā)生后，警察在現(xiàn)場(chǎng)抓到兩個(gè)犯罪嫌疑人。事實(shí)上，正是他們一起放火燒了這座倉(cāng)庫(kù)。但是，警方?jīng)]有掌握足夠的證據(jù)，只得把他們分開(kāi)囚禁起來(lái)，要求他們坦白交代。在分開(kāi)囚禁后，警察對(duì)其分別告知：
如果你坦白，而對(duì)方不坦白，則將你釋放，判對(duì)方8年。
如果你不坦白，而對(duì)方坦白，則將對(duì)方釋放，而判你8年。
如果你兩都坦白了，則判你兩各自4年。
那么兩個(gè)囚犯應(yīng)該如何做，是互相背叛還是一起合作？
從表面上看，其實(shí)囚犯最應(yīng)該的就是一起合作，都不坦白，這樣因?yàn)樽C據(jù)不足，會(huì)將兩人都進(jìn)行釋放。但是！因?yàn)槭聦?shí)確實(shí)是兩人放的火，所以他們不得不進(jìn)行思考，另一人采取了什么樣的行為？
犯人甲當(dāng)然不傻，他根本無(wú)法相信同伙不會(huì)向警方提供任何信息！因?yàn)槿绻镆坏┨拱祝约哼@邊如果什么都沒(méi)說(shuō)的話，就可以瀟灑而去。但他同時(shí)也意識(shí)到，他的同伙也不傻，也會(huì)同樣來(lái)這樣設(shè)想他。
所以犯人甲的結(jié)論是，唯一理性的選擇就是背叛同伙，把一切都告訴警方！這樣的話，如果他的同伙笨得只會(huì)保持沉默，那么他就會(huì)是那個(gè)離開(kāi)的人。而如果他的同伙也根據(jù)這個(gè)邏輯向警方交代了，那么也沒(méi)有關(guān)系，起碼他不必服最重的刑！
這場(chǎng)博弈的過(guò)程，顯然不是顧及團(tuán)體利益的最優(yōu)解決方案。以全體利益而言，如果兩個(gè)參與者都合作保持沉默，兩人都可以無(wú)罪釋放，總體利益更高！但根據(jù)假設(shè)（人性），二人均為理性的個(gè)人，且只追求自己的個(gè)人利益。均衡狀況會(huì)是兩個(gè)囚徒都選擇背叛，這就是“困境”所在！
事實(shí)上，這種兩人都選擇坦白的策略以及因此被判4年的結(jié)局被稱(chēng)作“納什均衡”（也叫非合作均衡），換言之，在此情況下，無(wú)一參與者可以“獨(dú)自行動(dòng)”（即單方面改變決定）而增加收獲。
我們看一下官方釋意是多么難懂“所謂納什均衡，指的是參與人的一種策略組合，在該策略組合上，任何參與人單獨(dú)改變策略都不會(huì)得到好處?！?/strong>簡(jiǎn)單點(diǎn)講，如果在一個(gè)策略組合上，當(dāng)所有其他人都不改變策略時(shí)，沒(méi)有人會(huì)改變自己的策略，則該策略組合就是一個(gè)納什均衡。
推薦閱讀
全部文章分類(lèi)與整理（算法+數(shù)據(jù)結(jié)構(gòu)+計(jì)算機(jī)基礎(chǔ)），持續(xù)更新
【吐血整理】那些讓你起飛的計(jì)算機(jī)基礎(chǔ)知識(shí)：學(xué)什么，怎么學(xué)？
寫(xiě)公眾號(hào)15個(gè)月以來(lái)，這一路上的學(xué)習(xí)與收獲