技术摘要：排名聚合中的比例代表制

问题定义

本文研究了**排名聚合（rank aggregation）**问题，其目标是将加权输入排名的剖面（profile）合并为一个单一的输出排名。在此设定中，一个剖面 $R$ 由一组候选人 $C$ 和一个将所有可能的排名 $\succ$ 映射到权重 $R(\succ) \in [0, 1]$ 的函数组成，且所有权重之和等于 1。这些权重代表了不同标准的重要性（例如，在酒店预订中，价格与评分的重要性对比）或支持特定排名的选民份额。

识别出的核心挑战在于，经典的社会福利函数（Social Welfare Functions, SWFs），如 Kemeny 规则、Borda 计数和 Condorcet 型规则，本质上是**多数派（majoritarian）的。它们倾向于选择与最高权重输入距离最近的输出排名，从而忽略了少数派的偏好。例如，如果两个相反的排名权重分别为 51% 和 49%，标准的 SWF 通常仅返回那 51% 的排名，未能体现 49% 群体的诉求。本文旨在设计能够保证比例代表制（proportional representation）**的 SWF，确保每一个输入排名都能根据其权重对输出产生相应的影响。

方法论与框架

作者通过定义输入排名 $\succ$ 对输出排名 $\triangleright$ 的**效用（utility）**为两者之间两两一致（pairwise agreement）的数量，从而将比例性形式化：
$$u(\succ, \triangleright) = |\{(x, y) \in C^2 : x \succ y \text{ 且 } x \triangleright y\}|$$
由于对于 $m$ 个候选人，总共有 $\binom{m}{2}$ 个两两比较，因此权重为 $\alpha$ 的输入排名理想情况下应获得至少 $\lfloor \alpha \binom{m}{2} \rfloor$ 的效用。

本文引入了一套受**基于批准的委员会投票（approval-based committee voting）和参与式预算（participatory budgeting）**启发的比例性公理层级：

1. 一致性正当代表性（Unanimous Justified Representation, uJR）： 一种弱化的要求，即任何权重 $\ge 1/\binom{m}{2}$ 的输入排名至少获得一个两两一致。
2. 一致性比例正当代表性（Unanimous Proportional Justified Representation, uPJR）： 核心公理，要求权重为 $\alpha$ 的输入排名获得的效用至少为 $\lfloor \alpha \binom{m}{2} \rfloor$。
3. 强比例正当代表性（Strong Proportional Justified Representation, sPJR）： 一个加强版的要求，将保证扩展到排名组（groups of rankings）。如果子剖面 $S$ 的总权重为 $\alpha$，则输出必须与 $S$ 中排名集合的并集达成至少 $\lfloor \alpha \binom{m}{2} \rfloor$ 个两两一致。

为了实现这些公理，作者借鉴了参与式预算中的**可定价性（priceability）**概念。他们将构建输出排名的过程建模为一个顺序购买过程，其中候选人（或候选人对）是通过输入排名的预算进行“购买”的。

核心贡献与结果

1. 现有方法的局限性

论文首先分析了平方 Kemeny 规则（Squared Kemeny rule）（由 Lederer 等人 [2024] 为比例排名提出的）。作者证明，对于 $m \ge 5$，平方 Kemeny 规则甚至无法满足最弱的公理 uJR。具体而言，他们构造了某些剖面，使得具有显著权重的输入排名从平方 Kemeny 输出中获得的效用为零，从而证明了开发新机制的必要性。

2. 比例顺序 Borda 规则 (PSB)

为了满足 uPJR，作者提出了比例顺序 Borda 规则（Proportional Sequential Borda rule, PSB）。

• 机制： PSB 采用顺序操作。在每一轮中，它选择基于当前预算使加权 Borda 分数最大化的候选人。随后，它根据该候选人对得分的贡献，按比例更新输入排名的预算，即为该候选人的排名位置“付费”。
• 理论保证： 作者引入了一个结构化公理——排名可定价性（rank-priceability），这借鉴了参与式预算中的可定价性。他们证明了排名可定价性意味着 uPJR。
• 结果： 定理 4.5 确立了 PSB 满足排名可定价性，并由此满足 uPJR。
• 定量保证： 除了公理化满足外，定理 4.6 证明了 PSB 保证每个子剖面 $S$ 的平均效用至少为 $\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$。这提供了相对于该组权重的线性效用下界。

3. 流调整 Borda 规则 (FB)

作者指出 PSB 无法满足 sPJR，因为其支付方案未能充分保护协同行动的排名组。为了解决这一问题，他们引入了对可定价性（pair-priceability），这是一个更精细的公理，其中支付是针对特定的候选人对而非仅仅是排名进行的。

• 机制： 流调整 Borda 规则（Flow-adjusting Borda rule, FB） 是 PSB 的一种改进。与 PSB 类似，它顺序选择 Borda 获胜者。然而，FB 不采用简单的比例支付，而是通过在一个构建的网络中求解**最大流问题（maximum flow problem）**来确定支付金额。该网络确保在遵守预算约束和两两约束的同时，最小化单位效用的成本。
• 结果： 定理 5.5 证明了 FB 满足对可定价性，进而满足 sPJR（定理 5.3）。
• 定量保证： 定理 5.6 显示 FB 提供了与 PSB 相同的线性平均效用保证（$\frac{|S|}{4}\binom{m}{2} - \frac{3}{16}$），确保了对个人和群体的强公平性。

4. 其他变体

在附录中，作者讨论了排名等份额法（Ranked Method of Equal Shares, RMES），这是一种受参与式预算中等份额法（Method of Equal Shares, MES）启发的变体。他们表明 RMES 满足排名可定价性（从而满足 uPJR），并提供了一种略有不同的功利主义剖面，即完全基于初始 Borda 分数选择前 $\lfloor m/4 \rfloor$ 个候选人。

意义与主张

本文声称提出了首个真正的比例社会福利函数用于排名聚合。其主要意义在于：

• 领域桥接： 它成功地将来自基于批准的委员会投票和参与式预算的深刻成果（特别是 PJR 和可定价性）转移到了排名聚合领域。
• 解决开放问题： 它解决了设计满足 uPJR 和 sPJR 的 SWF 的开放问题，而之前的尝试（如平方 Kemeny）未能实现这一点。
• 公理与定量的双重强度： 所提出的规则（PSB 和 FB）不仅被证明满足强公平性公理条件，还为任何选民群体提供了稳健的定量效用保证，确保少数派的偏好不会被系统性地忽视。

作者指出，虽然他们的工作侧重于将两两一致作为效用度量，但这在文献中是标准做法。他们建议未来的工作可以探索更强的公平性概念（如 EJR 或核心稳定性）以及考虑不同排名位置价值差异的更通用的效用函数。