一、三个人选餐厅
你、同事小周和小林三个人,要一起选一家餐厅。有三个候选:A、B、C。你们每个人心里有一个排序:
- 你:A > B > C(最想去 A,其次 B,最不想去 C),
- 小周:B > C > A,
- 小林:C > A > B。
你们决定用最朴素的办法:少数服从多数,两两比。
- A 和 B 比:你选 A,小周选 B,小林选 A(C > A > B 里,A 在 B 前面)。A 胜,2 比 1。
- B 和 C 比:你选 B,小周选 B,小林选 C。B 胜,2 比 1。
- C 和 A 比:你选 A,小周选 C,小林选 C。C 胜,2 比 1。
先别往下读。请你想一想:到底选哪一家?
A 胜 B,B 胜 C,C 胜 A……这是一个圈。没有任何一家,在两两比较里赢过所有别的。
这个现象,叫孔多塞悖论(Condorcet paradox,以 18 世纪的法国学者命名)。它说明:每个人的偏好都是"有条理"的(可以排成一个序),一群人的"多数意见"却可能没有条理。
这有多常见?我先用最极端的假设算:每个选民的排序,在 6 种可能的排序里随机抽。三个选民时,一共 6 × 6 × 6 = 216 种选票,有 12 种会形成圈,概率约 5.6%;选民很多时(我用随机模拟,1001 个选民,每次随机抽),概率约 8.8%,Tsetlin、Regenwetter 和 Grofman 2003 年的文章也给出约 0.088。(据摘要和二手转述。)不过,这是最极端的"完全随机"假设;据 Regenwetter 等人用真实选举调查数据做的研究,现实里的圈要少得多(有后来的综述认为这个问题还没有定论)。
二、同一批选票,不同的结果
即使没有圈,不同的计票办法,也可能选出不同的人。
100 位选民,三个候选人,选民的排序是:
- 41 人:A > B > C,
- 34 人:B > C > A,
- 25 人:C > B > A。
办法一:只数第一名的票(相对多数制)。A 得 41 票,B 得 34,C 得 25。A 胜。
可是看看两两比较:
- B 和 A 比:34 + 25 = 59 人觉得 B 比 A 好。B 胜。
- B 和 C 比:41 + 34 = 75 人觉得 B 比 C 好。B 胜。
B 在每一次两两比较里都赢。(这样的候选人,叫孔多塞赢家。)可是只数第一名的票,选出来的却是 A,一个有 59% 的人更不想要的人。
办法二:波达计分。第一名得 2 分,第二名得 1 分,第三名得 0 分,把分数加起来:
- A:41 × 2 = 82,
- B:41 × 1 + 34 × 2 + 25 × 1 = 134,
- C:34 × 1 + 25 × 2 = 84。
B 胜。
办法三:两轮决选。 第一轮,淘汰得票最少的 C;第二轮,A 对 B:59 比 41,B 胜。
所以,只数第一名的票,选出了 A;两两比较、波达计分、两轮决选,都选出了 B。(我用程序把三种办法逐个算过。)
三、一个落选的候选人,也会改变结果
再看一个让人不安的现象。
100 位选民,两个候选人 A 和 B。其中 55 人觉得 A 比 B 好,45 人觉得 B 比 A 好。两个人的比赛:A 以 55 比 45 胜。
现在,加进来第三个候选人 C,C 其实没什么人支持。选民的完整排序是(55 个觉得 A 好的人,分成两组):
- 35 人:A > B > C,
- 20 人:C > A > B,
- 45 人:B > A > C。
用"只数第一名"的办法:A 得 35 票,B 得 45 票,C 得 20 票。B 胜!
没有任何一个选民改变了对 A 和 B 的看法。 A 还是以 55 比 45 赢 B。可是只因为加进来一个根本赢不了的 C,结果就从 A 变成了 B。C “分走"了本来会投 A 的 20 票。这样的 C,叫搅局者(spoiler)。
⚠️ 这里第一次读会觉得别扭。 你会想:C 反正输了,C 的存在,为什么会改变 A 和 B 的结果?
关键在于:只数第一名的办法,只用了每个选民"最想要谁"这一个信息,把第二名、第三名都丢掉了。C 的 20 位支持者,宁愿让 A 胜 B(他们心里 A > B),可是这个办法看不到这一点。
波达计分也有类似的问题,只是方式不同。看一个很小的例子:
两个选民。你:A > C > B;小周:B > A > C。波达分:A = 2 + 1 = 3,B = 0 + 2 = 2,C = 1 + 0 = 1。A 胜 B。
现在改变 C 的位置,不改变任何人对 A 和 B 的看法:你:A > B > C;小周:B > C > A。你仍然是 A > B,小周仍然是 B > A。可是波达分:A = 2 + 0 = 2,B = 1 + 2 = 3,C = 0 + 1 = 1。B 胜 A!
没有任何人改变对 A 和 B 的看法,只因为 C 在每个人心里的位置变了,A 和 B 的结果就翻转了。(我用程序对两个选民的所有排序做了搜索,找到了这个例子。)
四、Arrow 不可能定理
怎么办?也许我们应该问:一个"合理的"投票规则,到底应该满足什么? 把个人的排序,合成一个社会的排序。
1951 年,Kenneth Arrow 提出了四条看上去非常合理的要求。
- 不限定偏好:规则要能处理任何可能的个人排序,不能说"只允许某些排序”。
- 一致性(帕累托):如果每个人都觉得 X 比 Y 好,社会排序里也必须是 X 比 Y 好。
- 无关选项的独立性:社会怎么排 X 和 Y,只取决于每个人怎么排 X 和 Y,和 Z 的位置无关。(正是上一节两个例子里被违反的那一条。)
- 没有独裁者:不存在这样一个人,无论别人怎么想,社会排序总是听 TA 的。
另外还默认,社会排序本身是个"有条理"的排序:任意两个候选人都能比较,而且不转圈(孔多塞悖论就是违反了这一点)。
Arrow 定理:如果有三个或更多的候选人,没有任何规则能同时满足这四条。
换一种说法:任何一个满足前三条的规则,必然是"独裁"的,社会的排序,永远等于某一个人的排序。
我们逐个看看熟悉的办法,都违反了哪一条:
- 少数服从多数,两两比较:违反"有条理",会转圈。
- 只数第一名的票:违反"无关选项的独立性"(搅局者的例子)。
- 波达计分:违反"无关选项的独立性"(两个选民的例子)。
- 听某一个人的:满足前三条,但违反"没有独裁者"。
⚠️ 这里第一次读会觉得别扭。 你会想:四条要求看上去都很温和,为什么不可能?
定理的证明很短,但不好读。大意是:先证明,如果所有人一致认为 X 比 Y 好,则社会排序也如此(一致性)。然后,可以找出一个"能决定某一对的"人群,用"无关选项的独立性",把这个人群越缩越小,最后缩到一个人,而这个人,对每一对候选人都有决定权。这个人,就是独裁者。(这只是思路,我没有展开证明。)
怎么办?Arrow 定理不是说投票没法用,而是说你必须放弃某一条。常见的做法是:
- 限制偏好:如果所有人的偏好,在某种意义上"排在同一条线上"(比如大家都按"左—右"一条线上的位置,来挑自己最喜欢的),多数决就不会转圈。
- 放弃无关选项的独立性:用波达计分,或者"两轮决选"一类办法,接受搅局者会改变结果。
- 不只看排序,还看强度:比如用打分,让大家说"我有多喜欢",这就超出了 Arrow 的框架(Arrow 只用排序)。
五、证据:理论与现实
理论预测。 多数决可能转圈;不同的计票办法可能选出不同的人;任何满足 Arrow 的前三条的规则,都是独裁。
证据。
- 理论。 Arrow 1951 年的《社会选择与个人价值》(Social Choice and Individual Values),来自 Arrow 的博士论文;Arrow 在 1950 年发表了一篇更早的论文《社会福利概念中的一个难题》(“A difficulty in the concept of social welfare”,我没有核对到期刊的卷页)。Arrow 与 Hicks 一起,获得了 1972 年的诺贝尔经济学奖(据转述)。
- 孔多塞悖论的频率。 上面我给出的 5.6% 和 8.8%,是"完全随机"假设下的数字;Tsetlin 等 2003 年(据摘要)指出,完全随机是最坏的情形,任何偏离都会降低圈的概率。Regenwetter 等人用真实选举调查数据的研究,报告了圈的"经验上的稀少"(据摘要),而后来的综述认为现实中的相关程度仍没有定论。
- 搅局者与克隆。 Tideman 1987 年在《社会选择与福利》(Social Choice and Welfare,4 卷 3 期,185–206 页)提出,一个好的投票规则,不应该因为加进一个与已有候选人相似的、不会赢的候选人,而改变结果;该文考察的一些常见规则,满足这一点的很少(据摘要的二手转述)。
局限。 Arrow 定理的前提是:只用选民的排序,且要给出一个完整的社会排序。如果允许用打分、允许只选出一个赢家(而不是完整的排序),结论会变;而且定理说的是一般的不可能,不是说在具体的选民群体里一定出问题。
分歧。 该放弃哪一条要求,是价值判断:是放弃无关选项的独立性,还是限制偏好,还是改用打分?不同选择反映了不同的价值(简单、公平、抗操纵、尊重强度)。至于现实里选举出现圈或搅局者的频率,则是事实问题,要靠数据。
六、常见的误用
- “多数决是最公平的办法。” 不一定。它可能转圈;在三个以上的候选人里,也可能选出大多数人更不想要的人。
- “Arrow 定理说民主不可能。” 不对。它说的是:同时满足那四条要求的规则不存在;放弃或放宽任何一条,就有办法。
- “选票里没有圈,就没有问题。” 不对。没有圈时,不同计票办法仍然可能选出不同的人。
- “搅局者是选民不理性。” 不对。每个选民都是理性、一致的;问题出在规则丢掉了信息。
- “波达计分比多数决更好。” 不一定。它违反了无关选项的独立性,也容易被策略性地操纵。
七、小结
- 孔多塞悖论:你 A > B > C,小周 B > C > A,小林 C > A > B,两两比较 A 胜 B、B 胜 C、C 胜 A。三个选民时,随机选票里有 12/216 ≈ 5.6% 形成圈;选民很多时约 8.8%(完全随机的最坏假设)。
- 不同的办法,不同的结果:41、34、25 的例子,只数第一名选 A;两两比较、波达计分、两轮决选都选 B。
- 搅局者:加进一个必输的 C,只数第一名的结果从 A 变成 B,没有任何人改变对 A、B 的看法。
- Arrow 定理:不限定偏好、一致性、无关选项的独立性、没有独裁者,四条不能同时满足(三个以上候选人)。
- 各办法的"罪名":多数决(转圈)、只数第一名和波达(违反无关选项的独立性)、独裁(违反没有独裁者)。
- 出路:限制偏好、放弃无关选项的独立性、用打分等强度信息。
回到那三个人选餐厅。下次你们用"投票"决定一件事,请想一想:你们用的是哪种计票办法?它用了每个人排序里的多少信息?如果加进一个"其实没人想去"的选项,结果会变吗?
思考题
- 三个选民:你 C > A > B;小周 A > B > C;小林 B > C > A。分别算出 C 对 A、A 对 B、B 对 C 的多数结果,说明是否转圈。
- 100 位选民:45 人 A > B > C;30 人 B > C > A;25 人 C > B > A。只数第一名、两两比较、波达计分,各选出谁?
- 100 位选民:40 人 A > B > C;15 人 C > A > B;45 人 B > A > C。(a)三个候选人,只数第一名,谁赢?(b)如果去掉 C,A 对 B,谁赢?C 是不是搅局者?
- 两个选民:你 A > C > B,小周 B > A > C。算出波达分。再把你的排序改成 A > B > C、小周改成 B > C > A(两人对 A 和 B 的看法没有变),重新算,说明波达计分违反了哪一条。
- 说明为什么"独裁规则"(社会排序永远等于某一个人的排序)满足 Arrow 的前三条,却不满足第四条。
- 想一个生活里"投票或排序合成"的例子(评选年度员工、决定聚餐的菜、评定比赛名次……),说说你们用的规则可能违反 Arrow 的哪一条,会带来什么问题。
思考题提示
- C 对 A:你 C、小周 A、小林 C(B > C > A 里 C 在 A 前面),C 胜,2 比 1。A 对 B:你 A、小周 A、小林 B,A 胜,2 比 1。B 对 C:你 C、小周 B、小林 B,B 胜,2 比 1。C 胜 A,A 胜 B,B 胜 C:转圈。
- 只数第一名:A 45,B 30,C 25,A 胜。两两比较:B 对 A:30 + 25 = 55 人觉得 B 好,B 胜;B 对 C:45 + 30 = 75 人觉得 B 好,B 胜。B 是孔多塞赢家。波达计分:A = 45 × 2 = 90,B = 45 + 30 × 2 + 25 = 130,C = 30 + 25 × 2 = 80。B 胜。
- (a)只数第一名:A 40,B 45,C 15,B 胜。(b)去掉 C:A 对 B:40 + 15 = 55 人觉得 A 好,A 胜。C 的存在,让结果从 A 变成 B,C 是搅局者。
- 原来:你 A 2、C 1、B 0;小周 B 2、A 1、C 0。A = 3,B = 2,C = 1,A 胜。改后:你 A 2、B 1、C 0;小周 B 2、C 1、A 0。A = 2,B = 3,C = 1,B 胜。你仍是 A > B,小周仍是 B > A,只有 C 的位置变了,A 和 B 的结果翻转了。违反了无关选项的独立性。
- 独裁规则:社会排序就是独裁者的排序。不限定偏好:任何偏好都能处理。一致性:如果所有人都觉得 X 比 Y 好,独裁者也觉得 X 比 Y 好。无关选项的独立性:社会怎么排 X 和 Y,只取决于独裁者怎么排 X 和 Y。可是,独裁者就是"独裁者",所以不满足"没有独裁者"。
- 开放题。例:评选年度员工,每人把候选人排序,用波达分。如果有人提名了一个明显不可能当选的人,可能会改变前两名的先后,这就是违反无关选项的独立性。