🏠 总目录📚 本教程 26 · 不可能定理 ← →

想要的投票性质不能兼得,究竟受哪些前提限制?

读后可检查:先核对公理和输出类型,再分别阅读 Arrow 与策略操纵结论的条件。

📑 本页目录(点开跳转)

26 · 不可能定理

⏱ 50 分钟 | 原预计,仅供参考;可以分次读 | ⭐ 不是“投票没用”,是先说清要保住哪些性质


🎯 一句话

不可能定理说的是“一组要求不能全部满足”,不是“群体无法作决定”。 使用定理之前,先核对输入允许什么、输出是什么。

想得到什么 本章名称 先去哪里
全部候选项的集体排序 社会福利函数 SWF Arrow 定理
确定的一个赢家 社会选择函数 SCF Gibbard–Satterthwaite 定理
各候选项被选中的概率 社会决策方案 SDS 随机化

第一次读,先看Borda 的手算,再看取舍地图。详细前提不必一次记住,但使用结论时要回来核对。


📏 一、公理:把“好规则”拆成可检验的条款

前两章用同一份 14 人选票比较规则:第 24 章六条规则得到五个不同赢家;第 25 章的 Condorcet 赢家是已经出现过的 $c$,没有新增第六个候选项。

结果不同,不足以单独判断哪条规则更好。公理化方法进一步问:这条规则保证哪些性质?有没有反例?

本章默认候选项与选民都是有限的,每位选民提交对全部候选项的严格完整排序,不允许个人并列。各定理的额外要求会单独写出。

先看三个容易混用的性质

性质 对排序怎么说 对确定赢家怎么说
帕累托 若人人都把 $x$ 排在 $y$ 前,集体也必须把 $x$ 排在 $y$ 前 若人人都更喜欢 $x$ 而非 $y$,就不能选 $y$
非独裁 不存在一名固定选民,集体排序始终照抄他的排序 不存在一名固定选民,结果始终选他的第一名
IIA 每人对 $a,b$ 的相对排序不变,集体对这两项的相对排序也不变 Arrow 的这个定义不能原封不动当作单赢家规则的性质

“这次结果刚好与某人一致”不叫独裁。独裁要求存在同一个人,在所有允许的选票组合下都决定结果。

再看其他五条

  • 匿名性 Anonymity:互换选民身份,结果不变;随机规则的概率也不变。
  • 中立性 Neutrality:给候选项统一改名,输出相应改名,不偏爱某个名字。
  • 候选项单调性 Monotonicity:当选者被上调、其他候选项相对次序不变时,它仍应当选。
  • Condorcet 一致:有能两两击败所有对手的候选项时,必须选它。
  • 策略防伪 Strategyproofness:固定其他人的报告,任何一位选民都不能靠单独谎报得到自己更喜欢的结果。

这里的单调性是普通“上调赢家”条件,不要与机制设计里其他同名、但更强的单调性概念混用。

违反 Condorcet 一致,不等于选出了输给所有人的候选项。 只要没有选出当时存在的全胜者,就违反了这条要求。

拿 14 人选票检查匿名性:只互换选民编号,不动票面,结果应不变。检查中立性:所有票统一交换 $a,b$ 的名字,输出也应交换。

这些性质不是免费的。 比如计分相同时,总优先选名字为 $a$ 的候选项,会破坏中立性。评价规则时,计票与平票处理要一起检查。


🔬 二、IIA:只动第三项,为什么会改变前两项的排序?

这次候选集合始终是 $\{a,b,c\}$,没有增加或删除候选项。

IIA 比较的是两份完整选票组合:每个人对 $a,b$ 的相对顺序都不变,集体对 $a,b$ 的判断能不能变?

使用 Borda 分数 $(2,1,0)$:第一名 2 分、第二名 1 分、第三名 0 分。按总分产生集体排序。

第一次:3 人报 $a\succ b\succ c$;2 人报 $b\succ c\succ a$。

票组 $a$ $b$ $c$
3 人组 $3\times2=6$ $3\times1=3$ 0
2 人组 0 $2\times2=4$ $2\times1=2$
总分 6 7 2

集体排序是 $b\succ a\succ c$。先记住:$b$ 排在 $a$ 前。

第二次:3 人组改成 $a\succ c\succ b$;2 人组不变。

票组 $a$ $b$ $c$
3 人组 $3\times2=6$ 0 $3\times1=3$
2 人组 0 $2\times2=4$ $2\times1=2$
总分 6 4 5

集体排序变成 $a\succ c\succ b$,现在 $a$ 排在 $b$ 前。两次总分都是 15,等于 5 人各分出 3 分。

核对对象 第一次 第二次
3 人组对 $a,b$ $a\succ b$ $a\succ b$
2 人组对 $a,b$ $b\succ a$ $b\succ a$
集体对 $a,b$ $b\succ a$ $a\succ b$

个人的两项比较没变,集体的两项比较变了。这就是 IIA 反例。

它提示“第三项的位置可能影响结果”,但不要把 Arrow 的 IIA 直接等同于“增加、退出候选项时的搅局现象”:后者改变了候选集合,需要另行定义和检验。

所有位置计分规则都这样吗?看一个明确范围的证明

先限定范围:两名选民、三个候选项,使用非恒定的名次分数 $\alpha\ge\beta\ge\gamma$,按总分排序并保留同分关系。

让两人分别报 $a\succ b\succ c$ 与 $b\succ a\succ c$。此时 $a,b$ 总分都是 $\alpha+\beta$,集体认为两者并列。

  • 若 $\beta>\gamma$:第一人改报 $a\succ c\succ b$。$a$ 得分不变,$b$ 从 $\alpha+\beta$ 降到 $\alpha+\gamma$,于是 $a$ 排在 $b$ 前。
  • 若 $\beta=\gamma$:非恒定条件意味着 $\alpha>\beta$。第一人改报 $c\succ a\succ b$;此时 $b$ 比 $a$ 多 $\alpha-\beta$ 分。

两种情况都没有改变任何人对 $a,b$ 的顺序,却改变了集体关系。因此,这一类规则不能普遍保证 IIA。

这比“名次会变,所以一定违反”更完整。分数全相同的退化规则需要排除;一名选民照抄自己的严格排序也不是反例。若另加固定平票优先序,还要把它纳入具体规则,不能直接复用“并列变严格”的证据。


⭐ 三、Arrow 不可能定理

Borda 反例只否定 Borda。Arrow 定理则覆盖满足下列设定的所有排序规则。

  • 数量:至少 3 个候选项、至少 2 名选民,数量有限。
  • 输入:允许所有严格完整个人排序的组合,即不限制偏好域。
  • 输出:完整且传递的集体排序;集体可以有并列。
  • 性质:排序版帕累托、IIA、非独裁。

结论:以上要求不能同时成立。 在这个输入域与输出要求下,满足帕累托和 IIA 的规则必然是独裁规则。

“完整”是任意两项都能比较;“传递”是比较不能自相矛盾,例如严格认为 $a$ 好于 $b$、$b$ 好于 $c$,就不能又把 $c$ 放在 $a$ 前。

采用的严格输入、允许并列输出版本,见《计算社会选择手册》定理 1.1。

为什么这个结论重要,但不能说“前提都很弱”?

  • 帕累托只在全体一致的两项比较上提出要求。
  • 非独裁排除固定一个人始终决定结果,但不等于匿名或权重完全相同。
  • IIA很强:它禁止使用其他候选项的位置信息来决定这两项的集体关系。
  • 不限制偏好域也很强:不能只处理意见排列整齐、容易达成一致的情况。

因此,不该说成“连任何人都会接受的最低标准也做不到”。这些要求是否适合当前任务,本身就值得讨论。

这不是“现有算法还不聪明”

只要完整保留定理前提,换实现、加算力或发明新算法,都不能让这组要求全部成立。

如果改变前提,定理可能不再适用。“不适用”不等于新方法已经成功,还要检查它实际保住了哪些性质。

可以联系第 11 章:没有免费的午餐:都要先读结论背后的量词与假设。NFL 的算法比较依赖特定的任务平均方式,不能简写成“所有现实问题上算法都一样好”。

与 Condorcet 循环是什么关系?

三名选民的两两多数关系可以出现 $a\succ b$、$b\succ c$、$c\succ a$。多数比较保留了两项信息,却在这份选票上失去传递性。

循环是一个具体反例,不是 Arrow 定理的完整证明。 它没有证明所有可能规则都失败;也不是说每份选票一定成环。

Arrow 的结论是:在全输入域上,不能同时保住完整传递的输出、帕累托、IIA 和非独裁。某份选票能顺利排好序,并不反驳这个全局结论。


⭐ 四、Gibbard–Satterthwaite:单独说谎能不能获利?

现在换对象:不要求社会排出完整顺序,只输出确定的一个赢家。 平票时也必须有规定,把它处理成唯一结果。

  • 数量:至少 3 个候选项、至少 2 名选民,数量有限。
  • 输入:允许所有严格完整个人排序的组合。
  • 输出:一个确定赢家,而不是集合或概率。
  • 满射 onto:每个候选项都能在某份允许的选票组合下获胜。
  • 策略防伪:固定别人报告,任何一人都不能靠谎报改善自己的结果。

结论:满足这些条件的规则必然独裁。 等价地,非独裁且满射的规则,必有一份选票与一位选民构成有利的单人操纵。

这是普通的偏好投票模型;若同时设计支付、换掉允许的输入或输出类型,需重新检查是否仍在本定理范围内。Cornell 教材第 12 章给出了这一版本及单峰域对照。

手算:14 人选票中的单人改票与联合改票

回到第 24 章的原选票。Plurality 只数第一名票;如实投票时 $a$ 有 5 票,唯一当选。

第 4 组两人的真实偏好都是 $b\succ d\succ e\succ c\succ a$。他们更喜欢 $e$,而不是当前赢家 $a$。

先把平票规则写清楚:本例新增一个固定优先序 $e,a,d,b,c$,同票者中选排在这个序列最前的一位。它只用于下面的单人反例;不是从原例中暗自推定的。

谁改报 $e$ 为第一名 $a$ $b$ $c$ $d$ $e$ 结果
无人:都如实报 5 2 0 3 4 $a$ 唯一胜出
第 4 组仅一人 5 1 0 3 5 按已声明优先序选 $e$
第 4 组两人一起 5 0 0 3 6 $e$ 唯一胜出

可以把谎报完整写成 $e\succ b\succ d\succ c\succ a$,仍是一张合法排序票。

  • 单人行:其他 13 人不变,这个人把结果从真实排序第 5 的 $a$ 换成第 3 的 $e$。它直接证明此确定规则不策略防伪。
  • 双人行:保留原来的联合操纵例子,两人都获益,且不依赖平票规则。它本身是联合操纵证据,不能直接代替单人证据。

固定优先序会偏袒某些候选名字,所以还要承认其非中立性。为了讲操纵而补的条件,不能在讲公平性质时藏起来。

Borda 的“压低对手”:到底扣多少分?

Borda 使用 $m-1,m-2,\ldots,0$ 分。若你把一个对手从自己票上的第 $r$ 名移到最后,它在这张票上少得 $m-r$ 分。

例如 5 个候选项,从第 2 名移到第 5 名,少 3 分,不是总少 $m-1=4$ 分。只有原来第 1 名移到最后才少 4 分。

这类做法叫 burying(压低对手)。其余候选项也会因为位置移动而改分;是否让你得到更喜欢的赢家,需要重算整张票与全局结果,不是“压低就必然获利”。

怎么读“存在操纵”,以及现实中的屏障?

定理的量词是:至少存在某个情形,有人能获利。不是每次选举都有人能成功说谎,也不是所有选民都能获利。

现实屏障 能做什么 不能保证什么
计算复杂度 某些规则与操纵设定下,寻找有利报告是 NP-难问题 最坏情况难,不代表常见小实例都难
信息不足 不知道其他票,会增加判断难度 部分信息、民调或结构有时已足够
操纵风险 错估形势可能让结果更差 风险不等于没有获利机会

这些屏障可能提高操纵成本,不自动等于策略防伪。另一条路是改变定理前提,例如下面的单峰域或随机输出。


Arrow 检查集体排序;G–S 检查确定赢家的单人操纵。

用取舍地图比较它们各自的条件。


🗺️ 五、取舍地图:先分输出,再比性质

定理没有宣布“投票没用”,也没有替你决定该牺牲什么。 它要求你把“不能接受哪种失败”说清楚。

规则与输出 提供什么 需要接受或检查的限制
Plurality:确定赢家 首位票计数简单 不保证 Condorcet 一致与策略防伪;还需处理平票
Borda:确定赢家 综合整张票的名次 不保证 Condorcet 一致或策略防伪;前章有具体反例
IRV:确定赢家 淘汰后转移偏好票 可能违反候选项单调性;不是通用的防票源分裂保证
Copeland / Kemeny:选择赢家 合适定义下保证存在的 Condorcet 赢家当选 仍需处理无全胜者和平局;不因此获得策略防伪
固定选民决定:确定赢家 选此人的第一名,可策略防伪 不满足非独裁;其他人不能改变结果

IIA 要另看“排序输出”。 Plurality 按票数排序、Borda 按总分排序时,可能违反 Arrow 的 IIA;不能把它直接贴在只输出一人的对象上而不解释定义。

Kemeny 的精确优化一般是 NP-难的,不是不可计算。候选项少时可以枚举或用求解器;用近似算法时,要重新检查是否仍保留希望的性质。

若采用“完整照抄固定选民排序”的 SWF,它满足传递性、排序版帕累托与 IIA;若只选此人第一名,才是相应的 SCF。两种独裁版本不要混在一栏当一个对象。

用这张地图做一次选择
  1. 先写输出:一个赢家、完整排序,还是抽签概率?
  2. 再写最不能接受的失败:忽略全胜者、支持反而落选,还是有人可以单独说谎获利?
  3. 写平票与允许票型,检查它们是否改变性质。
  4. 最后看规则在真实数据、规模与操作流程中的表现。

“容易解释”“照顾整体名次”“能转移后续偏好”可以是选择理由;但不能由此声称某条规则在所有场景最好。


🚪 六、两条绕开原前提的路

改变前提后,原定理不再直接适用。这给新规则留下空间,但是否成功,仍要用新的条件和结论证明。

① 域限制:所有人沿同一条轴单峰

单峰偏好要求有一条共同、固定的候选项轴。每人有一个最喜欢的位置;在峰的同一侧,越向外走,偏好越低。

它不是“按几何距离排序”。峰左右两侧之间怎样比较,还可以因人而异。

候选项轴为 $A<B<C<D<E$:

选民 完整偏好 峰 核对同侧顺序
1 $A\succ B\succ C\succ D\succ E$ $A$ 右侧逐步下降
2 $B\succ C\succ D\succ E\succ A$ $B$ 右侧 $C,D,E$ 递减;左侧只有 $A$
3 $C\succ B\succ D\succ A\succ E$ $C$ 左侧 $B,A$ 递减;右侧 $D,E$ 递减

看选民 2:即使轴上 $A$ 离峰 $B$ 较近,也允许把 $A$ 排在 $E$ 后。这不破坏“每一侧各自递减”。

看三个峰 A、B、C 在共同轴上的位置。取中间那个峰 B,不是把候选名字或名次数值求平均。

ABCDE选民 1 的峰选民 2 的峰选民 3 的峰中位峰是 B;不需要比较两侧距离
共同轴上的三个峰,中位是 B。

三个峰为 $A,B,C$,中位峰是 $B$。直接数两两选票:

比较 支持 $B$ 的人数 支持对手的人数
$B$ 对 $A$ 2 1
$B$ 对 $C$ 2 1
$B$ 对 $D$ 3 0
$B$ 对 $E$ 3 0

在共同轴、严格单峰偏好和奇数名选民下,中位峰是 Condorcet 赢家,中位规则也策略防伪。

这里把轴当作已知且固定,只允许在该单峰域内报告。谎报峰不能把结果推到自己更喜欢的位置;详细论证见Cornell 教材的中位规则。

什么时候可以用?什么时候不能直接用?

温度、预算规模或罚款额度可以排成轴,但能排成轴不代表每人的偏好就单峰。有人同时喜欢两个极端、讨厌中间,也可能破坏条件。

给定严格排序,识别是否存在共同单峰轴有多项式时间算法;这只是识别问题,不是在证明实际偏好一定符合假设。见 Bartholdi 与 Trick(1986)的原论文第 4 节。

多维议题通常更难合理解释成共同单峰轴,但也不能断言“有两个议题就一定不存在兼容轴”。

如果轴本身也由选民策略性报告或投票产生,不能直接沿用固定轴版本的策略防伪结论。

② 随机化:把输出改成概率

SDS 为每个候选项给出概率,总和为 1。记作 $\Delta(A)$ 的就是这些概率分布的集合。它不是确定的单赢家 SCF。

均匀随机独裁:先等概率抽一名选民,再选择他的第一名。 “独裁”在这里描述抽中者决定本次结果,并不是固定某个人永远决定。

三人的真实偏好分别是 $a\succ b\succ c$、$b\succ a\succ c$、$b\succ c\succ a$。

候选项 首位票数 随机独裁概率 Borda 总分 Borda 比例概率
$a$ 1 $1/3$ 3 $3/9$
$b$ 2 $2/3$ 5 $5/9$
$c$ 0 0 1 $1/9$

先看随机独裁那一列:各人被抽中的概率相等,所以候选项的概率就是首位票占比。

这个例子里 $b$ 是 Condorcet 赢家,却仍有 $1/3$ 概率选 $a$。所以代价不只是“有随机性”:它不保证只选 Condorcet 赢家。

“唯一”和“策略防伪”在随机情况下具体指什么?

仍取有限的至少 3 个候选项、至少 2 名选民,允许所有严格完整偏好组合。这里采用两个明确要求:

  • 强 SD 策略防伪:固定别人报告,按该选民的真实排序看前 1 名、前 2 名等每个前缀,如实报告所得的累计概率都不低于谎报。
  • 事后帕累托效率(ex post):任何被全体一致认为比某个其他选项差的候选项,都不获得正概率。

强 SD 要求等价于:对所有与真实顺序一致的 vNM 效用,谎报都不能增加期望效用。它不是只检查一种指定的打分,也不是更弱的“没有随机占优改善”。

在这些条件下,同时满足强 SD 策略防伪与事后帕累托效率的规则是固定权重的随机独裁;再要求匿名性,权重必须相等,得到唯一的均匀随机独裁。

这里的帕累托要求排除被支配的候选项,不是在声称最大化总期望效用。若改成允许个人并列、弱策略防伪或其他效率定义,不能直接照搬唯一性结论。参见Aziz 的 IJCAI 论文,前两节。

再看 Borda 比例那一列:这不是选 Borda 分最高的人,而是按分数占比分配中签概率。三人共分出 9 分,所以概率分母都是 9。

上例中,每个人都认为 $b$ 比 $c$ 好。Borda 比例却给 $c$ 分了 $1/9$ 概率,明确违反事后帕累托效率,不需要再加一个“假如”。

Borda 比例为什么可以策略防伪,而 Borda 选赢家不行?

固定选民数 $n$、候选数 $m$,每票给 $m-1,m-2,\ldots,0$ 分,所有票总分恒为 $nm(m-1)/2$。

按某人的真实排序看“最喜欢的前 $k$ 项”。如实报告时,这些项从他自己这张票得到最大的 $k$ 个分数之和;改报不可能让这部分得分更多。

其他人的贡献不变,总分母也不变,因此谎报不能增加任何真实前缀的累计概率。这就满足上述强 SD 策略防伪。

但“只选总分最高者”是另一种运算,赢家可能因排序微调而突变。不要把分数比例抽签、确定的 Borda 赢家,以及在同分者里均匀抽签当成同一个规则。

路线 改了哪个前提 拿到什么 仍需接受什么
共同单峰域 不再接受所有严格偏好组合 奇数选民时的中位峰赢家与策略防伪 要验证共同轴与单峰;固定轴假设不可省
随机输出 不再输出确定的一人 均匀随机独裁的匿名、强 SD 策略防伪、事后效率 结果不确定,也不保证只选全胜者

🎬 七、回望:个体与集体,分别需要哪些条件?

这一章是本板块最后一章理论正文。回顾时保留每个结论的条件,不把一串不同定理压成“集体理性不存在”。

走到哪里 带条件的结论
07 偏好与效用 有限候选集上,完整传递偏好可用效用数表示;无限情形需另查条件
08 期望效用 彩票偏好满足完整性、传递性、连续性和独立性等条件,才有 vNM 期望效用表示
11 纳什均衡 有限博弈存在混合策略均衡;不是保证纯策略均衡,也不限两个人
22 联盟博弈 核心可能为空,即不存在满足该模型全部联盟约束的分配
26 本章 集体排序可以建立,但在 Arrow 的全域设定下,不能兼得帕累托、IIA 与非独裁

个人偏好的传递性,不会自动传给两两多数关系。 但“不能自动继承”与“集体永远无法理性选择”是两回事。

其他机制也有各自的取舍,不是由 Arrow 统一推出来的:

  • 17 稳定匹配:严格偏好下,延迟接受算法对提案方在稳定匹配中最优;不保证存在双方同时最优的稳定匹配。
  • 19 怎么算公平:不可分物品下,完全无嫉妒可能不存在,因此考虑 EF1 等放宽标准。
  • 推荐算法 15b:GSP 一般不保证多广告位下如实出价为占优策略;它的机制与适用性应另行分析。

🔗 这一章连到哪里

去哪里 带着什么问题
24 · 投票规则 · 25 · Condorcet 与锦标赛解 对照原选票,区分规则结果与性质;不要重复算成“六个不同赢家”
16 · 机制设计在解什么 固定别人的报告,究竟有没有单人有利谎报?先核对输入与输出
数学原理 11 · 没有免费的午餐 不可能性结果依赖哪些假设与量词?不要直接推广到所有现实任务
推荐算法 15b · 广告:从推荐到竞价 支付、竞价和多广告位怎样改变机制问题,而不是机械套投票定理
27 · 实战与挑战项目 把选票、平票规则和性质检查写完整,亲手找反例

✅ 检查点

  1. 公理化方法为什么不能只比较“哪条规则选了谁”?
  2. Borda 的五人例子中,每个人没有改变什么,集体却改变了什么?
  3. “所有位置计分都违反 IIA”为什么需要限定范围,而不只是说名次会变?
  4. Arrow 管什么输入与输出?IIA 为什么是强要求?
  5. “再发明一个聪明算法就行”漏掉了定理的哪个量词?
  6. Condorcet 循环与 Arrow 定理,哪个是具体反例,哪个覆盖整类规则?
  7. G–S 的满射、确定输出与单人策略防伪,分别是什么意思?
  8. 14 人例子的单人、双人操纵有什么区别?哪一行依赖已声明的平票规则?
  9. 为什么 NP-难、信息不足和操纵风险不等于策略防伪?
  10. 单峰域与随机化分别改变哪个前提?各自有哪些边界?
  11. 均匀随机独裁的唯一性需要哪些精确条件?Borda 比例违反哪一条?
展开核对答案
  1. 不同赢家本身不能确定好坏;需要明确并检验性质。
  2. 每人对 $a,b$ 的顺序不变;集体从 $b\succ a$ 变成 $a\succ b$。
  3. 两人三候选、非恒定分数、同分保留并列的证明已给出。退化分数、选民规模和平票规则不能偷偷省略。
  4. 全部严格个人排序组合,输出完整传递集体排序。IIA 排除了使用第三项信息影响两项关系。
  5. 定理覆盖所有满足前提的函数,不只覆盖目前已经发明的算法。
  6. 多数循环是具体反例;Arrow 否定整组要求在全域上的共存。
  7. 每个候选项都可能赢;每次选唯一一人;固定别人报告时无人能单独说谎获利。
  8. 单人时 $a,e$ 各 5 票,靠明确优先序选 $e$;双人时 $e$ 得 6 票唯一当选,是联合操纵。
  9. 它们可能提高难度,不能排除所有有利报告。
  10. 单峰限制允许偏好,且轴固定、选民数为奇数时使用本章中位结论;随机化换成概率,不能照搬确定赢家性质。
  11. 有限至少三候选、全严格域、匿名、强 SD 策略防伪、事后帕累托效率。Borda 比例虽满足强 SD 策略防伪,却可能给被支配项正概率。

本节回顾

先记住这三件事

  • 先分清输出:集体排序、确定赢家,还是概率。
  • 不可能的是特定要求的组合,不是集体决策本身。
  • 改前提可以换取性质,但平票、输入域与概率比较标准都要写清楚。

下一节 👉 27-实战与挑战项目.md

打卡记录保存在你的浏览器里,首页能看到总进度