きつねたてにっき

るる鯖で人狼をプレーしているつるつるの考察。コメントで意見とか残してくれると喜びます。最新トリ:Jet◆SgN.usdTyF

最終日前に狐候補を占うべきか -人狼と囚人のジレンマ-

 この記事では、最終日前に狐候補を占うべきかという問題を題材に、人狼囚人のジレンマの関係について考えたいと思います。本記事を書くにあたって、るる鯖の夕霧氏の意見*1を参考にさせて頂きました。

占い師は狐候補を占うべきか

 まず、題材として狐入りの配役で起こりうる次のような状況を考えます。最終日前の夜に、以下の4人が生きているとします(つまり奇数進行です)。

A : 占い師
B : 狼
C : 村人
D : 狐 or 村人

 占い師AはBとCを既に占っており、それぞれ狼と村人だと知っているとします。また、Dはまだ占っておらず、狐か村人の可能性があるとします。このような状況で、占い師は誰を占うべきで、狼は誰を噛むべきでしょうか。Dが狐の場合には占い師はDを占わないと、村に勝利は無くなってしまいます。一方で、Dを占って呪殺が出た時に狼がD以外を噛み、2死体が発生すると狼の勝ちになってしまいます。


 整理するために、場合分けをして考えてみましょう。まず、Dが村人であれば、占い師がどこを占って、狼がどこを噛んでも村の勝ちです(前提として占い師がCやDの信用を取れていると仮定しています)。したがって、Dが狐の場合に限定して考えます。

占い師がDを占う 占い師がD以外を占う
狼がDを噛む 村の勝利 引き分け
狼がD以外を噛む 狼の勝ち 狐の勝ち

上の表を見ると分かるように、

  • 占い師視点は、狼がD以外を噛む場合にはどこを占っても負けなのでどっちでも良く、狼がDを噛む場合にはDを占うべきだと分かります。したがって、占い師は常にDを占うべきです。
  • 狼視点は、占い師がDを占う時にはD以外を噛むべきで、占い師がD以外を占う時にはDを噛むべきだと分かります。このように、狼視点は占い師の行動によって取るべき戦略が変わります。

 占い師の最善の行動はDを占うことですが、この場合には狼はD以外を噛むことが最善の行動になります。ところが、占い師(村陣営)にとって、狼にはDを噛んで欲しいはずです(表から分かるように、Dを占う場合も、占わない場合も村にとっては狼がDを噛んだ方が利益になります)。つまり、占い師は、狼にはDを噛んで欲しいが、自分の利益を追求すると狼はDを噛まなくなってしまうのです。この問題を考える上で、「囚人のジレンマ」が参考になります。

囚人のジレンマ

 まず、簡単に囚人のジレンマについておさらいします*2。二人の囚人A, Bがいて、司法取引を持ちかけられます。

  • 二人とも黙秘すれば、二人とも懲役2年
  • 二人とも自白すれば、二人とも懲役5年
  • 片方が自白して片方が黙秘すれば、自白した方は釈放で、黙秘した方が懲役10年

AとBの行動による損得を表にまとめると、

Aが自白 Aが黙秘
Bが自白 A懲役5年、B懲役5年 A懲役10年、B釈放
Bが黙秘 A釈放、B懲役10年 A懲役2年、B懲役2年

 表から分かるように、Aは常にBを裏切って自白した方が得であり、Bも同様であるのでともに自白することになります。ところが、共に黙秘(協力)した場合に比べてAもBも損していることになり、ここに囚人の「ジレンマ」があるのです。
 この例のように、1回だけのゲームの場合には、囚人達は常に裏切ることになります。ところが、複数回、このゲームを繰り返す場合には状況が変わってきます。実は、囚人たちの最善の選択はゲームが有限回行われるか、無限回行われるかに応じて変わります。有限回のゲームでは、簡単な帰納法を用いた議論により、最善の選択は「裏切り」だと証明できます*3。一方、無限回繰り返すゲームでは、協力が選択される可能性が生じます。詳しい説明は囚人のジレンマ - Wikipediaを読んでもらうとして、ポイントは、協力を選択するのは自分が裏切ると相手も次のゲームから裏切りを選択するので、総合的に見て損をするからです。

 このような単純化が行われた囚人のジレンマの設定に比べ、現実の経済の問題や人狼ゲームは繰り返しの状況がより複雑です。まず、囚人のジレンマではプレーヤーが固定ですが、人狼ゲームはゲームに参加するプレーヤー自体が変動しています。囚人のジレンマにおいては、相手が固定であり、今日自分が裏切ると明日に損するので、無限回繰り返す場合には協力を選択する可能性が出てきました。ところが、人狼ゲーム、特に毎回メンバーが変わる野良試合では、ランダムCNを採用していた場合、相手の中身がゲーム中に特定できない場合が多く、特定の相手のこれまでの選択を考慮してゲームをすることは少ないと思われます。つまり、実質的に1回だけの囚人のジレンマを行ってる状況に近く、毎回裏切るという選択をすることになります。
 最初の占い師が狐候補を占うべきかという問題に戻りましょう。もし、この設定のゲームを狼と占い師を固定して、何度も繰り返すとします(これは現実の人狼とは別のゲームです)。占い師が毎回Dを占うとしたら、狼がそれに合わせてD以外を噛むことになり、常に狼が勝ってしまうことになります。もちろん、占い師はそうならないように、D以外を占う時も混ぜて、狼にDを噛むモチベーションを与えるべきです。結論から言うとこのゲームでは占い師は1/3より少し小さい確率で、Dを占うべきだと結論できます。一方で、普段の人狼ゲームでは、狼と占い師は毎回違い人であり、相手プレーヤーの前回の選択が考慮される可能性は極めて少ないでしょう(この設定と同じ状況が生じる回数は多くないでしょうから)。そう考えると、占い師はDを占った方がいいと結論できます。

 最後に現実の人狼とは別ゲーなので、重要ではありませんが、固定メンバーで繰り返す場合になぜ1/3という数字が出てくるのか説明しておきます。仮定として、占い師は確率pで狐候補Dを占い、狼は確率qでDを噛むとします。また、引き分けの価値は勝利の価値1に対して1/2だとします*4。それぞれ、起こりうる事象の確率は以下の表のようになります。

占い師がDを占う(確率p) 占い師がD以外を占う(確率1-p)
狼がDを噛む(確率q) 村の勝利:確率pq 引き分け:確率(1-p)q
狼がD以外を噛む(確率1-q) 狼の勝ち:確率p(1-q) 狐の勝ち:確率(1-p)(1-q)

この時の村の得られる利益(勝ちを1、引き分けを1/2として)の期待値は
{ \displaystyle
pq + \frac{1}{2}(1-q)q = \frac{pq}{2} + \frac{q}{2}
}
であり、狼の得られる利益の期待値は
{ \displaystyle
p(1-q) + \frac{1}{2}(1-q)q = q\left( \frac{1}{2} - \frac{3}{2}p \right) + p
}
です。占い師と狼は自分の得られる利益の期待値を最大にできるように、確率pやqを設定するはずです。村の利益の期待値は、「もしqがpに依存しないなら」pを大きくした方がよいので、p=1、つまり占い師は常に狐候補を占います。実際には、狼は占い師の選択に依って、確率qを変えるはずです。狼の得られる利益の期待値を最大にするqの値は{ \displaystyle \left(\frac{1}{2} - \frac{3}{2}p \right) }の符号に依って変わります。{ \displaystyle p < \frac{1}{3} }の場合にはq=1、{ \displaystyle p > \frac{1}{3} }の場合にはq=0を取ると、狼の利益は最大化されます。つまり、占い師がDを占わない傾向にある時({ \displaystyle p < \frac{1}{3} })には狼はDを噛んだ方がよく、Dを占う傾向にある時には({ \displaystyle p > \frac{1}{3} })にはDを噛まない方がよいのです。この確率pに応じた、狼の選択するqの値を村の利益の期待値に代入してみましょう。すると、

  • { \displaystyle p < \frac{1}{3} }の場合:村の利益の期待値{ \displaystyle = \frac{1}{2} + \frac{1}{2} }
  • { \displaystyle p > \frac{1}{3} }の場合:村の利益の期待値{ \displaystyle = 0 }

つまり、占い師は1/3より小さいなるべく大きい確率で狐候補Dを占えば、村の利益の期待値を最大化できるのです。

その他の例

今回は特に、最終日前に占い師が狐候補を占うべきかどうかという問題をピックアップして議論しました。
この問題の場合には、人狼が単発のゲームではなく、同じ環境で繰り返し行うゲームであるという効果はプレーヤーの行動には(ほとんど)影響せず、単発のゲームであった場合と同じ選択(つまり、占い師は常に狐候補を占う)をするという結論でした。
しかし、他の問題の場合には、ゲームが繰り返し行われるという効果がプレーヤーの選択に影響を与えると思われます。例えば、

  • 初日呪殺時の位置情報推理
  • 柱を村置きできるかどうか

などがその例でしょう。

*1:No.397963「12B」村

*2:囚人のジレンマの詳しい内容はここではなくて、適当な文献で読んでもらった方がいいと思うので、知らない人は囚人のジレンマ - Wikipediaなどを参照してください

*3:囚人のジレンマ - Wikipediaなどを参照。お互いに合理的な選択をするという仮定があります。現実問題としては合理的な選択をしない可能性があるので、その辺はより複雑になると思われます。

*4:この値はその人の価値観や、そもそもの村の勝率などによって変動すると思われます。例えば、ここでは簡単のために1/2と設定しました