$p$-orderings: From Slater to Kemeny-Young to Ranked Pairs

技术摘要：p-排序：从 Slater 到 Kemeny-Young 再到 Ranked Pairs

问题陈述
在偏好选举中，选票会诱导出候选人之间的两两多数优势（pairwise majority margins）。虽然许多社会福利规则依赖于这种加权的成对信息而非完整的选票谱系，但目前仍缺乏一个将不同的排序规则联系起来的统一框架。具体而言，本文探讨了三种著名的基于边际（margin-based）的规则之间的关系：Slater 排序（最小化两两分歧的数量）、Kemeny-Young 规则（最小化分歧强度的总和）以及 Ranked Pairs（按词典序优先考虑较大的边际）。核心问题在于，这些规则是否可以被视为一个源自特定胜差（margin-of-victory, m.o.v.）矩阵优化原理的单一规范族成员。

方法论
作者引入了一类被称为 p-排序（p-orderings） 的排序规则，其定义为最小化与给定排序不一致的两两多数边际的 $p$-范数。

1. 在 m.o.v. 矩阵上定义 p-范数： 对于给定的候选人排序，作者隔离了 m.o.v. 矩阵中上三角部分的负值项（表示与该排序不一致）。作者定义了排序 $\pi$ 的 $p$-范数为：
   $$\|\pi\|_p = \left( \sum_{i<j, m_{ij}<0} |m_{ij}|^p \right)^{1/p}$$
   p-排序 即为使该量最小化的候选人排列。

2. 规范性证明（定理 1）： 本文认为选择函数 $f(x) = |x|^p$ 并非任意。在三个自然假设下——尺度不变性、仅依赖于边际大小以及关于边际大小的单调性——作者证明了唯一与此构造相兼容的连续评分函数必为 $c|x|^p$ 的形式。这确立了 p-族在基于边际的构造中的规范地位。

3. 通过 Q-和进行优化： 为了便于分析，作者定义了一个“Q-和”（推论 2），它对带符号的量进行求和 $\sum \mu_{ij} |m_{ij}|^p$。最大化此和等价于最小化负项的 $p$-范数。

关键结果
本文研究了 p-排序在 $p > 0$ 谱系中的行为：

• 当 $p \to 0^+$ 时的极限（命题 1）： 最小化 $p$-范数等价于最小化两两分歧的计数。因此，p-排序收敛于 Slater 排序。
• 当 $p = 1$ 时（命题 2）： 1-范数排序在数学上等价于 Kemeny-Young 规则，即最小化绝对分歧边际之和。
• 当 $p \to \infty$ 时的极限（定理 2）： 对于任何具有不同且非零两两边际的选举，存在一个阈值 $p^*$，使得对于所有 $p \geq p^*$，p-排序与 Ranked Pairs 排序完全一致。
  • 机制： 证明依赖于“累积支配性质”（引理 3）。随着 $p$ 的增加，最大胜差项在总和中的权重会主导其他较小的项。因此，优化过程变成了词典序化的：它优先满足最大的边际，然后是次大的，这完全镜像了 Ranked Pairs 算法。
• 稳定性： p-排序集在正 $p$ 轴上有有限个常数区间（命题 9）。对于足够大的 $p$，解会稳定为唯一的 Ranked Pairs 排序（假设边际是不同的）。

p-排序的属性
本文分析了 p-排序族的公理化属性：

• Smith 一致性： 对于所有 $p > 0$，p-排序将 Smith 集内的候选人排在集外候选人之上（命题 5）。
• Condorcet 兼容性： 如果存在 Condorcet 获胜者，该获胜者被排在第一；如果存在 Condorcet 失败者，该失败者被排在最后。
• 单调性： 如果 p-排序是唯一的，则它满足单调性（命题 7）。
• 末位失败者独立性： 在反转选票选举中移除排名最后的候选人，不会改变原始选举的获胜者（命题 6）。
• 克隆不变性： 该族通常不是克隆不变的，因为 Kemeny-Young 规则（$p=1$）未能满足此标准（命题 3）。

意义
本文声称将三种不同的投票规则——Slater、Kemeny-Young 和 Ranked Pairs——统一到了一个基于两两多数边际的单参数规则族中。通过证明 Ranked Pairs 是该规范族中最终的、大 $p$ 值的成员，这项工作为社会选择中的计数法、求和法和词典序法提供了理论桥梁。作者强调，Ranked Pairs 不仅仅是一个孤立的启发式算法，而是由边际大小驱动的连续优化过程的自然极限。在假设边际不同且非零的情况下，上述结果得以证明，从而避免了平局处理的复杂性，且向 Ranked Pairs 的收敛对于所有足够大的 $p$ 均成立。