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 不可能性定理:不存在完美的选举制度。

发表评论

8  +  2  =