■人狼とクリーク問題

人狼というゲームがある。カンタンにいえば、集団内の秘密組織工作員を排除するゲームである。

たいていは工作員を炙り出す役職なども存在し、それによって直接・間接にもたらされる情報がゲームを左右するのだが、まずは単純なモデルを考えてみたい。a人の集団A1, A2, ..., Aa内に、互いに顔見知りのb人の工作員B1, B2, ..., Bbが潜伏していて、a人全員がそれぞれに排除すべき人物を記名投票している。aとbの数は全員が知っている。投票数を最も集めた人物から排除されてゆく決まりがある。そして、他には何も情報がない状況である。

単純に考えれば、b人の工作員はお互いが排除されないよう、身内には投票などしない。そこでa人からなる完全グラフをまず描き、投票関係に陥ったエッジを消してゆくことによって得られるグラフGのクリーク問題は、工作員を推定するのに使えるのではないだろうか。

集団のとある人物Aは工作員なのだろうか？グラフGにおけるA1を含むエッジ数bのクリークはC(A1)通りだったとする　（あるいはC(G,b,A1)と表すすべきかもしれないが…）。C(A1), C(A2), ... , C(Aa)などと計算してゆき、さらに、その最大値を取る人物を探す。Jだったとしよう。はたしてJはどの程度工作員なのだろうか？何らかの妥当な仮定を置くと、Jが工作員である確率がC(A1)～C(Aa)やbなどから計算できるのだろうか？

身内投票の可能性を考えると、事態はより混沌となってゆく。つまり、C(A1)～C(Aa)に比べて十分にC(B1)～C(Bb)の値を小さくしながら、かつ、工作員の誰もが最多票をもらう確率を十分に抑えることが可能な、何らかの戦略が存在しうるのだろうか？

────

クリーク数を求める高速なアルゴリズムがないか探そうとしたら、すぐさまNP完全という情報にぶちあたって絶望してしまい、勢い余って変なものを書いてしまった。

────

実際の多くの人狼プレイにおいては、こうやって必死に狼を探そうとしても、勝利をもぎ取っていくのは第三勢力の狐が多いというオチがつく。

Permalink | 記事への反応(1) | 09:14

ツイートシェア