Arrow不可能性定理:独裁是唯一完美的选举制度

    由于某些原因,最近在整理以前的日志。偶然翻到这篇日志时,顺便在 Wikipedia 复习了一下 Arrow 不可能性定理的证明,惊奇地发现这个定理的证明过程非常困难但又非常初等,是一个门槛很低、老少咸宜的思维游戏。虽然不少人都翻译过 Wikipedia 上的这段证明,但我也想自己写一个自己的理解,一来做个笔记,二来也锻炼一下自己的表达能力。

    Arrow 不可能性定理是一个与选举制度有关的定理。选举制度,说穿了就是把所有选民的意见综合成一个全体意见的算法。选民的意见,无非是候选对象在心目中谁优谁劣,完整地反应在选票上,就是候选对象们从优到劣的一个顺序;形式最完整的全体意见,也就是候选对象的这么一个排列。因此,我们可以把整个选举制度想像成一个函数,输入 n 个排列(相当于 n 张选票),将会输出一个排列(相当于选举结果)。对输入数据的任何一处小改变,都有可能导致输出结果随之变化。作为一个合理的选举制度,它必须满足一些起码的要求。我们提出两个最基本的选举制度要求:

      1. 如果每张选票都认为 X 比 Y 好,那么投票结果中 X 的排名也必须比 Y 更靠前;
      2. 如果每张选票中 X 、 Y 的相对排名都不改变,那么投票结果中 X 和 Y 谁先谁后也不能变。

    我们将证明,同时满足上述两个条件的选举制度只有一种,就是选举结果唯一地由其中某个选民的选票决定。也就是说,独裁是唯一一种完美的选举制度。为了简便起见,让我们假设候选人只有 A 、 B 、 C 三个人。你会发现,下面的证明过程很容易扩展到多个人的情况。


    假设每张选票都把 B 放在最后一名。也就是说,每张选票都认为, A 比 B 好, C 也比 B 好。根据条件 1 ,最终投票结果中也应该满足, A 和 C 都排在 B 前面。也就是说,投票结果里 B 也是最后一名。现在,让我们按照一定的顺序依次把每张选票里的 B 从最后一名挪到第一名的位置上去,同时不断关注在改票过程中选举结果的变化。当所有的票都改完了后,根据同样的道理,投票结果中 B 自然就排到了第一名。因此,在改票的过程中,一定存在这么一个人,改完他的选票后,投票结果中 B 的名次靠前了(从最后一名升了上来)。我们把这张选票叫做“枢纽选票”。

    接下来的证明分成四个大步骤。我们第一步要证明的就是,在改票过程中,改完这张枢纽选票,投票结果中 B 的名次将会直接从最后一名一下子升到第一名。反证,假如此时 B 没有跑到投票结果的第一名去,那么投票结果要么是 A 、 B 、 C ,要么是 C 、 B 、 A 。不妨假设是 A 、 B 、 C 吧。现在,把每张选票中 C 的名次都改到 A 前面( C 本来就在 A 前面的那些选票就不用改了)。按照条件 1 ,最后的结果里 C 也应该跑到 A 的前面去。但同时,由于此时每张选票都把 B 列于第一名或者最后一名,调整 A 和 C 的顺序不可能影响到 B 、 A 之间的相对顺序,以及 B 、 C 之间的相对顺序,因此由条件 2 ,结果里 B 、 A 的相对排名和 B 、 C 的相对排名是不能变的。这就矛盾了:我们绝不可能在不改变 B 、 A 的相对位置以及 B 、 C 的相对位置的情况下,把投票结果 A 、 B 、 C 里 A 和 C 的位置互换。因此,把那张枢纽选票中的 B 提到第一名,一定让投票结果中的 B 也直接跑到了第一名去。

 
    注意,枢纽选票的产生是有前提的:它要从某个满足“每张选票里 B 都排最后”的情形开始,再按照一定的顺序把选票里的 B 都改成第一名,在此过程中才能产生对应的枢纽选票。如果具体的初始情形不一样,枢纽选票还一样吗?答案是肯定的。在第二步,我们要证明的就是,只要满足每张选票都把 B 放在最后一名(不管选票的具体内容是什么),并且按照同样的顺序进行改票,枢纽选票总会是同一张。

    这个原因很简单,关键就在于,我们总是把每张选票里的 B 从最后一名提到第一名。即使换一个不一样的初始情形,在改票过程的每一个时刻,每张选票里 B 和 A 、 B 和 C 之间的相对排名也都和原来一样,因而投票结果中 B 和 A 、 B 和 C 之间的相对排名也和原来一样。因此,投票结果里 B 的位置仍然会在同一个时候发生变化,枢纽选票还是同一张。

 
    在第三步里,我们要证明的是,这张枢纽选票有一个非常牛的性质:在任何情形下,它都能独裁 A 、 C 之间的相对排名。也就是说,这张枢纽选票认为 A 比 C 好,投票结果里 A 就一定比 C 好;反过来,它说 C 比 A 好,投票结果里 C 就比 A 好;并且此性质不依赖于任何前提条件,即使 B 不在各选票中的特殊位置,结论同样也成立。现在,我们就考虑任意一组选票,无妨假设其中枢纽选票里 A 比 C 靠前,我们将证明投票结果中 A 也是排在 C 前面的。证明的思路是,对各选票进行一系列不涉及 A 、 C 间相对排名的修改,从而看出投票结果里 A 在 C 前面。我们先把所有选票中的 B 都排到最后一位去,注意,这一步不会改变投票结果中 A 、 C 的先后顺序,但却让前面的结论得以适用。然后,我们把枢纽选票之前的所有票里 B 的位置都挪到最前面,由前面的结论,结果中的 B 仍然处于最后一位(因而 A 位于 B 前面)。接下来,我们把枢纽选票(它应该是 A 、 C 、 B 的顺序)改成 A 、 B 、 C ,由于这张票中 A 、 B 的相对位置没变,因此结果中 A 、 B 的相对位置也没变, A 仍然在 B 前面。接下来,我们把枢纽选票改成 B 、 A 、 C ,由前面的结论,此时结果里的 B 跑到了最前面(因而排到了 C 前面),但把枢纽选票从 A 、 B 、 C 改成 B 、 A 、 C 时并没有改变 B 和 C 的相对位置,因此刚才的投票结果中 B 也应该在 C 的前面。也就是说,枢纽选票是 A 、 B 、 C 时,投票结果里 A 在 B 前, B 在 C 前,也就是说 A 排在 C 前面。但上述所有修改都不会改变任何一张选票里 A 、 C 的相对排名,因此投票结果中 A 其实自始至终都在 C 前面。这就证明了,投票结果里 A 、 C 的相对排名完全取决于这张枢纽选票,不管其它选票是什么样的。

 
    最后一步证明就是,这张选票不但独裁了 A 、 C 的相对排名,它直接独裁了所有人的排名。原因很简单:按照之前的推理,还会有一张独裁 A 、 B 相对排名的选票,另外还有一张独裁 B 、 C 相对排名的选票;但一山不容二虎,这三个独裁者只能是同一个人,否则一个人说左一个人说右,就会立即产生矛盾。具体地说,首先,这三个独裁者肯定不可能是三个不同的人,否则 A 、 B 的独裁者说 A 比 B 好, B 、 C 的独裁者说 B 比 C 好, A 、 C 的独裁者说 C 比 A 好,投票结果就得同时满足 A 在 B 前、 B 在 C 前、 C 在 A 前,这是不可能的。这三个独裁者也不可能是两个人。比方说其中一人同时独裁了 A 、 B 和 A 、 C ,另一人则只独裁 B 、 C ,那么如果前者说 B 在 A 前面, A 在 C 前面,后者又说 C 在 B 前面,同样不会有兼顾两者的投票结果。因此,独裁者只能有一个,它就是填写枢纽选票的那个人。

    至此,我们就证明了,满足那两个基本条件的选举制度只有一种——独裁制度。

 
    上述结论有另外一种等价的表述方法:同时满足全体一致性、无关候选人独立性(就是那两个基本条件)以及非独裁性这三个条件的选举制度理论上是不存在的。这就是美国经济学家 Kenneth Arrow 提出的 Arrow 不可能性定理:不存在完美的选举制度。

64 条评论

  • hhtytommy

    我看到的证法是定义了一个可决断组,证明了两个引理的。

    • Charl

      the debt ceiling has been raised so many times before, but it isn't a joke. It's not just a name "the debt ceiling, it's what we owe and man are we way the fuck over our heads, stop spending, the spending corruption and cronyism of this adiaristnitmon is the joke.

  • hhtytommy

    如果不是每张选票都把 B 放在最后一名? 怎么办?

  • Mr.笨

    看完我凌乱了……

  • fengseqiuyuan

    推论的第一步就有问题:
    在第一次改票(部分票的B从最后移到最前,注意是部分)的情况下,BC、BA之间的相对顺序本来就不确定,B在前B在后两种情况都有。在第二次改票(全部票的C移到A前),作者却以“结果里 B 、 A 的相对排名和 B 、 C 的相对排名是不能变的”作为反证,试问两种排名同时存在,何谈相对排名不变,明显错了

  • kuphrer

    这篇文章有误导性,一张”选票”应该是一个偏序而不是m67文章中暗示的,一个全序,建议m67修改。
    当然,现实生活中的选举也不全然是偏序的,也就是并不全然是”理性”的。考虑这个情况:A和B同属一个党派,党派遵循赢者通吃规则,因此对某一个内心中对A评价极低而对B评价极高的人,尽管他不愿意,仍然会把选票投给A,即当让他在A,B两人中选择时,他会选择A,但如果引入另一个党派中的候选人C时,就可能会发生该选民在B和C中选B,C和A中选C这样的情况,虽然完全合理,但并不符合偏序的性质。

  • biohu

    看得我晕晕乎乎。。。

  • morrowind

    很简单,引入加权就能解决悖论。

  • fengseqiuyuan

    所谓“满足全体一致性”,最开始是指“B在最后一名”,不过随着部分票将B提到最前(如果是全体改票,那第一步推论中的“枢纽选票”也就失去了意义),这个“全体一致性”已经不存在了

  • morrowind

    推理过程没任何问题,楼上几位自己再推敲推敲。
    不过个人认为的前提“2. 如果每张选票中 X 、 Y 的相对排名都不改变,那么投票结果中 X 和 Y 谁先谁后也不能变”是不合理的假设。
    No.1 > No.100 跟 No.99 > No.100,给弄成一样的,这能说服人么!
    引入加权,应该还是存在完美选举制度的。

  • fengseqiuyuan

    实际上,现实中确实存在所谓“枢纽选票”,比如选举中双方打成平手后,最后一个人的“决定性的一票”的确可以决定双方的成败。但你要说这个人是独裁者,“无视其他人”就可以决定结果,这就是概念性的错误了。独裁者可以一个人说了算,那个人却不能失掉之前的50%选票的基础,如果只有他那一张票,根本无济于事

  • fengseqiuyuan

    还有,Arrow 不可能性定理的意思是同时满足ABC这三个条件的选举制度理论上是不存在的。
    这意思可并不是说,满足C的选举就一定同时满足A和B,更不是说“独裁是唯一完美的选举制度”,这概念偷换的太明显了

  • fengseqiuyuan

    还有,Arrow 不可能性定理的意思是同时满足ABC这三个条件的选举制度理论上是不存在的。
    这意思可并不是说,不满足C的选举就一定同时满足A和B,更不是说“独裁是唯一完美的选举制度”,这概念偷换的太明显了