その抽選、本当に等確率ですか？

ギルドに入ろうのシステム担当・パズル担当ことfffです。
今回のナゾガク公演では、参加権の一部を抽選で決めることになり、仕様決定や実装をfffが担当しました。
この記事はその抽選についてのお話です。

理想的な抽選とは？

まず、抽選で行われることは次の通りです。

あるイベント( X人 $${\times}$$ Yチーム)に対して複数のグループ(X人とは限らない)が参加応募するときに、その応募を適切に割り振りY個のチームを作成する

そして、抽選で期待されることは次の通りです。

1. 各応募グループの人数によらず、すべての人の当選確率ができるだけ公平になる

2. 応募人数が当選可能数よりも多いとき、当選可能数の上限まで当選してほしい

1番の要件は言うまでもありませんね。抽選は公平であるに越したことはありません。
2番の要件は、たくさん応募いただいているならば公演人数上限まで当選してほしいということです。

現実的には2番の要件の重要度が高く(空席は出したくないですね)、1番がどの程度重視されているかは不透明なところだと思いますし、そもそもちゃんと計算しないと、抽選システムを書いた本人すらどの程度確率が偏っているか気づかないと思います。

今回はその1番の要件に焦点をあてます。

その抽選、本当に等確率ですか？

過去に次のようなアルゴリズムでの抽選を聞いたことがあります。

アルゴリズム1

各公演の各チームについて、次の操作を繰り返す。
・[そのチームの空き席数]以下の人数のグループの中から1つランダムに選び、チームに割り当てる

アルゴリズムの評価

しかし、これはグループの人数が大きければ大きいほど当選確率が低くなるアルゴリズムです。
グループの人数が少なければ、空席への割り当て抽選を受ける機会が圧倒的に増えます。

仮に4人1チームの公演に以下のように応募があったとします。

4人グループ: A組
3人グループ: A組
2人グループ: A組
1人グループ: A組
(ただしAは十分に大きいとする)

この時、各グループの当選確率はおおよそ次のようになります。(複数グループが当選することがあるので当選確率の和は1になりません。)

4人グループ: 約 $${\frac{1}{4A}}$$
3人グループ: 約 $${\frac{1}{3A}}$$
2人グループ: 約 $${\frac{1}{2A}}$$
1人グループ: 約 $${\frac{1}{A}}$$

Aを十分に大きくした時という強い仮定を置いていますが、4人グループと1人グループの間に4倍近い当選率の差ができてしまいました。

イベントの抽選でまことしやかに言われる「1人グループの方が当たりやすい」という噂は、ひょっとするとここからきているのかもしれません。

一応、このアルゴリズムの長所として、非常に単純であるためバグを起こしにくく、チーム数の増減にも容易に対応できることがあげられると思います。

先に何人組に分けるか抽選してみよう

この現象は、人数が小さいグループのほうが空席の隙間に入りやすいことを考慮していないアルゴリズムを実行したことが原因でした。
そこで、先に何人組にチームを分けるかを抽選してしまえば公平性が保てます。
以下は実際に今回のギルドに入ろうの抽選で使用したアルゴリズムの概略です。

アルゴリズム2

4人1チームの公演に、以下の応募が来ているとする。

4人グループ: A組
3人グループ: B組
2人グループ: C組
1人グループ: D組
(ただし、B < D、C≧2、D≧4とする)

このとき、以下の手順で抽選する。
$${X_1 = A, X_2 = B, X_3 = \frac{C}{2}, X_4 = \frac{(D-B)}{4}}$$とする。
$${S=X_1 + X_2 + X_3 + X_4}$$とする。
$${\frac{X_1}{S}}$$の確率で4人グループ1つを、
$${\frac{X_2}{S}}$$の確率で3人グループ1つと1人グループ1つを、
$${\frac{X_3}{S}}$$の確率で2人グループ2つを、
$${\frac{X_4}{S}}$$の確率で1人グループ4つを各々ランダムに抽選する。

アルゴリズムの評価

このアルゴリズムは使える状況に制約がかかりますが、どのグループも等確率で当選します。
この制約も、C≧2、D≧4は応募数が増えれば容易に達成しますし、3人グループの応募が1人グループの応募数を上回るのはかなり稀有な状況だと思われます。

ここでは4人チームの時の具体的な確率のみ提示しましたが、先にグループの人数だけ決めてしまう方法自体はチーム人数が増えたとしても取ることができる手段です。

一方で、チーム人数が変わるたびに多少のカスタマイズが必要ですし、バグを埋め込む確率も多少上がります。システムに人員を割けない環境では多少躊躇する選択肢ではあると思います。

終わりに

ギルドに入ろうの公演の抽選は今後も公平性を重視して実装しますので、参加ご希望の方は当選確率を気にせず、参加したい方と一緒に抽選に応募いただければ幸いです。

また、チーム制イベントの抽選を実装している担当者の方がいらっしゃいましたら、ご参考にしていただければ幸いです。