博弈論里的囚徒困境怎麼解決？
無限次重複博弈的實驗結論，上面的答案都不完整，我來寫個完整的吧
首先定義囚徒困境具體的模型，背叛(Temptation)，一同合作(Reward)，一同背叛(Punishment)，合作(Sucker)四種收益應該有： T &> R &> P &> S
在 Axelrod 最開始的實驗中，TFT(一報還一報) 獲得了勝利。它的策略是，第一局先合作，然後每一局都複製對方上一局的策略。
這個實驗遠沒有結束，後面的才是精彩內容。
Nowak 為整個系統加入了雜訊，導致一定概率下，本應該是合作的，變成了背叛；本應該是背叛的，卻變成了合作。
實驗結果很悲觀，ALLD (永遠背叛) 成了最後的贏家。TFT 的優勢是，他們能互相促進合作，但可惜過於記仇無法對抗噪音，所以輸給了 ALLD。為了彌補 TFT 的不足，GTFT(慷慨的一報還一報)被介紹進來，在 TFT 的基礎上設定噪音，導致即使上一局對方背叛，這一局 GTFT 仍然有概率選擇合作。用寬恕來對抗背叛。
GTFT 擊敗 TFT 成為主流後，寬恕戰勝了背叛，很像一個全是好人的理想世界，此時 ALLC(永遠合作) 會成為新的主流。原因很簡單，ALLC 寬恕的效率比 GTFT 還高，更能促進合作發生。
ALLC最大的敵人就不用說了，自然是ALLD(永遠背叛)。你發現了沒，這是一個循環。
ALLD - TFT - GTFT - ALLC - ALLD，可以這麼理解，這是一個「誠實淳樸的人們合作趕走了壞人，幸福的生活卻又使人放鬆了警惕，壞人趁虛而入再次掌權，好人們再次合力趕走壞人」的故事。
最厲害的策略來了，發現了這個循環後，Nowak 為打破循環，引入新的策略WSLS(win-stay, lose-shift)：如果上一局的收益是S/P，那麼這一輪我就換另一種策略；如果上一局的收益是T/R，這一局我就維持上一局的策略不變。
WSLS 之間傾向於一直合作，如果因為雜訊產生了背叛，也會在一局內糾錯，僅僅弱於永遠寬恕的 ALLC。我認為有三種方法可以解決囚徒困境：
1.外部力量補充導致payoff改變。比如，選擇坦白的囚犯會受到組織的懲罰。
2.不固定次數的重複博弈。
之所以強調不固定次數，是因為根據「倒推法」，如果知道博弈次數，那麼在最後一輪就應該選擇「不合作」，因此在倒數第二輪也應該選擇「不合作」，一隻可以推至，在第一輪就應該選擇不合作。（reference： 維基百科 固定次數的囚徒困境）
3.教育
對於「教育」我的理解有這樣兩種：
- 共有知識的完全信息
這裡我認為的共有知識是指：對方知道我知道共同選擇合作是最好的選擇；對方知道我也知道他知道共同選擇合作是最好的選擇。也就是說不是基於相互之間的無強制力的信任，而是基於對方的common knowledge。
- 教育導致payoff的改變
比如，因為教育改變了對方對自己行為所帶來的內部utility改變了，就是說雖然事情的外部後果沒有變，但是由於愧疚或者其它情緒導致payoff發生了變化。
Bibliography ：在耶魯大學博弈論公開課中，教授Ben Polak提出，
解決囚徒困境的本質是一定要改變參與者的payoff，其具體提出了三種方法解決囚徒困境：
1.訂立具有強制力的契約、合同等。
2.重複博弈
3.教育
Polak教授同時強調了溝通並不能夠解決囚徒困境。原因是：
在缺乏外部約束的情況下，即使兩者串供商定選擇合作，「我」並不能知道對方會不會遵循這個約定。更重要的是，如果「我」確定對方會遵循了這個約定，那麼根據理性人原則（假設我是經濟學上理性的），為了自己的利益最大化，」我」應該選擇背叛。
1、利用無限次重複博弈（例如，經典的針鋒相對策略、冷酷策略等）
2、利用信息不完全（例如，聲譽效用、個體類型等）
3、利用心智模型，放鬆主體假定（例如帶有同情的博弈）
4、本方可以採取一些措施（如降低本方的收益，簽協議）讓對方有理由相信你沒有動機產生偏離，從而有動機產生合作歷史上曾經有人在真實環境中做過囚徒困境的實驗，發現重複博弈後的結果就是趨於合作。
其實經典博弈論中的「個體絕對理性」假設實在是太強了，因此後來有人就提出了「有限理性」的假設，即人們的計算能力是有限的，不可能用數學去計算分析完博弈的所有結果後再做出選擇（因為很多情況下人們並不知道該怎麼分析），而只是依據經驗做出選擇，然後再對結果進行學習（舉例來說，如果你沒學過博弈論，你可能就不知道該如何「理性」地分析囚徒困境，你所做的只是依據經驗做出選擇）。這個思想其實和生物進化論的思想差不多（或者機器學習也類似），其中的一個概念就是evolutionarily stable strategy。因此博弈論在某些方面還不夠完善，它還不太適合來進行「預測」。
囚徒困境之所以會成為「困境」，主要在於他們是『囚徒「，而且是分開監禁的，而現實中的參與者是有交流的，有interactions的。
在交流中，某些文化因素可以把外在性內在化（internalize externalities），比如機會主義行為會讓行為人丟面子這種。
另外，人之間的信任也能改善，這就是所謂social capital的作用先寫幾條經典「囚徒困境」的假設
- 參與人是理性的，目的是為了減少坐牢時間。
- 每個人關心的只有自己，不關心對方。
- 博弈只進行一次。
引用張維迎教授的《博弈與社會》一書的概念
博弈中的每個參與人的最優選擇依賴於別人的選擇，但在囚徒困境博弈中，每個人的最優選擇與他人的選擇無關。這種獨立於他人選擇的最優戰略稱為該參與人的佔優戰略。
也就是說，對於佔優戰略，是能給參與人帶來最大支付的，也就是在博弈時最先考慮的。
懶得畫圖了，百度的表。
顯然，對於每一個參與者來說，坦白是自己的佔優戰略，在佔優戰略下，兩個參與人的佔優戰略組合便組成了佔優戰略均衡，也就是（-8，-8）這個結果。
囚徒困境實際上是個體理性與集體理性的衝突，每個人想要自己不坐牢，就坦白，但是對於集體來說，肯定會走向兩人坦白的情況。
我們不妨倒回來思考一下：是不是在假設的前提下，限制了結果的走向？
首先，我們將逐個條件都改變一下，看看博弈結果會有什麼變化。
1，原博弈的兩位參與者都是零階理性共識的人，也就是，都不知道對方是否知道自己理性與否。那麼我們可以設想幾種情況
（1）若一個人零階理性共識，一個人是一階理性共識。即，A是理性，但不知道B理性，他會選擇坦白，B除了自己理性，還知道A也是理性，但是B不知道A是否知道自己理性。（有點繞，多讀兩次就好了。）最後結果還是B選坦白。（2）那麼如果A,B都是一階理性與上同理
（3）當有一方是二階理性時候，假設是B，那麼B知道A知道自己是理性的，而A只知道B是理性的，不知道B是否知道自己理性。如果A認為：我知道B是理性，但B不知道我理性，那B肯定坦白，我不能給他得逞，我也坦白，結果雙方坦白。
而對於B來說，他知道A理性，也知道A知道自己理性，但是不知道A是否知道自己知道他是理性的。自己不能虧啊，選坦白。（4）兩方都是二階理性共識時候。A知道B知道A知道B理性，B也知道A知道B知道A理性。好了簡單來說：雙方都知道雙方知道自己理性，會心一笑，達成共識，合作吧，都抵賴。
2.假定有一個人是愛慕另外一個人♂。或者男女愛慕也行，比如男的暗戀一個女生，他知道女生會坦白，那麼他為了女生會坦然選擇抵賴，出於自我犧牲，結果會是一個抵賴，一個坦白的情況。
3.假如博弈能多次進行，在重複剔除劣戰略之後，雙方會跳出局限，選擇合作。
嗯，不知道這樣解釋行不行。
（鑒於評論，已把所有名詞改成中文，之前的英文名詞只是為了清晰和效率，沒有充分考慮到知乎的政治正確）
由於囚徒困境里的「困境」是所有人選擇嚴格佔優策略 (佔優可解的)，也就是說有且只有這一個均衡，所以任何的精鍊都沒有用，所有的「解決」其實都從根本上改變了這個博弈的結構。
比較著名的「解決」就是很多人已經提到了的無限重複博弈，trigger strategy[這個我真不知道怎麼翻譯](第一輪先合作，如果對方第一輪不合作，之後就再也不合作)在一定參數條件下（第一期的偏離的獲利小於未來無限期合作均衡與不合作均衡差值的貼現和）能達到一直合作的均衡。
在有限重複博弈裡面因為逆向推導導致唯一的子博弈精鍊納什均衡是每一期都選擇不合作。然而由於人的有限理性，完全可以看作在期數足夠多的重複博弈中人們在剛開始也會保持合作，臨近結尾就不好說了。
事實上不僅僅是囚徒困境，在任何一個博弈的「困境」中，只要人們足夠耐心（貼現值足夠高)，任何一個其他的策略組合，如果每個人的收益都比這個「困境」高，那都可以成為無限重複博弈里一個均衡使得每一期都實現這個收益。(無名氏定理)
建議你有興趣的話，看一下《囚徒的困境：馮·諾伊曼、博弈論，和原子彈之謎》，書中比較詳細的分析了這個模型，並且提出多次博弈中的最優策略——一報還一報。
建立健全個人信用體系，將單一的博弈過程變成長期多次的博弈，多次博弈就如@曹懷寧 說的，一報還一報是最優的。即你先選擇相信對方，如果遇到對方背叛你，你在下一次博弈時懲罰他。
前面幾位說的都對。純粹理性帶來的問題，其實就需要跳出框框來找心理上有擊穿效應的解決方案。要麼建立堅固的信任，要麼把懲罰抬高到不可承受的程度。這些都是有社會成本的，比如現代社會的建立行業協會，上下游擔保聯盟，古代為結盟通常搞一些婚約等，落到實際社會中，方法很多很具體的，但都要大的長期投入。合作的根基還是信任、人心。中國社會有點放大《孫子兵法》，壞世界邏輯，英美講契約。就事論事吧，不要把問題太抽象化了。
看看黑社會是怎樣做的就最清楚了：
坐一次牢要十年，重複博弈的話能重複多少次？即使重複了，能碰上同一個夥伴的機會是多少？
1、安家費
只要囚徒保證不供出其他人來，他便能得到一筆安家費，家人可以衣食無憂，他坐牢也不用再擔心了。
2、恐嚇
如果囚徒供出同夥，則面臨幫會清算的危險，幫會的手段比政府厲害多了。
3、名聲
供出同夥被認為是「沒義氣」的表現，即使不用坐牢，一輩子也不能在朋友面前抬起頭。而且也不會有任何幫會肯收留，將來生計也會成問題。如果是局外人我就不說了，如果是局內人，
現實往往比粗略的理論複雜得多，很多囚徒困境只是看上去像囚徒困境罷了。就拿囚徒例子來說好了，聽說過坦白從寬，牢底坐穿，抗拒從嚴，回家過年嗎？
忍一時風平浪靜，
退一步海闊天空。
以前看過一個段子：
警察抓了兩個黑社會老大分開審訊，結果兩個老大在無交流的情況下打死不承認，結果只能以很小的罪名關了幾個月，出獄後有人問那倆老大為什麼不出賣對方，答：如果我出賣他，他手下的兄弟能饒得了我家人？反之亦然……
所以囚徒困境的解法除了雙方相互信任之外，還有一個解法是實力相當並互相忌憚
所以，各位要找可靠的同夥的時候，記得找實力和處境差別不大的，不然……圖片來源：Peter Eso | Academic, University of Oxford.
見Folk theorem (game theory).
Folk Thereom的結論為在完全信息的無限games中，任何feasible並且individually rational的payoff都可以被一個納什均衡所支持。Fudenberg Mashkin稍後證明了在一定的限制下，任何feasible並且individually rational的payoff都可以被一個subgame perfect equilibrium所支持。這個定理其實就回答了LZ的問題。解釋如下：
首先引入兩個概念：
多次博弈中feasible payoff的集合為下圖中的藍色區域，即直線連接最外層的所有payoff點。這個集合是所有在多次遊戲中可能的average discounted payoff的集合。
Individually rational payoff的集合為大於等於雙方minmax payoff的payoff的集合。在下圖的game中，不管對方怎麼玩，只要play not 都能得到至少1的payoff。所以individually rational payoff對於雙方都大於等於1。
下圖是一個囚徒困境。
對於兩個players來說，defect都dominate了cooperate。因此雙方都會選擇defect。而這並不是帕累托最優的結果。雙方都cooperate才是帕累托最優的。在單次遊戲中，納什均衡為(D,D)。
參照上面的例子，我們可以看出，雙方的minmax payoff都是0，因此在無線遊戲中，任何可行的雙方payoff都大於0的pair都可以成為一個納什均衡/SPE。
具體怎麼操作呢？最簡單的是一個Grim Trigger Strategy。
雙方都採取如下Strategy:
第一階段. 選擇C，直到對方選擇D，那時進入第二階段。
第二階段. 選擇D。那麼這時候雙方是否還有incentive選擇D呢？
假設因為人們的不耐心／未來的不確定，未來的payoff沒有現在的payoff那麼好，discount rate為x。那麼如果他一直選擇C，他的average discounted payoff為1。如果他選擇了D，那麼在選擇的那一回合他拿到了2，之後的所有回合都是0，這種情況下，他的average discounted payoff是 2(1-x)。
當x&>=1/2時，一直選擇C的payoff更高，因此他會一直選擇合作。
結論：在充分信息的情況下，無限次遊戲中，只要人們足夠耐心，那麼囚徒困境可解。偷懶複製了一下 @郭韓勇 的關於博弈論基礎的介紹,結果標註編號123 "假如囚徒甲、乙，1甲乙都不供，判五年，2甲乙都供，判十年，3甲乙中甲供，乙不供，則乙獲刑20年，甲不用坐牢。"
那麼在這個關係里,如無信任,雙方都擔心成為情況3種的乙方,那麼如果招供,那麼結果將會在坐牢0-10年,如果不招供將會在5-20..毫無疑問的是如果單方決策,招供的風險和利益比較合理. 所以這個環境才會被稱之為雙均得益的無解.
要想實現結果一,有2個途徑,其一,將雙方利益捆綁...可見結果一,甲乙一共坐牢10年, 結果二,甲乙一共坐牢20年,結果三甲乙一共坐牢20年. 如果可以將甲乙統一在一起,大家算總盈虧,則避免因為考慮分配的個人利益而損傷共同利益.
其二,懲罰機制. 有答案說在下次報復,那麼下次施展報復的一方並不能得到好處,因為預計被報復的人會堅持選招供,最後會進入結果二. 這裡的懲罰機制是指,單向懲罰,如不遵守協議,付出更大代價. 例如, 黑手黨的方法, 如果出現了結果三,那麼甲方出獄就面對被殺死的情況. 由另外體系的第三方執行的維護協議的方式.
如上.艾克斯羅德重複博弈實驗是囚徒困境的升級版。
轉自有哪些思想實驗的好例子？
艾克斯羅德做了一個實驗，邀請多人來參加遊戲，得分規則與囚徒困境類似，在遊戲中，對於A來說，當對方選C，他選D得5分，選C只得3分；當對方選D，他選D得1分，選C得零分。因此，無論對方選C或D，對A來說，選D都得分最多。這是A單方面的優超策略。而當兩個優超策略相遇，即A，B都選D時，結果是各得1分。什麼時候結束遊戲是未知的。他要求每個參賽者把追求得分最多的策略寫成計算機程序，然後用單循環賽的方式將參賽程序兩兩博弈，以找出什麼樣的策略得分最高。
第一輪遊戲有14個程序參加，再加上艾克斯羅德自己的一個隨機程序(即以50%的概率選取合作或不合作)，運轉了300次。結果得分最高的程序是加拿大學者羅伯布寫的"一報還一報"(tit for tat)。這個程序的特點是，第一次對局採用合作的策略，以後每一步都跟隨對方上一步的策略，你上一次合作，我這一次就合作，你上一次不合作，我這一次就不合作。艾克斯羅德還發現，得分排在前面的程序有三個特點：第一，從不首先背叛，即"善良的"；第二，對於對方的背叛行為一定要報復，不能總是合作，即" 可激怒的"；第三，不能人家一次背叛，你就沒完沒了的報復，以後人家只要改為合作，你也要合作，即"寬容性"。
來來，我來黑一下囚徒困境。當時在讀書的時候，我們的老師說讀書不要說什麼就是什麼，你們做過這個關於囚徒困境的真實實驗嗎？於是我們設計了一個實驗，在全校抽取了100組學生來做，最後的結果是：將近80%的學生選擇cooperate。選擇dominant strategy（自私自利）的學生中，大多數人都是學過博弈論的（哎，無話可說）。。。。我們老師說，他每個學期都要讓新生做這個實驗，每次的結果都是類似的。所以就像一樓說的，其實這個困境在現實生活中不太可能是一個困境（大部分的受訪者都認為我們挺蠢的，既然cooperate能得到6顆糖果，為啥不cooperate呢，莫名其妙），所以樓主還是有空去糾結別的東西吧
1、對合作行為給予獎勵，對不合作行為給予懲罰。這樣，囚徒困境中雙方不合作帶來的回報將不再是最高，明顯低於合作行為所得到的回報。
2、信息對稱。我知道你的選擇，你知道我的選擇，我知道你知道我的選擇，你知道我知道你的選擇，我知道你知道我知道你的選擇…
3、重複博弈。願意吃虧、誠實的人更容易得到別人的信任。因此，當博弈的次數足夠多的話，建立良好合作形象的人更能得到與別人合作的機會。
囚徒困境隱含的假設前提是交易是第一次且僅有一次呀。
要不你以為黑色會大哥是因為人格魅力而讓小弟頂罪而不是你招供我出去後殺你全家么
上面的答案已經很全面了，很多博弈論的教程都會指出1. 教育，2. 反覆大量進行博弈 和 3. 規則訂立。。。等（也許兩個囚徒相愛（不理性）了也能解決很多問題） 是解決囚徒困境的方法。竊以為研究博弈論的樂趣是通過分析觀察博弈者的動作及最可能做出的決策來採取應對方法，重點在於分析，對博弈者們互動的研究以及將其用於生活實踐。「解決這個困境」 本身很具有現實意義，不過看這倆囚徒如何在困境中相互反應，勾心鬥角（而且他倆都是純理性人）豈不是更有意思~方法總比困難多。囚徒困境如此普遍、麻煩，早就有人研究對策了。主要的一個方法在於：對作弊者嚴懲，以促成合作。
首先，你得發現陷入困境中的多個對象，有誰在作弊（破壞規定，只為自己利益）。對於被抓的兩名犯人，供出同伴的那個就是作弊者；對於同行業的企業，率先惡意降價、搶佔顧客的是作弊者。然而，發現作弊者其實並不容易。因為在有多個參與者的博弈里，現實中需要考慮的因素是多層面、很複雜的，看似是作弊產生的現象很有可能是其他因素引起的。
其次，對作弊者嚴懲。每個鼓勵合作的良好計劃里，通常都會包含某種懲罰作弊者的機制。一個坦白且供出同伴的囚徒可能遭到同伴朋友的報復，就像警察利用這點來威脅罪犯供出其他人，先是哄著你，只要你供出一個同夥，就放你自由，到了後面乾脆威脅你，若不供出同夥，我就放了你（難道大家都會相信你真的沒有出賣同伴，只是警察故意放你？）。同樣的，惡意競爭的企業，在真相大白後，可能遭到同行和顧客的鄙視、政府的處罰和打壓，接下來持續的利潤下降很可能超過先前作弊時賺取的利潤。
最後，在懲罰的程度和方式上，有一些探討。有人認為，懲罰的力度應該儘可能嚴厲，增大作弊者的損失促使大家不敢作弊，由於嚴厲的懲罰能夠起到威懾作用，那麼懲罰本身多嚴厲多殘酷就沒關係了，因為恐懼會使得大家不敢作弊，懲罰真正發生的情形是很少的。但這種觀點沒有考慮到偵查作弊者其實存在出錯的風險，嚴懲一個被冤枉的人將是眾人不願意看到的事。
懲罰的方式應該簡單、清晰、明確，便於參與者方便地計算出作弊的後果。於是有人提出「以牙還牙」的策略。密歇根大學的Robert Axelrod設計了一個二人囚徒困境博弈競標賽，參賽者通過電腦程序提交自己的策略，比賽結果是「以牙還牙」的策略獲得冠軍。該策略優勢在於，它首先選擇相信對方，竭盡全力促成合作，同時避免相互背叛。其他參賽者要麼太輕信別人，要麼太咄咄逼人。這驗證了現實生活中，人們選擇的「人不犯我，我不犯人，人若犯我，我必犯人」、「你可以騙我，但絕不要超過X次」、「一報還一報」等也是蠻有道理的。
但「以牙還牙」並非是一個完美的策略。現實中的合作歸根結底是人與人之間的交往，存在誤解和衝動的可能。電腦程序比賽沒有涉及人的思維和感性，才沒有暴露這個缺陷。1988年，加拿大發現前來訪問的蘇聯外交官從事偵察活動，當即宣布縮小蘇聯外交使團的規模，而蘇聯則以縮小加拿大在蘇聯的外交使團的規模作為回報，最後兩國關係逐漸惡化，外交合作難上加難。男女婚姻當中，若錯誤地認為對方的某些行為舉止是背叛的表現，就選擇決裂或背叛作為回應，也會得不償失、令人惋惜。所以，我們應該更加寬容和耐心，在發現對方有作弊行為的時候，仔細分辨，降低誤會的可能性；同時根據情況考慮給對方多幾次機會。
推薦閱讀：
