🔢 mathematics

Counting Votes with Multisets

本論文は、マルチセットの圏論的性質、具体的には自由可換モノイド、関手、およびモナドとしての構造が、即時決選投票、ド・ボルダ方式、および単一移譲式投票を含む様々な投票制度における結果を導出し表現するために、いかに効果的に適用され得るかを実証するものである。

原著者： Bart Jacobs, Michael Johnson, Richard Buckland

公開日 2026-06-05

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Bart Jacobs, Michael Johnson, Richard Buckland

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、紙の投票用紙を一枚ずつ数える代わりに、色とりどりのビー玉が入った巨大な袋を管理していると想像してください。これが、この論文の核心である「マルチセット（多重集合）」の考え方です。

以下は、著者であるバート・ジェイコブス、マイケル・ジョンソン、リチャード・バックランドによる提案を、日常的な例えを用いて分かりやすく解説したものです。

1. 魔法の袋（マルチセットとは何か？）

通常、数学における「集合（セット）」は、一意のアイテムのリストのようなものです。例えば「果物の集合」がある場合、「リンゴ」と「バナナ」は含まれますが、定義として「リンゴが2個」ということはありません。単に「リンゴ」という存在があるだけです。

マルチセットは、ビー玉の袋のようなものです。

もし、袋の中に赤色のビー玉が4個、青色のビー玉が3個、緑色のビー玉が2個入っていたとしたら、順番は重要ではありません。
重要なのは**個数（カウント）**です。
著者はこれを次のように記述します：4|R⟩ + 3|B⟩ + 2|G⟩。
選挙において、この「袋」は投票を表します。「誰が」あるいは「いつ」投票したかは関係なく、重要なのは「赤に対して4票、青に対して3票、緑に対して2票ある」ということだけです。

なぜこれが良いのか？
もし投票をリスト（スプレッドシートのようなもの）として保持すると、そのリストの順序によって、誰が誰に投票したかが偶然に露呈してしまう可能性があります。しかし、すべてを「マルチセットの袋」の中に投げ込んでしまえば、順序は消滅します。これにより、個人に遡ることが不可能な、クリーンで匿名の集計結果が得られるのです。

2. 3つの投票ゲーム

この論文は、この「ビー玉の袋」のアプローチが、3つの複雑な投票システムをいかに理解しやすく、計算しやすくするかを示しています。彼らは「関手（ファンクタ）」や「モナド」といった難解な数学用語を使っていますが、これらはビー玉を動かすためのルールだと考えてください。

ゲームA：即時決選投票制（「脱落」ゲーム）

仕組み: 有権者は候補者を順位付けします（1位、2位、3位……）。もし誰も50%の票を得られなかった場合、最も票の少なかった候補者が脱落します。その候補者の票は、投票者の「第2希望」へと移されます。
マルチセットのトリック: あなたの投票用紙の袋が、リストのスタック（積み重ね）であると想像してください。
1. すべてのリストの最上部（第1希望）を確認し、ビー玉の数を数えます。
2. 落選者（候補者C）を見つけます。
3. 「魔法の消しゴム」（論文では「関手」と呼ばれます）を使って、袋の中にあるすべてのリストから候補者Cを削除します。
4. すると、第2希望が新しい第1希望になります。再び袋の中を数えます。
5. 誰かが過半数を得るまで、これを繰り返します。
メリット: 何千枚もの紙から手作業で名前を消していく代わりに、「削除」というルールを袋全体に一度に適用するだけで済みます。

ゲームB：ド・ボルダ方式（「重み付きポイント」ゲーム）

仕組み: 有権者は候補者を順位付けします。第1希望には4点、第2希望には3点、第3希望には2点……といった具合にポイントが付与されます。全員のポイントが合算されます。
マルチセットのトリック:
1. 単に票を数えるのではなく、すべての投票用紙を「重み付きのミニ・バッグ」に変えます。例えば「A、B、C、D」という投票は、4|A⟩ + 3|B⟩ + 2|C⟩ + 1|D⟩となります。
2. これらすべてのミニ・バッグを、一つの巨大な「スーパー・バッグ」の中に投げ込みます。
3. 「平坦化（フラットニング）」ツール（論文では「モナド」と呼ばれます）を使って、すべての層を押しつぶしてまとめます。
4. その結果、各候補者に対する総ポイントが一つにまとまったカウントとして得られます。
メリット: 複雑な数学の問題を、単純な「すべてを足し合わせる」という操作に変換します。

ゲームC：単記移譲式投票制（「余剰分配」ゲーム）

仕組み: これは複数の当選者を選ぶ場合（市議会など）に使われます。そこには「クォータ（当選に必要な最低票数）」が存在します。もしある候補者が必要以上に多くの票を得た場合、その「余剰」票を無駄にしてはいけません。それらは投票者の次の希望へと移されるべきです。
マルチセットのトリック:
1. ある候補者が93票で当選したとします。しかし、クォータが63票だった場合、彼には30票の「余剰」があります。
2. この30票をランダムに選んで移す（これは不公平です）代わりに、著者らは数学的なトリックを提案しています：**「票の価値を下げる」**ことです。
3. その当選者に投じられた93票のすべてを取り出し、特定の割合で縮小します（写真のサイズを縮小するように）。
4. 次に、その当選者をリストから「削除」し、これらの「縮小された」票を次の候補者へと移します。
5. これにより、数学的に「端数の票」を完璧に扱うことができ、票が無駄になったり二重にカウントされたりすることを防ぎます。

3. なぜこれが重要なのか？

著者たちは新しい種類の数学を発明しようとしているのではありません。**「古い数学（圏論）こそが、現代の投票のための完璧な道具である」**ということを示しているのです。

透明性: マルチセットは投票の順序を無視するため、集計プロセスは数学的に匿名であることが保証されます。
簡潔さ: 複雑なルール（落選者を削除したり、余剰票を分割したりすること）が、ビー玉の袋に対する単純な操作になります。
正確性: もし、これらの「袋」のルールを使って投票を集計するコンピュータプログラムを書けば、紙の山を仕分けようとするよりも、間違いを犯す可能性がはるかに低くなります。

要約すると: この論文は、投票を「乱雑な紙の山」として考えるのではなく、「色とりどりのビー玉の袋」として捉え直すことで、公平かつ迅速に、そしてミスなく集計するためのシンプルで強力な数学的ルールが使えるようになる、と主張しています。

技術要約：マルチセットを用いた投票集計

問題提起
本論文は、複雑な選挙制度、特に優先順位付き投票（優先順位付け）や複数の重み付き選択肢を伴う制度における、投票集計アルゴリズムの記述、説明、および実装における課題に取り組んでいる。単純な選挙（例：候補者2名、単一投票）はリストや単純なカウントによって記述できるが、即時決選投票（IRV）、ド・ボルダ方式、単一移譲式投票（STV）などのメカニズムには、余剰票の移譲、候補者の排除、および優先順位の再重み付けが含まれる。著者らは、標準的なデータ型であるリストは、これらのタスクにおいて最適ではないと主張している。なぜなら、リストは順序を保持してしまうため（順序は結果に関係しない）、情報の漏洩（投票のシーケンスに関する情報の漏洩）を招き、機密性を損なう可能性があるからである。さらに、これらのアルゴリズムをリストを用いて実装すると、複雑でアドホックなコードになりやすく、正当性の検証や透明性の確保が困難になる。

手法
本論文は、選挙結果および投票集計プロセスを、リストではなくマルチセット（要素が複数回出現し得る集合）を用いてモデル化することを提案している。著者らは、これらのマルチセットに対する操作を定式化するために、圏論の初等的な手法を用いている。コアとなる手法は以下の通りである：

データ型の選択： 投票の集合を、候補者を要素とし、その多重度を投票数とするマルチセット $N(X)$ （または分数投票のための $M(X)$ ）として表現する。これにより、投票の順序を抽象化する。
圏論的構造： 著者らは、投票アルゴリズムを導出し表現するために、マルチセットの3つの特定の圏論的性質を利用している：
- 可換モノイド： マルチセットは自由可換モノイドを形成し、順序に関係なく投票数の加算（投票箱の結合）を可能にする。
- 関手性（Functoriality）： マルチセット構成 $N$ は関手として機能する。これにより、候補者に定義された関数（例：「リストの先頭」や「候補者の削除」）を、リストのマルチセット上の関数へと持ち上げることが可能になる。この性質は、第1希望の集計や、候補者が排除された際の投票の再分配を行うために使用される。
- モナド構造： マルチセットは、unit（単一要素のマルチセットの生成）と flatten（マルチセットのマルチセットを潰す操作）を持つモナドを形成する。この構造は、1つの投票（優先順位リスト）が複数の候補者への重み付き寄与へと分解される、重み付きカウントを扱うために使用される。

主な貢献と結果
論文では、これら圏論的構造の適用を3つの具体的な投票メカニズムを通じて示しており、抽象化を説明するために（EfProbライブラリによるPythonスクリプトを用いた）小規模な例を用いて検証を行っている：

即時決選投票 (IRV):
- メカニズム： 最も少ない第1希望票を持つ候補者が反復的に排除され、その票は次の優先順位へと移譲される。
- 適用： 著者らはマルチセットの関手性を利用している。head 関数（第1希望の選択）および delete 関数（排除された候補者の削除）を、優先順位リストのマルチセット上で動作するように持ち上げる。これにより、第1希望の集計と、その後の投票の再分配を、複雑な反復リスト処理を回避して、単純な関数合成（ $N(\text{hd})$ および $N(\text{del } c)$ ）として表現できる。
ド・ボルダ方式 (De Borda Count):
- メカニズム： 有権者は候補者をランク付けし、ランクに基づいて点数が割り当てられる（例：1位は $n$ 点、2位は $n-1$ 点など）。
- 適用： モナド構造が利用される。各優先順位リストは、unit と点数割り当てを通じて、重み付き候補者のマルチセットへとマップされる。このような重み付きマルチセットの集合は、「マルチセットのマルチセット」を形成する。flatten 操作はこの構造を単一の合計スコアのマルチセットへと崩壊させ、重み付き寄与を効率的に合算する。
単一移譲式投票 (STV):
- メカニズム： 多人数選挙区で使用される。クォータ（ドロップ・クォータ）を超える候補者が当選し、その余剰票は次の優先順位へと移譲される。
- 適用： 著者らは、「移譲値」（投票の分数）を扱うために、データ型を分数マルチセット（ $M(X)$ ）へと拡張している。彼らは、減算（当選した候補者に使用された票の価値を減らすこと）のためにモノイド構造を利用し、再分配のために関手性を利用する。プロセスは、当選した候補者のクォータ重み付き票を総マルチセットから反復的に減算すること、および当選者の削除と残りの分数重みの次の優先順位への移譲としてモデル化される。

意義と主張
本論文の主要な貢献は、深い圏論の研究にあるのではなく、既存の圏論的構造（関手、モナド、モノイド）を投票システムという領域内で認識し、活用したことにあると控えめに主張している。著者らは以下のように述べている：

抽象化： これらのアルゴリズムをマルチセットの観点から記述することで、複雑なメカニズムを数行の数学的記法で記述することが可能となり、「抽象的」なものとなる。
正当性と透明性： マルチセットのアプローチは、投票の置換に対する不変性（順序に依存しないこと）を本質的に保証しており、これは公正な集計の基本要件である。これは、集計のロジックと、物理的または逐次的な表現を分離する。
実装： この抽象化は、マルチセットをサポートする関数型プログラミング言語（Haskellなど）における、証明可能な正しい実装を容易にする。
アクセシビリティ： 本論文は、これらの圏論的手法を非専門家にも利用可能にすることを目指しており、これらが単なる理論的な構成物ではなく、選挙結果の透明性と正確性を確保するための実用的なツールであることを示している。

結論として、簡略化された仮定（例：一様なリスト長）はあるものの、マルチセットのアプローチは、物理的な投票用紙の仕分けという歴史的な依存を超え、将来的なリファレンス実装および選挙アルゴリズムの分析のための堅牢なフレームワークを提供すると述べている。