囚人のジレンマ


ビルゲイツの面接試験−ジャンケン編
http://satoshi.blogs.com/life/2007/03/post_16.html


こういう問題はけっこう好きなので考えてみた。
こういう最適解が無い問題を囚人のジレンマというらしい、


パブロフ戦略が最善戦略として考えると、
(協調で裏切られたら逆をやる戦略)


協調はグーとパーを交互に出し25万づつで決定。


じゃあ裏切りはというと


すべてグーはパーをだされてしまってダメ


パーとチョキを交互にだしてしまうとチョキを出されてダメ


グーとチョキを交互にだしてしまうと相手がグーとチョキでくると
協調に戻らなくなってしまうのでできれば避けたい。


すべてチョキだと相手は絶対勝てないので
相手が負けてくれれば協調へ戻るという条件にすれば
相手は協調することが最善策となるのでこれを裏切りとする。


よって


最初はグーとパーを交互に出す。
裏切られたら(相手がパーに対してチョキを出したら)チョキを出し続ける。
相手がパーを出して負ければまたグーとパーを交互に出す。


となる。


いや、まだまだ。もっとつめてみる。


初回に近い段階でパーに対して相手がチョキを出した場合に
たまたまか裏切りか判別がつかない。


最初のうちは相手も手探り状態であり
たまたまである確率が高いのと
協調の意思を相手に伝えるために初回10回程度は
相手がチョキを出しても協調をつづける必要があると思う。


また、協調で出す順序をグーパーにするかパーグーにするかという
とこもつめてみる。


協調に入るタイミングは
1.1手目
2.裏切りから協調へ戻る場合
がある。


1.の場合、初回はできるだけ勝つ手数を増やすためパーを
出すのが最善かと考える。


2.の場合、裏切り回復の手が
チョキに対して相手がパーを出すという手順になる。
相手が協調する意思があるとすると(グーとパーを交互に出す)
次の手はパーの方が協調に入りやすい。


よってどちらも場合もパーグーの方が最適解になるかなと思う。


まとめると


10手目まではパーグーを繰り返す。
10手目以降、裏切られたら(相手がパーに対してチョキを出したら)チョキを出し続ける。
相手がパーを出して負ければパーグーを出す。


初回10回程度というところがあいまいなので、
相手の裏切りの明確なタイミングがあるかどうかとか、
相手が同じ考えの場合1000回パーグーのまま0円で終了してしまうので
協調時に何回目かまで引き分けがつづけば相手に合わせるとか
もっとつめれそう。


回答が楽しみ。