🔢 mathematics

Counting Votes with Multisets

本文论证了多重集的范畴属性——特别是其作为自由交换单子、函子和单子的结构——如何能有效地应用于推导并表达各种投票制度（包括即时决选制、德波达投票制和单一可转移票制）的结果。

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

发布于 2026-06-05

📖 1 分钟阅读🧠 深度阅读

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

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下你正在主持一场投票，但不是一个一个地清点纸质选票，而是管理着一个巨大的彩色弹珠袋。这就是这篇论文的核心思想：多重集（Multisets）。

以下是作者 Bart Jacobs、Michael Johnson 和 Richard Buckland 提出的方案的简单拆解，使用了日常类比。

1. 魔法袋（什么是多重集？）

通常在数学中，“集合（Set）”就像是一个唯一元素的列表。如果你有一个水果集合，你可以有一个苹果和一个香蕉，但你不能在集合定义中拥有“两个苹果”；它仅仅是“苹果”。

多重集（Multiset）就像是一个装满弹珠的袋子。

如果你在袋子里放入 4 个红弹珠、3 个蓝弹珠和 2 个绿弹珠，顺序并不重要。
重要的是计数。
作者将其写作：4|R⟩ + 3|B⟩ + 2|G⟩。
在选举中，这个袋子代表了选票。谁投了票或何时投的票并不重要；重要的是袋子里有 4 票给红色，3 票给蓝色，2 票给绿色。

为什么这样做很好？
如果你将选票保存在一个列表中（比如电子表格），列表的顺序可能会意外泄露谁投给了谁。但如果你只是把所有东西都倒进一个“多重集袋子”里，顺序就消失了。你得到的是一个干净、匿名且无法追溯到个人的计数。

2. 三种投票游戏

论文展示了这种“弹珠袋”方法如何让三种复杂的投票系统变得更容易理解和计算。他们使用了一些高级数学术语（如“函子/functors”和“单子/monads”），但你可以把它们看作是移动弹珠的规则。

游戏 A：即时淘汰制投票（“淘汰”游戏）

运作方式： 选民对候选人进行排序（第一志愿、第二志愿、第三志愿）。如果没有人获得 50% 的选票，得票最少的人就会被踢出局。他们的选票将被转给选民的第二选择。
多重集技巧： 想象你的选票袋是一叠列表。
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. 为什么这很重要？

作者并不是试图发明一种新的数学类型；他们是在展示旧数学（范畴论）是现代投票的完美工具。

透明度： 因为多重集忽略了投票的顺序，计票过程在数学上保证了匿名性。
简洁性： 复杂的规则（如删除落选者或拆分剩余票）变成了对弹珠袋的简单操作。
正确性： 如果你编写一个使用这些“袋子”规则来清点选票的计算机程序，它比尝试整理成堆的纸张要难出错得多。

简而言之： 论文认为，如果我们不再把选票看作一堆乱七八糟的纸，而是开始把它们看作一个装满彩色弹珠的袋子，我们就可以使用简单的、强大的数学规则来公平、快速且无误地清点它们。

技术摘要：使用多重集进行计票

问题陈述
本文探讨了描述、解释及实现复杂选举系统（特别是涉及偏好投票（排序选票）和多个加权选项的系统）中计票算法的挑战。虽然简单的选举（例如，两个候选人、单票制）可以通过列表或简单计数来描述，但诸如即时决选制（IRV）、德波达计票法（De Borda counts）和单一可转移票制（STV）等机制涉及剩余票数的转移、候选人的淘汰以及偏好权重的重新分配。作者认为，标准的数据类型（如列表）对于这些任务而言并非最优，因为它们保留了顺序（而顺序对结果而言是无关紧要的），并且可能会泄露有关投票序列的信息，从而可能损害机密性。此外，使用列表来实现这些算法往往会导致产生复杂且针对特定场景编写的代码（ad-hoc code），这类代码难以验证其正确性和透明度。

方法论
本文建议使用多重集（multisets，即元素可以出现多次的集合）而非列表来对选举结果和计票过程进行建模。作者利用范畴论中的初等技术来形式化多重集上的操作。核心方法论包括：

数据类型选择： 将选票集合表示为多重集 $N(X)$ （或用于分数票数的 $M(X)$ ），其中元素是候选人，多重度是票数。这抽象掉了顺序的影响。
范畴结构： 作者利用了多重集的三个特定范畴属性来推导并表达投票算法：
- 交换单子（Commutative Monoid）： 多重集构成一个自由交换单子，允许进行票数相加（即票箱的并集），其中顺序是无关紧要的。
- 函子性（Functoriality）： 多重集构造 $N$ 作为一个函子。这使得定义在候选人上的函数（例如“列表头部”或“删除候选人”）可以被提升（lifted）到列表的多重集上的函数。这一属性被用于聚合第一偏好，并在候选人被淘汰时重新分配选票。
- 单子结构（Monad Structure）： 多重集构成一个具有 unit（创建单元素多重集）和 flatten（合并多重集的集合）结构的单子。该结构用于处理加权计数，即将单个选票（偏好列表）分解为对多个候选人的加权贡献。

主要贡献与结果
本文通过三种具体的投票机制展示了这些范畴结构的运用，并使用小规模示例（通过 EfProb 库的 Python 脚本进行验证）来阐释这种抽象：

即时决选制 (IRV)：
- 机制： 迭代地淘汰第一偏好票数最少的候选人，并将他们的选票转移到下一个偏好。
- 应用： 作者利用了多重集的函子性。head 函数（选择第一偏好）和 delete 函数（移除被淘汰的候选人）被提升到对偏好列表的多重集进行操作。这使得聚合第一偏好以及随后的选票重新分配可以被表达为简单的函数复合（ $N(\text{hd})$ 和 $N(\text{del } c)$ ），避免了复杂的迭代列表处理。
德波达计票法 (De Borda Count)：
- 机制： 选民对候选人进行排序，并根据排名分配点数（例如，第1名得 $n$ 分，第2名得 $n-1$ 分，依此类推）。
- 应用： 利用了单子结构。每个偏好列表都被映射为一个加权候选人的多重集（通过 unit 和点数分配）。所有此类加权多重集的集合构成了多重集的集合（multiset of multisets）。flatten 操作随后将此结构压缩为单个总分的单一多重集，从而高效地汇总加权贡献。
单一可转移票制 (STV)：
- 机制： 用于多议席选区。超过配额（Droop quota）的候选人当选，其剩余选票将被转移至下一个偏好。
- 应用： 作者将数据类型扩展为分数多重集（ $M(X)$ ）以处理“转移值”（即选票的分数部分）。他们利用单子的交换性质进行减法（减去用于选举候选人的选票价值），并利用函子性进行重新分配。该过程被建模为从总多重集中迭代减去当选候选人的配额加权票，随后移除该当选候选人，并将剩余的比例权重转移给下一个偏好。

意义与主张
本文谦虚地声称，其主要贡献不在于深奥的范畴论，而在于对现有范畴结构（函子、单子、单子）在投票系统领域内的识别与利用。作者认为：

抽象化： 通过多重集来描述这些算法，使得这些算法变得“抽象”，从而可以用寥寥数行的数学符号描述复杂的机制。
正确性与透明度： 多重集方法本质上确保了在选票置换下的稳定性（即顺序无关性），这是公平计票的基本要求。它将计票逻辑与选票的物理或序列表示分离开来。
实现： 这种抽象促进了在支持多重集的函数式编程语言（如 Haskell）中创建可证明正确的实现。
易用性： 本文旨在使这些范畴技术对非专家也具有吸引力，证明它们是确保选举结果透明度和准确性的实用工具，而非纯粹的理论构想。

文章总结道，尽管文中做了一些简化假设（例如统一列表长度），但多重集方法为未来的参考实现和选举算法分析提供了一个稳健的框架，使其能够超越历史上对物理选票进行排序的依赖。