由于某些原因，最近在整理以前的日志。偶然翻到这篇日志时，顺便在 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 不可能性定理：不存在完美的选举制度。
沙…沙发…
我看到的证法是定义了一个可决断组，证明了两个引理的。
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.
如果不是每张选票都把 B 放在最后一名？ 怎么办？
地 地板
看完我凌乱了……
推论的第一步就有问题：
在第一次改票（部分票的B从最后移到最前，注意是部分）的情况下，BC、BA之间的相对顺序本来就不确定，B在前B在后两种情况都有。在第二次改票（全部票的C移到A前），作者却以“结果里 B 、 A 的相对排名和 B 、 C 的相对排名是不能变的”作为反证，试问两种排名同时存在，何谈相对排名不变，明显错了
这篇文章有误导性，一张”选票”应该是一个偏序而不是m67文章中暗示的，一个全序，建议m67修改。
当然，现实生活中的选举也不全然是偏序的，也就是并不全然是”理性”的。考虑这个情况：A和B同属一个党派，党派遵循赢者通吃规则，因此对某一个内心中对A评价极低而对B评价极高的人，尽管他不愿意，仍然会把选票投给A，即当让他在A,B两人中选择时，他会选择A，但如果引入另一个党派中的候选人C时，就可能会发生该选民在B和C中选B，C和A中选C这样的情况，虽然完全合理，但并不符合偏序的性质。
咦？Pingzhong Tang 证阿罗不可能定理的的论文里 http://www.cs.cmu.edu/~kenshin/arrow_aij.pdf 说，选票和选举结果都是全序（linear order = total order）
看得我晕晕乎乎。。。
很简单，引入加权就能解决悖论。
所谓“满足全体一致性”，最开始是指“B在最后一名”，不过随着部分票将B提到最前（如果是全体改票，那第一步推论中的“枢纽选票”也就失去了意义），这个“全体一致性”已经不存在了
推理过程没任何问题，楼上几位自己再推敲推敲。
不过个人认为的前提“2. 如果每张选票中 X 、 Y 的相对排名都不改变，那么投票结果中 X 和 Y 谁先谁后也不能变”是不合理的假设。
No.1 > No.100 跟 No.99 > No.100，给弄成一样的，这能说服人么！
引入加权，应该还是存在完美选举制度的。
实际上，现实中确实存在所谓“枢纽选票”，比如选举中双方打成平手后，最后一个人的“决定性的一票”的确可以决定双方的成败。但你要说这个人是独裁者，“无视其他人”就可以决定结果，这就是概念性的错误了。独裁者可以一个人说了算，那个人却不能失掉之前的50%选票的基础，如果只有他那一张票，根本无济于事
还有，Arrow 不可能性定理的意思是同时满足ABC这三个条件的选举制度理论上是不存在的。
这意思可并不是说，满足C的选举就一定同时满足A和B，更不是说“独裁是唯一完美的选举制度”，这概念偷换的太明显了
还有，Arrow 不可能性定理的意思是同时满足ABC这三个条件的选举制度理论上是不存在的。
这意思可并不是说，不满足C的选举就一定同时满足A和B，更不是说“独裁是唯一完美的选举制度”，这概念偷换的太明显了
我觉得关键选票和独裁还是两个不同的概念的。
对选举本身来说这不重要吧
主要问题是，社会中绝大多数人都不完全知道一个候选人的详细情况，想建立一个完整的关系，一定程度上只能靠信任和猜测
如果每个人都特别详细的了解所有候选人，那么根本不需要选举，独裁是没有任何问题的，最多公开征集点建议就可以了
关键是每个选举人都有均等的概率成为“独裁者”。
关键选票和“独裁”是两个概念，只要和最终结果相同的任意一张票都可以“视为”关键选票，但不意味这张票“独裁”（任何情况下仅靠这一张票就决定结果）
社科类的问题是无法用自然科学搭建的简单模型得到有效解决的，我没有看具体的证明过程，不过很显然这个模型过于简单，忽略了很多因素。那这个模型得到的结论自然就非常局限了。
同意11楼的说法，
[
前提“2. 如果每张选票中 X 、 Y 的相对排名都不改变，那么投票结果中 X 和 Y 谁先谁后也不能变”是不合理的假设。
No.1 > No.100 跟 No.99 > No.100，给弄成一样的，这能说服人么！
]
为什么“每张选票中 X 、 Y 的相对排名都不改变，那么投票结果中 X 和 Y 谁先谁后也不能变”才算完美的选举？
关键是每个选举人都有均等的概率成为“独裁者”。 +1
恩 这也是我想说的
“关键是每个选举人都有均等的概率成为“独裁者””
虽然确实是这么回事,但如果说选举像摇奖一样取决于随机性的话就太那个了…
传递性满足吗？
凌乱了
或者说，没有完美的民主制度的原因是选民在这个算法中都导致了自涉？
说加权的同学们，你们有没有自己去看看Arrow的东西？使用加权的后果就是权值做调整其结果排名也可以相应调整，并不违反全局一致性和偏好独立性。
一直认为取排名平均值再比较相对大小不就行了？？
我幼稚了？
一直认为取排名平均值再比较相对大小不就行了？？
我幼稚了？?
推理是没有错的，楼上某些同学不用激动，我觉得还是wiki上要说的清楚些，特别是指明1到n这种推理手法比较适合我们学数学的吧，感觉翻译成中文之后有点绕……
那依照不同的顺序改票，不是可以产生不同的“枢纽选票”吗？有点像那个“老虎悖论”。
有翻页吗….
话说第一个是不证自明的，第二个就有一些问题了，有点第五公设的感觉
发现一个问题不解，问一下：
假定现在有abc三个候选人，100个投票人，投票方式为每人都对abc三人排序，第一名100分，第二名1分，第三名0分。
现在60人acb，40人bca，于是a总分6000分，b总分4000分，c总分100分，总排名abc。
然后要求所有人选票中b的位置不变，a与c的位置置换，于是c6000分，b4000分，a100分，总排名cba。
但是，这里所有选票中b要么第一要么最后，所以b相对a的位置在ac置换前后不变，b相对c的位置在ac置换前后不变，但是总排名中ab相对位置发生改变，bc相对位置发生改变，所以与“最基本的选举原则第二条”矛盾。
可见，第二条“最基本的原则”本身就是错误的。
T’es tu en train d&unoro;squs dire qu’il faut croire aux fantômes, aux vampires, aux dragons, aux superhéros et aux aliens ? Parce que tsé au nombre de films, de livres …..
接上：
由于“最基本的选举原则”第二条本身是错误的，所以后面对于“枢纽选票”的探讨就存在问题——可以构造出将b从最后一位变为第二位而不是第一位的“过度选票”。
比如，100人选abc，首票100分，次票1分，尾票0分。
以开始所有人选acb的顺序，于是a10000分，c100分，b0分。
现在开始逐个从acb变为bac，于是第一次改变后a9900分，c99分，b100分，于是b从最后变为第二，而不是第一。
所以在这个例子中不存在“枢纽选票”，只有“过度选票”，而且有50张。
总结说来，这个问题的根本就在于我们要求了“最基本的选举原则第二条”这个不合理的要求，是这条导致了“完美的选举就是独裁”这个不合理的结果。
证明过程没错，不过要求2不合理啊
讨论一下，以前读书的时候只是知道这个定理，今天仔细研究了推导过程，现在觉得阿罗不可能定理只是一个扭曲了的语言逻辑。
我觉得这个更准确的表述应该是，只有当某个和社会结果一致的投票碰巧位于n/2+1(n为偶数）(n+1)/2(n为奇数）（这个位置即枢纽票）的情况下，才能在某个逻辑演绎过程（即定理的证明）当中不会产生矛盾的进行推导。
简单来说，n=5的5张选票，cab,acb,acb,cab,cab，按照推导过程，枢纽票是第三票，在进行到第三步的变换时，把b移到a和c的当中时，会出现bca,bac,abc,cab,cab这样的情况，从而有c>a>b>c的结果，于是第三步的推导出现矛盾。而当把选票顺序变换成acb,acb,cab,cab,cab（即第一三票的位置交换）的时候，就可以顺利推导下去，不会出现悖论。由此阿罗认为这个枢纽票就决定了社会的观点，成为了独裁。但是从这个对比里面很明显地看到，其实是因为第三票碰巧和最终的社会结果一致，所以做为枢纽票才能保证逻辑顺利。这是一个简单的相关性是否等于因果性的问题。
而且不可能性定理证明当中所谓的枢纽票，是以把所有选票顺序排序的结果，顺序的不同导致枢纽票的位置是一样的，但是对应的选票可能不是同一张，也就是说，碰巧成为独裁者并不是因为你投了什么，而是排序是不是正好排在那个位置上（而且碰巧和社会结果一致）。这完全和普遍对独裁的文字理解是两回事。这个定理只不过是一个数字逻辑被语言逻辑给扭曲了，然后语言逻辑又因为其危言耸听性变成了一个所谓的定理。
我的观点基本和12楼是一个意思，只不过用举例的方式表述出来了。这个定理做为单纯的数学逻辑的演绎是没有问题的，但是把这个数学逻辑变换成语言逻辑的人的逻辑是有漏洞的。
另外33/34楼，你说的东西和阿罗的模型完全是两回事，那个模型里就是严格的可选对象的两两分对比较决定最终的排序。做为一个逻辑推理过程你不能因为不接受前提假定就认为逻辑推理的过程是错误的。你是完全自拟了一套游戏规则然后认为另一套游戏规则是错误的。
the only problem ive ever had with the versions of this story is the fact that…wooden trunks arnt soundproof at all. if her face was frozen in a scream why did no one hear.VA:F [16.o21_1199](fr.m 0 votes)
这个定理的推导过程当中偷偷引入了一个sequential（顺序）的概念，即投票有先后的，但是这实际上和大家认同的投票机制是违背的，投票只是一个pooling的过程，大家把所有的票放到一起清点。所以因为有这个顺序的过程在，才会出现这张枢纽票，但是因为实际投票的过程不是顺序的过程，所以每张和最终社会排序结果一样的选票都有同样的机会会成为这个“独裁者”。
这个月刚见到Arrow，他来演讲 ..
拜读了楼主很多篇日志了，非常佩服，但楼主可能不是学经济学的吧，Arrow不可能定理可不是这样证明了，其结论也不是这种含义。Arrow定理是说四个基本原则不可能同时满足，即偏好可加总规不能同时满足偏好排序非循环、弱帕累托最优、非独裁、选民独立性，且有非常严格的“选民间必须存在不可协调的矛盾”，其结论为选举程序越严格，越难以实现民主。并且现在一些理论可以使得“偏好排序非循环性”更加弱化。数学证明在其原著上可以查到，我在这里只说思想了
不太才，终于看懂了。
You can use the &#tr86;sma21phone detection’ to automatically direct the smart phone users to the mobile site, but the user is directed to the index or home page. It would take additional coding on each regular page to have it direct to a specific mobile page.
阿羅不可能定理廣泛存在於現實生活，主要在法學上的投票悖論，“不可能”指的不是什麼完美投票制度的“不可能”，而是指的不可能存在“集體偏好”這個東西。
事實上，沒有人說民主投票是最完美的制度，只是說他是最不壞的制度。樓上的樓上的樓上Fischer說的很清楚了。
首先这里有个很诡辩的前提，那就是枢纽选票的出现是和唱票顺序有关的。
这里提出的两个条件并不意味着完美，其很明显不保证同票同权，即对任意选票集合，其任何排列作为输入得到的输出相同。
比如说，把最后一张选票上的候选人顺序直接作为结果输出，就已经满足那两个『基本选举前提』来。
这篇文章最后的结论应当是，不存在同时满足这两个『基本选举条件』和同票同权的排序(选举)方案，这个结论就不那么刺耳了。
膜拜
C没有什么大不了的，投票时并没有知道其他人的选举情况。如果每个人都有可能投出枢纽选票，而不能人为控制（何况改变唱票顺序枢纽票就可能不再有效），更不能在选举开始前通过1个人的投票策略确定某结果的产生，那么就是公平的
哈哈，我也研究过这个问题！http://1.likit.sinaapp.com/?p=121
range voting通过引入score 解决了这个问题。a
range voting通过引入score 解决了这个问题。
lz原来是个高级五毛啊，这是lz的献菊之文
一直认为取排名平均值再比较相对大小不就行了？？
GE
学博弈论讲到 IIA 条件，赶紧回来看一下。嘿嘿。