人狼とクリーク問題

人狼というゲームがある。カンタンにいえば、集団内の秘密組織工作員を排除するゲームである。 たいていは工作員を炙り出す役職なども存在し、それによって直接・間接にもたらされる情報がゲームを左右するのだが、まずは単純なモデルを考えてみたい。a人の集団A1, A2, ..., Aa内に、互いに顔見知りのb人の工作員B1, B2, ..., Bbが潜伏していて、a人全員がそれぞれに排除すべき人物を記名投票している。aとbの数は全員が知っている。投票数を最も集めた人物から排除されてゆく決まりがある。そして、他には何も情報がない状況である。 単純に考えれば、b人の工作員はお互いが排除されないよう、身内には投票などしない。そこでa人からなる完全グラフをまず描き、投票関係に陥ったエッジを消してゆくことによって得られるグラフGのクリーク問題は、工作員を推定するのに使えるのではないだろうか。 集団のとある人物A