囚人のジレンマ
囚人のジレンマ（しゅうじんのジレンマ、）とは、ゲーム理論におけるゲームの1つ。お互い協力する方が協力しないよりもよい結果になることが分かっていても、協力しない者が利益を得る状況では互いに協力しなくなる、というジレンマである。各個人が合理的に選択した結果（ナッシュ均衡）が社会全体にとって望ましい結果（パレート最適）にならないので、社会的ジレンマとも呼ばれる。
1950年に数学者のアルバート・タッカーが考案した。ランド研究所のとの行った実験をもとに、タッカーがゲームの状況を囚人の黙秘や自白にたとえたため、この名がついている。
囚人のジレンマではゲームを無期限に繰り返すことで協力の可能性が生まれる（後述）。囚人のジレンマは、自己の利益を追求する個人の間でいかに協力が可能となるかという社会科学の基本問題であり、経済学、政治学、社会学、社会心理学、倫理学、哲学などの幅広い分野で研究されているほか、自然科学である生物学においても生物の協力行動を説明するモデルとして活発に研究されている。
共同で犯罪を行ったと思われる2人の囚人A・Bを自白させるため、検事はその2人の囚人A・Bに次のような司法取引をもちかけた。このとき、「2人の囚人A・Bはそれぞれ黙秘すべきかそれとも自白すべきか」というのが問題である。なお2人の囚人A・Bは別室に隔離されており、相談することはできない状況に置かれているものとする。
2人の囚人A・Bの行動と懲役の関係を表（利得表と呼ばれる）にまとめると以下のようになる。表内の (○年, △年) は2人の囚人A・Bの懲役がそれぞれ○年、△年であることを意味する。たとえば表の右上の欄(10年,0年)とは，「Aが黙秘・Bが自白」を選択した場合、Aの懲役は10年、Bの懲役は0年であることを意味する。
2人の囚人A・Bにとって、「互いに自白」して互いに5年の刑を受けるよりは「互いに黙秘」して互いに2年の刑を受ける方が得である。しかし、2人の囚人A・Bがそれぞれ自分の利益のみを追求している限り、「互いに黙秘」という結果ではなく「互いに自白」という結果となってしまう。これがジレンマと言われる所以である。このようなジレンマが起こるのは以下の理由による。
まず囚人Aの立場で考えると、囚人Aは次のように考えるだろう。したがって、囚人Aにとっては，囚人Bがどのように行動するかにかかわらず自白することが最適な選択ということになる。これは囚人Bにとっても同じであるため、囚人Bも囚人Aと同じ考えによって自白することが最適な選択である。このような理由で2人の囚人A・Bは結果的に「互いに自白」という行動をとることとなる。
重要なのは、「囚人Bが自白してしまうのではないか」という懸念や恐怖から囚人Aは自白するわけではなく、囚人Bが黙秘しようが自白しようが囚人Aは合理的に自白する、という点である。
2人の囚人A・Bにとって「互いに黙秘」することがパレート最適であるにもかかわらず，2人の囚人A・Bがそれぞれ合理的に自白するという「互いに自白」という結果はナッシュ均衡ではあってもパレート最適ではない。
2人の囚人A・Bが「互いに黙秘」することを「協調」と言い換え，「どちらかが黙秘しているとして自分だけが自白して釈放してもらおう」とすことを「裏切り」と言い換えたとき，結果的に両者は「裏切り」を選択することとなる。
囚人のジレンマのゲームを一回しか行わない場合は上で説明したように両者が「裏切り」を選択するが、それに対しゲームを複数回行った場合（繰り返しゲーム）における2人の囚人の行動は、彼らがゲームの繰り返し回数を知っているか否かで異なる。
2人の囚人がゲームの繰り返し回数を知っている場合は有限繰り返しゲームと呼ばれ、この場合には2人の囚人が全てのゲームで「裏切り」を選択することが知られている。証明は、最終回のゲームから逆順に以下の帰納法を行うことで示せる（後退帰納法）。以下ゲームの繰り返し回数を"n" とする。2人の囚人がゲームの繰り返し回数を知らない場合は無期限繰り返しゲームと呼ばれる。有限繰り返しゲームにおいては、最終回のゲームから順に後退帰納法を適用することで全てのゲームで裏切りを選択するのが均衡となることを導いた。しかし，無期限繰り返しゲームではゲームが終了する確定的な期限がないので後退帰納法を適用できず、協調の可能性が生まれる。
このことを説明するため、以下の利得表で表される囚人のジレンマゲームを考える。なお以下では，数学的な説明のために「囚人」を「プレーヤー」という言葉で置き換える。この表は2人のプレーヤー formula_1 と formula_2 が「協調」か「裏切り」かの戦略を選ぶときの、１回ごとの利得を示す。並んだ数字の左側は formula_1 の利得、右側は formula_2 の利得である。なお、「利得」とは得られる利益を意味し、多い方がよい。
そして次のを考える。
お互いにトリガー戦略をとっているときに自分がこの戦略から逸脱するインセンティブがなければ、トリガー戦略がナッシュ均衡になることが示される。
最も簡単なケースは、プレーヤーが将来を割り引かず、常に明日のことを今日と同じぐらい大事に思う場合である。ゲームを無限に何度も繰り返すものとして、各プレイヤーが無限回の利得を平均した平均利得を最大化すると想定しよう。互いにトリガー戦略をとると互いに協調しつづけることになるので毎回の利得は2であり平均利得も2である。一方、自分がトリガー戦略から逸脱して裏切った場合、裏切った回は3の利得を手に入れるがその後は相手も裏切るので自分の利得はせいぜい1にしかならない。1回だけ利得3でその後ずっと毎回利得1なので平均利得は1になるが、これはトリガー戦略の平均利得2を下回る。つまりプレイヤーはトリガー戦略から逸脱すると長い目でみて損をする。したがって互いにトリガー戦略から逸脱せず協調しつづけるのがナッシュ均衡になる。これにより協調が生まれる可能性が示される。
ナッシュ均衡を生み出す戦略はトリガー戦略のみに限らない。たとえば最初は協調し以降は前回相手の出した手をそのまま出すしっぺ返し戦略も、逸脱するインセンティブがないので均衡となる。このほか協調を実現する均衡は無数に存在する。また、互いに裏切り続けるのも均衡として残る。このように無数の均衡が存在することはフォーク定理で示される。
上記の平均利得を最大化するという設定は、プレイヤーが無限に忍耐強くて将来を割り引かないことを意味しており、現実的とはいえない。プレイヤーが将来を割り引く場合については、次の通りである。
プレイヤーは将来の利得を一定の割引因子 formula_5 で割り引いていくものとし、そうして割り引いた割引利得の総和を最大化するものと想定しよう。お互いトリガー戦略をとると互いに協調しつづけるので、毎回の利得は2であり割引利得の総和は
である。一方、自分がトリガー戦略から逸脱して裏切った場合、裏切った回で利得3をとるが、その後の利得はせいぜい1であるので、割引利得の総和は
である。すなわち，formula_8 であれば formula_9 となるので，裏切っても割引利得の総和が増えず、裏切るインセンティブがないので、トリガー戦略はナッシュ均衡になる。すなわち割引因子が十分に高い場合に協調が生まれる可能性がある。
ここまではゲームを永久につづける無限（infinitely）繰り返しゲームを考えたが、これは現実的とはいえないので、その代わりに無期限（indefinitely）繰り返しゲームを考える。無期限繰り返しゲームとは、ゲームが確定的に終わる期限はないが、ゲームが確率的に終わる可能性を想定する。ゲームの終わる確率が十分に小さければトリガー戦略がナッシュ均衡になり、協調の可能性が示される。
ここまでは相手の行動を完全に観測できると想定した。現実には「相手に協調してもらったのに裏切られたと誤解する」「裏切られたのに気付かない」というように、他人の行動を不完全にしか観測できないことが多い。このような不完全観測のもとでの無期限繰り返し囚人のジレンマの理論は近年大きく発展している。
不完全観測のケースでは、相手の他のプレイヤーの行動を不完全ながら表すシグナルを観察できるものとし、誰もが観察できるシグナルがある場合を公的不完全観測、各人自分しか見られないシグナルを観察する場合を私的不完全観測という。
公的不完全観測のケースは比較的分析が容易である。完全観測下のトリガー戦略に似た戦略で協調が生まれる。フォーク定理は1994年にきわめて緩い条件のもとで証明された。
一方、私的不完全観測のケースは分析が困難で、いまだ研究途上にある。私的不完全観測では協調を生み出す戦略を見つけること自体が難問で、長い間ゲーム理論の未解決問題として有名であった。この難問に初めて答えが出たのは1997年のことで、きわめて高い精度で人の行動を私的観測できる場合の囚人のジレンマで協調を生み出す戦略が見つかった。また、各期の終わりに集まってコミュニケーションをとれる場合に限っていえば、1998年に一定の緩い条件のもとでフォーク定理が証明された。コミュニケーションを取れない場合については、相手が今までみてきたことを全く気にする必要のないような特殊な均衡をつくる信念不問アプローチが多くの成果を挙げている。2002年には信念不問アプローチにより囚人のジレンマの均衡を簡単につくる方法が発見され、本格研究が進展し始めた。そして2012年、ついに私的不完全観測下のフォーク定理がかなり緩い条件のもとで証明された。
企業の値下げ競争、公共財の供給、環境問題、共有資源の管理、自由貿易や軍縮のための国際協力など、現実社会における事象にも囚人のジレンマを使って説明できるものは多くある。
それどころか、囚人のジレンマはあらゆる商談についてまわる。商品交換の機会は典型的な１回限りの囚人のジレンマの状況を含む。取引によって互いに利益を得ることができるが、取引相手を騙すことで自分の利益を増やすことができるからである。具体的には、買い手が期日までに代金を支払わない、売り手が商品を引き渡さない、不良品を売りつける、といった裏切りである。取引が実現するには裏切りをコントロールする仕組みが必要だが、その仕組みは取引の繰り返しによっても確保される。取引相手が裏切ったら将来の取引をやめるという脅しをかけあうことで裏切りを阻止するのである。
政治学者のアクセルロッドは、無期限繰り返し囚人のジレンマの競技会を企画し、各分野の社会科学者からコンピュータ・プログラムを募って対戦させた。その結果、しっぺ返し戦略が優勝した。さらにアクセルロッドが参加プログラムについて進化シミュレーションを走らせたところ、生き残った戦略のなかでしっぺ返し戦略の数が最大であった。アクセルロッドはこれらの結果にもとづいて、しっぺ返し戦略は善良・報復・寛容・明快を兼ね備えており人間の協力全般にとって適切なパラダイムである、と主張した。この主張を鵜呑みにする社会科学者は少なくない。
アクセルロッドの研究は大きな反響を呼び、これ以降、進化生物学、社会学、政治学、コンピュータ科学などにおいて、さまざまな戦略を戦わせて、どの戦略が生き残るかをみるコンピュータ・シミュレーションが行われるようになった。このようなアクセルロッド流シミュレーション研究は、均衡の存在を数学で証明する本来のゲーム理論とほとんど関係がない。
アクセルロッドの研究はゲーム理論研究者の間で評判がよくなかった。ケン・ビンモアらゲーム理論研究者はアクセルロッドを次のように批判する。
アクセルロッドはゲーム理論からの批判を意図的に無視し続けているという。
なお、ゲーム理論においてアクセルロッドの業績が全否定されているわけではない。ビンモアによると、アクセルロッドの貢献はただ一点。フォーク定理が存在を証明する無数の均衡の中から特定の均衡を選ぶことが重要であると気づかせてくれた点にある。進化ゲームによる均衡選択は今やゲーム理論の均衡選択問題で標準的なアプローチになっている。アクセルロッドはその先駆者である、という。
以下にアクセルロッドの競技会に参加した戦略の例を記す。
囚人のジレンマの標準的なゲームでは二人のプレイヤーが同時に行動する。これに対して、プレイヤーの間で行動のタイミングがずれるゲームは一般に信頼ゲームと呼ばれるが、一方向の囚人のジレンマとも呼ばれる。一方向の囚人のジレンマは、同時行動の囚人のジレンマと同じように、一回限りでは協力が成立しないが、無期限に繰り返すと協力が成立し得る。
社会学では囚人のジレンマを3人以上の集団に拡大したものを社会的ジレンマと呼ぶことがある。この意味での社会的ジレンマは、社会において(1)各人が協力か非協力かを選ぶ、(2)各人にとっては協力よりも非協力を選ぶほうが望ましい結果を得る、(3)全員が非協力を選ぶと全員が協力を選んだ場合より誰にとっても望ましくない結果におちいる、と定義される。
社会学では、社会的ジレンマを多人数囚人のジレンマに限るのは社会的ジレンマの定義として狭すぎるという意見がある。社会的ジレンマの定義を拡張し、社会的ジレンマを全てのナッシュ均衡がパレート非効率であるゲームと定義するとか、さらにはナッシュ均衡がパレート効率である多人数チキンゲームを社会的ジレンマに含めるといったことがある。
直接互恵は、トリヴァースが提唱した進化生物学の概念であり、個体間の協力が進化するメカニズムの一つである。直接互恵では、2つの個体が繰り返し出会い、出会うたびに協力か裏切りを選ぶ。自分が今回協力すれば相手も次回協力してくれるかもしれないので協力は有利かもしれない。この直接互恵は、ゲーム理論の繰り返し囚人のジレンマに相当する。
アクセルロッドが行った囚人のジレンマのコンピュータ・トーナメントでは単純なしっぺ返し戦略が優勝したが、しっぺ返し戦略の弱点はすぐに見つかった。「震える手」や「曖昧な心」による誤作動があると、しっぺ返し戦略の成績は悪化する。単純なしっぺ返し戦略では間違えて裏切ると報復合戦に陥って間違いを修復できないからである。そこで、しっぺ返し戦略に代わって「寛容なしっぺ返し」戦略が台頭する。これは相手が協力するときは常に協力するが相手が裏切っても時々協力する戦略である。
次いで、さらに単純な「勝てばそのまま負ければかえる」戦略が台頭する。これは、うまくやっている時は手を替えないが、さもなければ替えるという戦略である。「勝てばそのまま負ければかえる」戦略は、成績の計測次第で「しっぺ返し」や「寛容なしっぺ返し」より強い。しっぺ返し戦略は裏切者の多い社会において協力を促進するが、一旦協力が確立されると「勝てばそのまま負ければかえる」戦略のほうがもっと協力を維持できる。
協力を促す戦略は無数にあるが、その一般法則は次の通りである。同じ２つの個体が再び出会う確率"w"が、協力行動の費用 "c" と利益 "b" の比率を上回る場合（"w" > "c" / "b"）に限り、直接互恵は協力の進化を促す。