竹内郁雄先生のアイコ問題について
竹内郁雄先生の最終講義で話題に上がった「大勢でジャンケンするときに、アイコになりやすくでとても時間がかかる！なんかいい方法はないか？」という問題。
先生の講演の中では参加者n=3の時の方法が解説されていた。「3人のうちの2人がジャンケンをして、どちらかが勝ったならそれが勝者、アイコならジャンケンしなかった人が勝者」と。
厳密な「ジャンケンのルール」の定義がなされていないとか、何を最小化すべきかが明確に与えられていない、という意見が散見される。でも、そうじゃないんだよ。与えた問題に正しく答えたからといって出題者は何も楽しくない。そんなことより「面白い結論」が得られる問題設定を作ることの方が創造的で面白いんだ。妥当な問題設定でアイコの確率を0にできるなら、それはかなり面白い。
さて、ここからは僕が竹内先生の講演を聞いて勝手に解釈したアイコ問題について語る。
まず、僕は「n人の参加者の中から1人の勝者を選ぶ方法」が求められていると考えているわけだが、そこに「各参加者は平等に1/nの確率で勝者になる」という条件が必要だ。当たり前すぎるけど、もしこの条件がなければ「みんながグーチョキパーを出して、出した手に関係なく確率1でAさんが勝利」というとてもつまらない「アイコにならない方法」があるからね。
この条件は少し強化する必要があると思う。たとえば9人から勝者を選ぶ際に2人がジャンケンをして、グー*グーならAさん、グー*チョキならBさん、という方法で選ぶ場合、ジャンケンをする人がランダムに1/3の確率で手を出すなら確かにみんな1/9の確率で勝者になれる。しかし、Aさんがジャンケンのプレイヤーなら自分が勝てる可能性のあるグーを出したいよね。各参加者の手の選択によって誰かの勝率が上がったり下がったりしてはジャンケンと呼ぶには複雑なゲームになってしまうと思う。だから各参加者の手の選択と各参加者の勝率は独立、無相関である必要がある。(注1: こうやって整理するまで気づいていなかったけども、この条件は強すぎるかも知れない。というのは、参加者全員が自分の勝率を最大化しようと振舞うことによって、結果的に勝率が1/nになるというゲーム設計も可能かも知れないからだ。考えとこう。)
最後に、僕は下で述べる理由で「ジャンケン1回で勝者を決定できる方法はない」と思っている。竹内先生も「nが大きくなるほど早く終わる」と仰っていたので、1回で決定出来る方法があるとは思っておられないはず。しかし、紀先生は
@nishio #nue 公平じゃんけん問題、あいこにならない方法があると思う。竹内先生の解と違うと思うが、ヒントはご講演の中にあった。（ただし、まだ自信/検証なし）
http://twitter.com/Nikoriks/status/9959755293
と仰っておられて、どちらが正しいのか、それとも双方の考えている問題設定に違いがあって両方正しいのかはまだ未解決問題である。僕は上記注1の見落としがあったので少し自信喪失気味。
さて、それではネタバレ防止のためにフィボナッチ数列を挟んで「僕の考える正解」を解説しよう。
1
1
2
3
5
8
13
21
44
65
さて、まず「手の選択と勝率は独立である」という条件を満たしている一番シンプルなアルゴリズムはn=3の例で述べられていた「2人のジャンケンで3つの要素から1/3の確率で選ぶ方法」だ。これを部品に使おう。
n=4の時、2人ずつに分けてそれぞれジャンケンをすることで9つの要素から1/9の確率で平等に選ぶことができる。9個の内8個にそれぞれの参加者の名前を割り振れば、8/9の確率で平等に勝者を選ぶことができる。1/9はアイコとし、もう一度ジャンケンをする。
n=5の時、同様に9個のうち5個に参加者の名前を割り振ることで、アイコの確率を4/9にできる。これはすごく多く思えるかも知れないが、普通のジャンケンをした場合のアイコ確率147 / 243 ~ 0.60よりはだいぶまし。
n=6の時、ジャンケンをするペアが3つに増えるので27個からの選択になる。この場合もアイコ確率は1/9。n=7の時は6/27。n=8の時は1/81。n=9の時は0。n=10の時は3/243。一般のnの場合、dom = 3 ** (floor(n / 2)) として (dom % n) / dom。
nが増えるに従って、アイコ確率の分母が指数的に増えるのに対して、分子は常にn未満であるので、アイコ確率はどんどん下がる。n=5の場合が最もアイコ確率が高いが、それでもジャンケン回数の期待値は1.8である。n=2の時は普通のジャンケンをして、期待値が1.5になる。
よってこれは、平均2回未満のジャンケン回数で、任意のn人から平等に1人を選ぶことができる方法である。解説終了。
なお僕がアイコをなくせないと考えるのは、たとえば4人の手で作ることのできる全事象は3 ** 4なので、4の倍数ではなく、いくつかの事象をアイコとして除外しなければ1/4の確率を作れないから。しかし僕が大前提においた「出す手と勝率は独立」って条件を外すと、もしかするとなんとかする方法があるのかも知れない。それはこれを公開してから考える。
