不可能完美的选举 – Arrow不可能定理_不可能了是什么意思

 

1.不可能です

这是我以前blog里的一篇老文，觉得有必要保留下来不要紧张，本文无关政治，是数学下面要说的是一个选举的问题，我们规定一些看上去完全合情合理的条件，结果却发现没有任何一种选举制度能够满足从这个意义上讲，任何一种选举制度都是有缺陷的。

2.不可能完美的经典理论

下面把问题形式化一下，有N个投票人，K个候选人每个投票人根据自己的喜好，把这K个人排个序，设这K!种可能的序列组成的集合为L(K)一个选举制度，就是N个L(K)的笛卡尔积到一个L(K)的映射前面这句话是吓人用的，说白了就是，选举制度就是一个算法，输入是N个{1..K}的排列，设为R1,R2…Rn，每个排列表示一个投票人的观点，算法的输出是一个{1..K}的排列，表示结合所有的观点计算出一个最终的投票结果。

3.啥叫不可能

我们要证明的是，不管你用什么算法在某种意义上都是有缺陷的我们觉得这选举算法应该满足如下3个条件：(1)一致性或帕雷托最优性(unanimity): 如果对于全部N个排列，候选人a都排在b的前面，则最终结果a也应该排在b的前面

4.不可能完整的样子

(2)非独裁性(non-dictatorship): 不存在这样一个i (1 <= i <= n)，使得无论输入是什么，总的结果总和Ri相同(3)无关因素独立性(independence of irrelevant alternatives。

5.ばかな不可能

, 以下简作IIA): 对于两组可能不同的输入R1,R2…Rn和S1,S2…Sn，如果对于每个i，候选人a和b的相对顺序在Ri和Si里都一致，则由R1,R2…Rn得出的最终结果和由S1,S2…Sn得出的最终结果中，a和b的相对顺序是一样的。

6.不可能完不可能完成的任务

条件(3)的另一种理解方式为，如果我们只关心K个候选人的一个子集，假设说是M个候选人，那么把投票人的排列里我们不关心的人都划去，剩下的仍保持原来顺序，就好像只有这M个候选人一样然后用同样的选举算法计算，最终这M个人的顺序和原来考虑全部K个人时这M个人的相对顺序是一样的。

7.不可能konodio

这三个条件看上去似乎都很合理，然而我们可以证明，没有任何一种选举算法能同时满足三条下面我们就证明，满足(1)和(3)的选举算法，必然不满足(2)，也就是说，满足一定条件的民主就变成了独裁…… -_-证明可以分为三部分：

8.不可能不行

第一部分：存在关键的投票人我们考虑N个投票人和三个候选人A,B,C如果所有投票人都把B排在最后，根据一致性，显然在总排名里B排在最后（我们把这种状态叫做状态1）同理，如果所有人都把B排在最前，总排名里B就在最前。

9.不可能的下一句

下面我们考虑从状态1开始，编号从1到N的N个投票人，逐个把B从最后改成最前，每当一个投票人改变一次排列，就重新计算一次总的排名这样的话，一开始B总排名垫底，到最后总排名最高，这中间必定有个变化的过程我们会发现，这个变化是直接“跳”上去的，也就是说，在中间的某个投票人改变自己的排列后，B的总排名会突然从垫底跳到最高，没有中间过程。

10.不可能呀

我们用反证法，假设存在一个中间过程，也就是说，在某个投票人（不妨设为第n个）改变主意后，B升到了A和C的中间不妨设此时总排名是C>B>A（A>B>C同理），现在我们把每个投票人的排列里的A都改到C的前面，由一致性可知，总排名里A也应该在C前面。

又因为在投票人的排列里B不是在最前就是在最后，我们改变A,C的顺序对B的相对位置没有影响，由IIA知，因为BA, BC的相对顺序都没变，故总排名里BA,BC的相对顺序也都不变但此时就出现了矛盾，要想让A改在C前面，BA,BC的相对顺序不可能不变。

故假设不成立，第一部分得证第二部分：存在决定A与C相对顺序的独裁者继续第一部分的讨论，我们把B的排名发生跳跃之前的状态，也就是前n-1个人把B排在最前，后面的人都把B排在最后的状态，称为状态2，此时总的排名里B在最后。

把B的排名发生跳跃之后的状态，也就是前n个人把B排在最前，后面的人都把B排在最后的状态，称为状态3，此时总的排名里B在最前下面我们要证的是，这第n个人就是决定A与C相对顺序的独裁者，他说谁在前面谁就在前面。

设第n个人的投票是A>B>C，此时如果我们只考虑A和B，把C去掉，我们会发现A,B的相对顺序和状态2里是相同的（前n-1个人AB），于是根据IIA，A-B的最终相对顺序也与状态2相同，也就是说，A应该在B前面（因为状态2里B最终在最后）。

同理，如果我们只考虑B和C，我们发现B,C的相对顺序和状态3里是相同的（前n个人B>C，后面的人BB>C。

若设第n个人的投票是C>B>A，同理可得最终顺序是C>B>A现在我们只考虑A-C相对顺序，把B完全忽略掉，可以发现A-C的相对顺序是由这第n个人决定的注意这里是我认为整个证明里最难理解的一点：根据IIA，在我们决定A-C相对顺序时，。

B是无关紧要的尽管我们的证明里出现了B，但最终的结论里没有B的事，引入B只是为了证明独裁者的存在性在这里我猜很多人都会有的一个疑问是：我们是在如此特殊的状态下才证明了最终结果取决于第n个人，为什么可以得出在所有状态下都成立？如果我不是让前n-1人都把B排最前而后面的人都把B排最后，而是随便乱给一个输入状态呢？（如果你没有这个疑问，说明你的智商远高于我，这是一件概率非常大的事，那样就可以跳过下面的这段解释了）。

解释是，我们确实可以乱给一个输入，根本不是前面状态1状态2状态3的样子，但因为现在只考虑A-C相对顺序，我们可以从这个乱给的输入里把其它的候选人都拿掉，结果是不变的，再把B按照状态1的情况插进去，结果还是不变，再逐个地把B从最低提到最高，结果还是不变，但是当总排名里B出现跳跃的时候，独裁者（那第n个人）就找到了。

如果我们把此人对A,C的排名交换位置，则总排名里A,C也交换位置这时你可以再把所有的B都改回一开始乱给的那种输入下的位置，由IIA知B的位置是不影响A-C顺序的这样我们又回到了原来的输入，只是交换了第n个人对A,C的排名，结果总结果里就跟着变化了。

所以第n个人确实是A-C顺序的独裁者第三部分：独裁者只有一个这一部分的证明最简短了第二部分我们只证明了决定A-C顺序的独裁者存在，当然同理决定B-C顺序和A-B顺序的独裁者也存在，现在的问题是这些独裁者是不是同一个人？。

假设A-B独裁者x和B-C独裁者y不是同一个人，则由这两个独裁者的意见就可能决定了A-C的顺序比如x投票是A

最后我们把问题扩展到大于三个候选者，由IIA，前面的所有讨论对任意一个包含三个候选者的子集都仍然成立，于是每个三元组都有一个独裁者由类似第三部分的证法易知，所有这些独裁者都是同一个于是总的命题得证后记：

这其实是博弈论里的一个叫做Arrow不可能性定理的东西，我只是把这个Wiki页面翻译了一下，稍微加入一点自己的理解关于这个定理网上能搜到很多介绍，不过大都没有涉及具体的证明过程我觉得这个证明还是颇为锻炼逻辑思维能力的，而且不需要高深的数学，每一步都只是简单的逻辑推理，最终得到了神奇的结论。

这个定理能说明一切选举都无效么？显然不是的实际上现有的选举制度都是对前面的三个条件作出了妥协的结果，但是他们有很多都工作得很好三个条件里限制最强的就是IIA，我们也发现了在上面的证明中IIA无处不在，而现有的选举制度大都不满足IIA的要求。

关于此问题的后续研究很多都致力于探索如何适当放宽IIA的要求来更准确地评价选举制度的好坏感兴趣的可以深入看看wiki里的参考文献，我也不懂就不多说了Blog: 不可能完美的选举 - Arrow不可能定理