http://www.asyura2.com/11/lunchbreak48/msg/405.html
| Tweet |
http://ja.wikipedia.org/wiki/%E5%9B%9A%E4%BA%BA%E3%81%AE%E3%82%B8%E3%83%AC%E3%83%B3%E3%83%9E
囚人のジレンマ
出典: フリー百科事典『ウィキペディア（Wikipedia）』
移動： 案内, 検索
横山秀夫による小説及びそれを原作とした2004年のテレビドラマについては「第三の時効」をご覧ください。
囚人のジレンマ（しゅうじんのジレンマ、Prisoners' Dilemma）は、ゲーム理論や経済学において、個々の最適な選択が全体として最適な選択とはならない状況の例としてよく挙げられる問題。非ゼロ和ゲームの代表例でもある。この問題自体はモデル的であるが、実社会でもこれと似たような状況（値下げ競争、環境保護など）は頻繁に出現する。
1950年、アメリカ合衆国ランド研究所のメリル・フラッド (Merrill Flood) とメルビン・ドレシャー (Melvin Dresher) が考案し、顧問のアルバート・W・タッカー (A.W.Tucker) が定式化した。
目次
1 囚人のジレンマ
1.1 問題
1.2 解説
2 繰り返し型の囚人のジレンマ
3 繰り返し型の囚人のジレンマゲーム（ノイズあり）
4 その他
5 現実における囚人のジレンマ
6 関連項目
7 参考文献
8 外部リンク
[編集] 囚人のジレンマ
[編集] 問題
共同で犯罪を行った（と思われる）2人が捕まった。警官はこの2人の囚人に自白させる為に、彼らの牢屋を順に訪れ、自白した場合などの司法取引について以下の条件を伝えた。
もし、おまえらが2人とも黙秘したら、2人とも懲役2年だ。
だが、共犯者が黙秘していても、おまえだけが自白したらおまえだけは刑を1年に減刑してやろう。ただし、共犯者の方は懲役15年だ。
逆に共犯者だけが自白し、おまえが黙秘したら共犯者は刑が1年になる。ただし、おまえの方は懲役15年だ。
ただし、おまえらが2人とも自白したら、2人とも懲役10年だ。
なお、2人は双方に同じ条件が提示されている事を知っているものとする。また、彼らは2人は別室に隔離されていて、2人の間で強制力のある合意を形成できないとする。
このとき、囚人は共犯者と協調して黙秘すべきか、それとも共犯者を裏切って自白すべきか、というのが問題である。
2人の囚人の名前をA、Bとして表にまとめると、以下のようになる。表内の左側が囚人Aの懲役、右側が囚人Bの懲役を表す。たとえば右上の欄は、Aが懲役15年、Bが1年である事を意味する。
囚人B 協調 囚人B 裏切り
囚人A 協調 （2年、2年） （15年、1年）
囚人A 裏切り （1年、15年） （10年、10年）
[編集] 解説
囚人2人にとって、互いに裏切りあって10年の刑を受けるよりは互いに協調しあって2年の刑を受ける方が得である。しかし囚人達が自分の利益のみを追求している限り、互いに裏切りあうという結末を迎える。なぜなら囚人Aは以下のように考えるからだ。
囚人Bが「協調」を選んだとする。このとき、もし自分 (=A) がBと協調すれば自分は懲役2年だが、逆に自分がBを裏切れば懲役は1年ですむ。だからBを裏切ったほうが得だ。
囚人Bが「裏切り」を選んだとする。このとき、もし自分がBと協調すれば自分は懲役15年だが、逆に自分がBを裏切れば懲役は10年ですむ。だからBをやはり裏切ったほうが得だ。
以上の議論により、Bが自分との協調を選んだかどうかによらずBを裏切るのが最適な戦略（支配戦略）であるので、AはBを裏切る。囚人Bも同様の考えにより、囚人Aを裏切ることになる。
よってA、Bは（互いに裏切りあうよりは）互いに協調しあったほうが得であるにもかかわらず、互いに裏切りあって10年の刑を受ける事になる。合理的な各個人が相手の行動を所与として自分にとって「最適な選択」（裏切り）をする結果、全体としては「最適な選択」をすることが達成できないことがジレンマと言われる所以である。
なお、この場合のパレート効率的な組合せは、(2,2)、(15,1)、(1,15)の3点であり、(10,10) はナッシュ均衡ではあってもパレート効率的ではない。
[編集] 繰り返し型の囚人のジレンマ
上述したように、2人プレーヤーの囚人のジレンマのゲームを1回しかしない場合は、両者が「裏切り」を選択する。では囚人のジレンマのゲームを繰り返し行った場合はどうなるか。合計の懲役年数が最も小さくなるようにしたい。これは、囚人達がゲームの繰り返し回数を知っているかどうかによって変わる。
ゲームの繰り返し回数を囚人達が双方とも知っていた場合は、全ての回で囚人がともに「裏切り」を選択する事が分かっている。これは状況を最終回から順に帰納法的に考えてみれば分かる（後退帰納法）。
最終回のゲームの後にもうゲームをやらないので、最終回のゲームの戦略が他のゲームの戦略に影響する事はない。よって最終回のゲームの戦略はゲームを一回しかやらない場合の戦略と同様であり、囚人はともに「裏切り」を選択する。
最終回のゲームでは双方とも必ず「裏切り」を選択するのだから、最終回の一回前のゲームで自分が「協調」を選択しようが「裏切り」を選択しようが最終回のゲームには影響しない。よって最終回の一回前のゲームにもやはり駆け引き的要素は存在せず、このゲームでも囚人達はともに「裏切り」を選択する。
以下同様に考える事で、全てのゲームで囚人がともに「裏切り」を選択する事が分かる。
次にゲームの繰り返し回数をいずれの囚人も知らない場合を考える。1980年にロバート・アクセルロッドは、繰り返し型の囚人のジレンマで利得の多くなる戦略を調べるため、様々な分野の研究者から戦略を集めて実験を行った。（ただしこの実験には様々な批判もでている。たとえばKen Binmoreによる批判論文のサーベイ(山形浩生訳)を参照。） 実験には14種類の戦略が集まり、アクセルロッドはこれらを総当りで対戦させた。その結果、全対戦の利得の合計が最も高かったのは、「しっぺ返し戦略（tit for tat）」であった。「しっぺ返し戦略」とは、最初は「協調」し、以降は、前回相手の出した手をそのまま出す戦略である。
アクセルロッドは、続いて2回目の実験を行った。この実験には、62種類の戦略が集まった。前回の勝者が「しっぺ返し戦略」であることは伝えられていたため、集まった戦略はこれよりも高い利得を得ようと工夫されたものだった。それにもかかわらず、最大の利得を得たのは、またしても「しっぺ返し戦略」であった。
なお、実験の結果は、実験の具体的方法や他の戦略の種類、数にも影響されるため、「しっぺ返し戦略」が常に最強とは限らない。しかし、ある条件下では「しっぺ返し」戦略が「常に裏切り」戦略よりも有効であることを以下のように示すことができる。
例えば、2人のプレーヤーPaとPbが「協調」か「裏切り」かの戦略を選べるときの、それぞれの利得を示す。並んだ数字の左側はPaの利得、右側はPbの利得である。
Pa/Pb 協調 裏切り
協調 2, 2 0, 3
裏切り 3, 0 1, 1
ゲームが1回きりの場合、前に述べたとおり、ナッシュ均衡は（裏切り, 裏切り）のみである。しかし、ゲームを複数回行う場合、ゲームが次回も続く確率をpとすると、利得は以下のようになる。
Pa/Pb しっぺ返し 常に裏切り
しっぺ返し 2/(1-p), 2/(1-p) -1+1/(1-p), 2+1/(1-p)
常に裏切り 2+1/(1-p), -1+1/(1-p) 1/(1-p), 1/(1-p)
この場合、p>0.5において2+1/(1-p)<2/(1-p)となる。すなわち、相手が「しっぺ返し」戦略をとっている時に自分が「常に裏切り」戦略を取る利得がなくなり、（しっぺ返し,しっぺ返し）がナッシュ均衡となる。
[編集] 繰り返し型の囚人のジレンマゲーム（ノイズあり）
また、ノイズあり「繰り返し型の囚人のジレンマゲーム」というものが、考えられる。ここでノイズとは、「相手が協調しているにも関わらず、なんらかの理由で、裏切ったと解釈されてしまう」（あるいは逆に、裏切っているにも関わらず協調していると思い込む）というものである。
ノイズあり「繰り返し囚人のジレンマゲーム」では、しっぺ返し戦略はもはや最強ではなく、パブロフ戦略が強くなる。これは、前回うまくいったら今回も同じ行動を、前回失敗したら今回はその反対の行動をとるという戦略である。ノイズはどんなに微小であっても、しっぺ返しよりパブロフの方が強いことが理論的に示せる。また、ノイズがあってもなくても社会全体が、突然変異を除き1つの戦略で一様に覆われてしまうことは変わらない。
[編集] その他
しっぺ返し戦略とパブロフ戦略は、前回の行動のみから今回の行動を決定するというタイプの戦略であるが、これをもっと以前の情報をもとに今回の行動を決められるように、戦略空間を拡大することを考える。
すると、社会全体がある戦略に収束するのではなく、さまざまな戦略が誕生しては滅んでゆくような終わりなき進化がおこりうることがリンドグレーンによって示された。
[編集] 現実における囚人のジレンマ
現実世界でも囚人のジレンマないしそれに類似した例を見つける事ができる。例えば核兵器開発では、A国とB国が両方とも核兵器開発を止めれば平和が維持できるにもかかわらず、相手国が裏切って核兵器開発をはじめる恐怖に耐え切れず、双方とも核兵器開発をはじめてしまう（恐怖の均衡）。また低価格競争でも、A社とB社が両方とも値下げを止めれば利益を維持できるにもかかわらず、相手企業の値下げによりシェアが奪われる恐怖に耐え切れず、双方ともに値下げ合戦をして利益を圧縮してしまう。このように囚人のジレンマは政治・経済の解析にかかせない。
[編集] 関連項目
ジレンマ
パラドックス
ナッシュ均衡
パレート効率性
ベイジアン・ゲーム
ベイジアン・ナッシュ均衡
フォーク定理
合成の誤謬
スタグハントゲーム
複占
司法取引
[編集] 参考文献
Axelrod, Robert (October 1985). The Evolution of Cooperation. Basic Books. ISBN 0465021212. （邦訳 R.アクセルロッド 『つきあい方の科学――バクテリアから国際関係まで』 松田裕之、ミネルヴァ書房〈Minerva21世紀ライブラリー〉、1998年5月。ISBN 4623029239。）
Poundstone, William (January 1993). Prisoner's dilemma. Anchor. ISBN 038541580X. （邦訳 ウィリアム・パウンドストーン 『囚人のジレンマ――フォン・ノイマンとゲームの理論』 松浦俊輔、青土社、1995年3月。ISBN 4791753607。）
[編集] 外部リンク
（百科事典）「Prisoner's Dilemma」 - スタンフォード哲学百科事典にある「囚人のジレンマ」についての項目。（英語）
表・話・編・歴ゲーム理論のトピックス
定義 協力ゲーム - 非協力ゲーム - 進化ゲーム - ハイパーゲーム- 行動ゲーム
均衡 ナッシュ均衡 - 部分ゲーム完全均衡 - ベイジアン・ナッシュ均衡 - 逐次均衡 - 完全均衡 - 合理化可能性 - 進化的に安定な戦略 - パレート効率性- 戦略的補完性
ゲームのクラス 標準型ゲーム - 展開型ゲーム - 特性関数型ゲーム - 完全情報ゲーム - 不完全情報 - 繰り返しゲーム - ゼロ和 - 非ゼロ和 - 二人零和有限確定完全情報ゲーム
ゲーム 囚人のジレンマ - チキンゲーム - スタグハントゲーム
理論 ミニマックス法 - フォーク定理 - コアの極限定理 - アローの不可能性定理
関連項目 数学 - 経済学 - 進化論 - 集団遺伝学 - オペレーションズリサーチ - 社会生物学 - 環境社会学
「http://ja.wikipedia.org/wiki/%E5%9B%9A%E4%BA%BA%E3%81%AE%E3%82%B8%E3%83%AC%E3%83%B3%E3%83%9E」より作成
カテゴリ: ゲーム理論 | 思考実験 | 数学に関する記事
この記事を読んだ人はこんな記事も読んでいます（表示まで20秒程度時間がかかります。）
スパムメールの中から見つけ出すためにメールのタイトルには必ず「阿修羅さんへ」と記述してください。すべてのページの引用、転載、リンクを許可します。確認メールは不要です。引用元リンクを表示してください。
