Subscribed unsubscribe Subscribe Subscribe

12A猫で学んだこと-Memoir-

...What are you learning now?

参加人数が非常に多いときの狼数の話-ゲームをするためには, 何人を狼にすればいいの-

日本では, Are you a werewolf?(人狼)という名前でおなじみのゲームですが, 元々は, Mafiaという, マフィアが市民を殺していくゲームでした. 夜な夜な村人に人狼に喰い殺される...というゲームではなく, マフィアが市民を殺していく... うーん, 自分は人狼の背景設定の方が好きかな? 「夜は狼の美少年/美少女」と, 「夜はマフィアになる美少年/美少女」では, 前者の方が魅力的ですよね!

研究者によって, いくつか論文を発表されています. その仲で自分が面白いなーと思ったのがあったので, 紹介しようと思っています. 『(対人の人狼で)強くなりたい!』という人には露にも役にたたない内容となっております.

本日のネタはこちら!

Braverman , Etesami , Mossel : Mafia: A theoretical study of players and coalitions in a partial information environment

 

この論文の前半部分の結果は, 大勢の人狼のゲームをする時に, 参加者のうち, どのくらいを何人を狼にすれば, ゲームとして成立するのか? という問題に対して, 答えを与えてくれています. ゲームが成立するというのは, ここでは, (参加者が増えていった時)"村勝率が0や1にならない" ということを意味しています. ゲームを始める前から勝利が分かっていたり, 敗北が分かっているのは 面白くないですよね!

複雑な状況を考えると難しいので, 村人と狼しかいないゲームを考えましょう. (そんなゲームはつまらないよね! という突っ込みはナシでお願いします....) 参加者の数をN人としましょう. 狼の数を, f(N)と書くことにします. Nが大きくなる時, 最初の狼の数を何人にすればゲームとして成立するでしょうか?

例えば, "参加者がどれだけ大きくなったとしても, 狼は1人. 最初から1匹狼で頑張れ!"(f(N) = 1 )では, (数学的に妥当なシンプルな仮定をおいた時)参加者の数(N)が大きくなった時に必ず村勝ちになります. 数式を使って説明することもできますが, 人狼をプレーしたことをある人なら感覚的に分かると思います. ..."80億人の村人に対して, 貴方1人が人狼です. さて, 勝負をしましょう."...勝てる気がしませんね. (80億人の中から, 3人 or 4人1Wの最終日を作るまで生き残るって, ほぼ無理ですよ.) 逆に, 参加者の数Nに対して, "狼の数を大体Nの半分より少し少ないくらいにしよう"(e.g. f(N) = 1/2 N - 2 とか) この場合だと, 狼勝ちになっちゃうことは, 人狼をプレーしたことのある人は, 感覚的に 分かりますよね。 占い師のいない村で, 100グレー49Wとか, 村人が勝てると思いますか? ...ほぼ狼勝ちでしょう.

 

じゃあ, どれくらいの狼数にすれば, ゲームとして成立する...村陣営が勝利する確率, 狼陣営が勝利する確率がどちらも1に近づかないのか? 論文の結果は, 「f(N) = (定数) × ルートNぐらいにすると, Nが大きくなった時に, 村人の勝率が0になったり, 1になったりしないよ!」 と教えてくれています. 素朴に考えると, 100人で10人ぐらいのオーダーの狼数, 10000人で100程度のオーダーの狼数. これぐらいの割合で最初の狼数を決めると, 楽しいゲームになるね! ということです.

 

 

...「だから, 何だ?」と思われるかもしれません... だけど, ここは社会学的想像力(= かなり無理筋な議論)を働かせて, この結果から色々考えてみるのは面白いのかもしれません. とりあえず, 自分が考えたことを2つほど.

 

 

●「仲間を知っている」 + 「仲間以外をゲームから排除できる」ことの強さの意味. => 自分自身の集団の大きさを2乗した程度の集団と同じ力を持つ.

昼の間の処刑はランダムに選んだ人を吊る...これで狼の組織票作戦を無くしたとしても, 夜の間の噛みで, 狼以外の人を確実にゲームから排除できます. 狼のこの能力が持つ力の意味を, プレイヤーの数に置き換えてみることを考えます. すると, それは狼の人数を2乗したのと同じぐらいの村人がいるのと同じ状況なんだな. というのが, 考えたことの1つ目です.

 

人狼とは似ているゲームとして, 違うゲームを考えましょう.
人狼と村人陣営がいるのですが,
相違点1. 人狼は夜の噛みができない.
相違点2. 人狼は仲間が誰か知らない.
昼の吊りだけで, 人を1人ずつゲームから除外していき, 人狼陣営か村陣営の数が0になったら, 残った陣営の勝ちというゲームを考えます.
(きちんと計算をしていないのですが,) この条件にすると. 参加者Nに対して, 狼数はf(N) = (0 〜 1の定数) * N でゲームとして成りたつ = (村勝率 0 ~1の定数になる) この意味で, 「噛むことが出来る」 + 「仲間を知っている」ことによる 狼の能力は, 陣営の数に換算すると, 本来の陣営の数の2乗くらいになるんだなぁ...と思いました.

 

上記のことを踏まえて, 実際の社会であり得るかもしれない状況を考えましょう.

 

●派閥の力.
*(状況) 権力争いを行っている集団があります. 集団の実験を握ろうとしている派閥がありました. その派閥の人だけではなく, 他の人間が権力の座を目指して水面下で闘争を繰り広げています. 1ヶ月で1人の人が無作為に, 脱落します. 次の1ヶ月では, (派閥の暗躍によって)その派閥に属していない人間が, ランダムに1人権力争いから脱落していきます. 以降これが繰り返されていきます. その派閥の人間が全て権力争いから脱落するか, 集団の中でその派閥が過半数になり, その派閥が権力を掌握するか, それぞれの確率は?

 

...この問題を非常にシンプルに捉えると, 占い師無しの人狼の問題と非常に似ていることに お気づきいただけると思います. 「仲間を知っている」 + 「仲間以外を集団から排除できる」ことはやっぱり民主主義の中で強いんですね. 派閥の力はやはり強いのです. この問題設定の状況なら, 組織の中で権力を握ろうとする派閥は, 組織の拡大に合せて自分自身の派閥の大きさを その平方根程度の大きさ以上で拡大させていかなければならない. というのが, 論文の数学の結果が示唆することです.
これがどういうことかは, 「派閥」みたいなものには縁もゆかりも無いStudentSには分かりませんが, 人狼というゲームと同じような視点で, 現実世界を捉えるような視点って面白いですよね. 人狼のゲームでは, ただ夜にボタンを押して参加者をゲームから除外するだけですが, それと同じような感覚で, 自分自身の勝利を目指す為に, ある人を集団の中から社会的に抹殺するという行動を とっている人がいるかもしれない...と想像すると, 人狼ゲームの見方が少し変わりませんか?

 

おまけ, <論文の証明を読む為の最初の一歩>(自分自身が証明を追いきれていないです...)

 

一般的に, 数量的な議論を行う時に, 数学的に良い性質を持っている量を定義できると議論が行いやすいです. 今回のエントリで紹介した論文の証明では, その量(の1つ)として,
(生存狼の数) * (生存狼の数 - 1) / (生存プレイヤーの数)
という値に着目しています.

 

 

きちんと書くと, $t$日目に生存しているプレイヤーの数をN_t, そのうちの狼の数をW_tとして, X_t = W_t(W_t-1)/N_tという量を定義しています. X_tの値は, $t$日目の狼有利度を表している量だと考えることができます. X_tが大きいということは, プレイヤーの数に対して, 残っている狼の数が多いことを意味しているからです. この$X_t$は数学的に扱いやすい
martinagale性を有します. (martingale性については, Wikipediaを参照)
(村の最善進行である乱択で昼の吊り先を選ぶ戦略を採用すると,) E[X_{t+1}| X_t] = W_t/N_t * (W_{t-1})(W_{t-2})/(N_{t - 2}) +(N_t - W_t)/N_t * W_t(W_{t-1})/(N_{t - 2}) =X_t です. )
素朴な説明としては, martingale性とは, 期待値が時間の経過によって変化しないということです.  "ゲームが続いている限り", 全ての$t$に対して, E_{t}[X_t] = X_0 = f(N)* (f(N) -1) / Nです.

 

 

この"全ての日"t"で, その日の狼の数と生存プレイヤー数から決まるX_tの期待値が決まるのですが この$t$の決め方を, "条件を設定して, その条件を初めて満たした日"(これをT日目としましょう.) としても, E[X_T] = X_0 = f(N)* (f(N) -1) / Nが成り立つ. という数学の定理があります. ($T$の決め方は, 数学的な仮定を満たすことが必要. また, 期待値をとる時に, Tの値自体が確率的に決まることが違いです. T自体も確率変数なんです.)

 

詳細は, optinal stopping time Theorem

Optional stopping theorem - Wikipedia, the free encyclopedia

参照です. きちんと論文中の証明が追えていないのですが, この性質を利用して証明を進めている感じのようです. 

 

P.S.
ダイスの女神様進行の最適性は, やっぱり議論していたんだなぁ...と論文を(紹介しているwikipedia)読んだときに感じました.

 

Dec 10th, 2015

 

Twitterで自分のBlogの計算ミスを指摘してくださっている方の投稿をみつけました...そっと直しました....Thanks! です.  その方の投稿で, 

「狼が複数人いるときの, 村/狼の勝率を知りたい」という投稿がありました. wikipedia

Mafia (party game) - Wikipedia, the free encyclopedia

によると, 漸近的には, 狼の勝率は, \frac{(狼の数)}{[sqrt{全ての参加者の数}}という近似が成り立つという記述がありました .(この値が40%以下のときに良い近似となるとのことです. )
正確な確率計算は, 不肖, 私もこのブログで漸化式で導出しましたし,
wikipediaの記述によると, 論文にもなっているようです.
(論文と自分のブログの内容があっているかどうかは未検証....あぁ, 自分の弱さを許してください....)

 

自分の中で今回紹介した論文の話は, X_t = W_t(W_t-1)/N_tがmartingale性を有していて, X_0が有限の値となるためには, W_tがN_tのルート程度でなければならないことが分かった地点で, 何となく簡潔している所があります...