写完上一篇笔记之后，我的匹配理论(Matching Theory)笔记就准备进入一个新的板块：College Admissions模型了。相比起婚姻市场，College Admissions更贴近读者们的现实生活（?），但也更加复杂、硬核。在写该模型之前，我还是决定先写点论证简单、结果有趣的经济学，比如这一篇——阿罗不可能定理(Arrow's Impossibility Theorem)。

此定理名称奇葩，不需要多少专业知识就可以对其津津乐道；横跨数学、经济学、政治学三大领域，且结果十分反直觉，后续对社会选择理论(Social Choice Theory), 福利经济学(Welfare economics)及其他政治科学的影响之深远也是其他定理无可比拟的。简直就是经济学界的海森堡测不准定理(Heisenburg's Uncertainty Principle)（当然，正确的名称是海森堡不确定性原理。)

历史上，对民主制度优劣性的讨论从未停息，尤其在民主和法西斯产生激烈碰撞的二战之后。于是，也有许多经济学家和政治学家想探究一个问题的答案：民主制度是建立在投票表决上的，那是否存在一个完美的投票机制呢？

然而，在1951年，历史上最负盛名的数理经济学家之一，后来的炸药奖得主肯尼斯.阿罗(Kenneth Arrow)横空出世，用数学方法证明了此后饱受非议的阿罗不可能定理。通俗地讲，这个定理表明在一个民主社会中，满足特定基本条件(帕累托效率、独立于无关选项)的投票机制必然导致独裁者(即一个能完全操纵选举结果的投票者)的出现，说明了一个完美的民主投票机制不可能存在。

对于这个定理的解读则见仁见智了。有人用此来质疑民主本身，但也有人倾向于淡化它对现实社会的启示。比如，有的人会觉得模型本身太有局限性，和现实中的情况不够一致。

笔者完全没有学过政治学，这篇文章也不会对民主、独裁社会的优劣性进行讨论。这篇文章的结构是从几个经典的投票悖论引入常见投票机制的缺陷，然后定义什么是一个好的投票机制，再介绍阿罗不可能定理和此后学术界对它的讨论。现实世界千变万化，笔者个人觉得这个定理数学上很漂亮，却对真实社会启示不够大。

阅读本篇笔记，需要具备小学二年级的数学知识——1000以内的加减乘除、初中水平的阅读理解能力以及一颗好奇的心。如果想亲手尝试阿罗不可能定理的证明，还需要一颗特别好用的脑子。仅此而已。

让我们开始吧。

先来看一个美国大选的例子吧。

2000年，争议最大的美国大选之一，佛罗里达州。共和党的小布什(Bush)以537票的微弱优势战胜民主党的戈尔(Gore)拿下了这个州的选票。

这里补充一句，美国的大选机制是“Winner-takes-all”, 赢得一个州的选举即可以获得该州的所有选票。

大选中有一个绿党的独立候选人叫拉尔夫.纳德尔(Ralph Nader), 在一番大力宣传之后成功获得了总数2.7%的选票。然而，正是他改变了选举的结果：民调显示，在佛罗里达投给他的97421人里，三分之二喜欢戈尔多过布什。也就是说，在佛罗里达，喜欢戈尔的人其实多过布什。而如果赢下佛罗里达之战，当选总统的就会是戈尔，后来发动阿富汗和伊拉克战争的可能也就是他了。戈尔很气，民主党更气。

当时美国大选中每个州的投票机制，叫多数票制(Plurality), 俗称少数服从多数。每个投票者选出自己最心仪的候选人，得票数最高的当选。然而，上面的美国大选暴露了它的两个问题：一个微不足道的候选人有可能会影响最终的结果；选出来的候选人不一定是最多人喜欢的——在佛罗里达更多人喜欢戈尔多过布什。

这样的情形也发生在了凤南小学三年八班的一次班长选举中。班里有297名学生参与投票，如下是他们的偏好排序：

101 李雷 \succ 小刚 \succ 韩梅梅

100 韩梅梅 \succ 李雷 \succ 小刚

95 小刚 \succ 韩梅梅 \succ 李雷

1 小刚 \succ 李雷 \succ 韩梅梅

举个栗子，第一行表示有101个人喜欢李雷多过小刚，喜欢小刚多过韩梅梅。

凭借着多数票制，李雷以101:100的优势战胜了韩梅梅当选班长。然而，韩梅梅一点也不服气。

明明有195个人喜欢她多过李雷啊。如果她和李雷单挑，毫无悬念获胜的明明是她啊！

不服气的韩梅梅努力学习，在长大之后成为了一名经济学家，在多数票制的基础上发明了一种新的投票机制：

在这个例子中，第一轮没有候选人票数过半，于是票数最少(96票)的小刚遭到淘汰。投给小刚的96人中，有95人在剩余的候选人中最喜欢韩梅梅，他们的票数转移给了韩梅梅；1人票数转移给了李雷。

在第二轮中，韩梅梅获得了195票，李雷获得了102票，韩梅梅成功当选班长。

韩梅梅终于凭借芝士的力量，报了小学的落选之仇。

排序复选制的缺点也不少，比如比多数票制更容易出现平局，需要事先制定一种打破平局的规则(Tie-breaking Rule)。

除了多数票制和排序复选制，生活中常见的投票机制还有很多，像认可投票制(Approval Voting, 投票者给自己喜欢的候选人（们）点赞，赞数最多的候选人当选）和累计投票制(Cumulative Voting, 每个投票者有一定数量的点数，自行在候选人之间分配。）碍于篇幅和钢铁雄心4太好玩的原因，笔者不会在这一一介绍。但是有两个投票机制和一个概念不得不说：

比如刚刚那个例子：

凤南小学三年八班班长选举

101 李雷 \succ 小刚 \succ 韩梅梅

100 韩梅梅 \succ 李雷 \succ 小刚

95 小刚 \succ 韩梅梅 \succ 李雷

1 小刚 \succ 李雷 \succ 韩梅梅

李雷： 101 \times 2 + 100 \times 1 + 95 \times 0 + 1 \times 1 =303

韩梅梅： 101 \times 0 + 100 \times 2 + 95 \times 1 + 1 \times 0 = 295

小刚： 101 \times 1 + 100 \times 0 + 95 \times 2 + 1 \times 2 = 293

在波达投票制下，仍然是李雷当选。而且这次韩梅梅也不好意思直接说她比李雷更适合当班长了，毕竟她分数确实没李雷高。

然而，这个例子可能会出什么问题呢？

思考30秒继续往下看。

让我们假设，选举当天，小刚一看民调中自己垫底，于是抢先一步退出了竞选，回家追马上开播的半泽直树2去了。这时的波达投票制暴露了和多数票制一样的缺点：垫底的小刚退出了选举，竟然改变了选举结果，使得韩梅梅超越李雷当选了班长。

经济学家根据这些例子，归纳出了一个“完美的”投票机制应该具有的特点之一：独立于无关选项(Independence of Irrelevant alternatives, IIA). 通俗的讲，两个候选人之间的最终排序不应该取决于每个投票者对他俩与其他候选人之间的相对排序（比如，李雷vs韩梅梅的结果不应该和李雷vs小刚和韩梅梅vs小刚的结果有关），只应该取决于他俩之间的相对排序。这样的话，任意的候选人退选都不会影响到选举结果。我们会在后面详细解释。

有个朋友说，小刚这个名字比起李雷和韩梅梅差的太多了。但小刚的故事其实很精彩。

这个小刚，不就是第一个例子里的拉尔夫.纳德尔吗。他的一生中曾经五次参与大选，没有一次得到超过3%的选票，却改变了美国的历史。于是，在2000年被坑了一把的民主党在04年大选前气急败坏地在二十几个州对拉尔夫提出了诉讼，想通过法律手段取消他的竞选资格。最后他只在11个州获得了参选资格，自知当选无望的他也退出了竞选。

他还有一个身份，是韩梅梅的老公——人民教育出版社小学英语配套教材《派斯英语》中，韩梅梅嫁了一个新人物，叫韩刚。

波达投票制还有一个缺点。不知道大家还记不记得上一篇笔记讲到的抗策略性(Strategy-Proofness), 估计不记得了吧。

通俗地讲，一个“抗策略”的投票机制下，不管其他人如何投票，每个投票者都没有动机去说谎，即汇报假的偏好排序——说真话永远是最优的策略（之一）。然而，波达投票制并不是抗策略的：

在1991年的基里巴斯总统选举中，政府党派候选人Teatao Teannaki的支持者就利用了这个特点，将对他威胁最大的竞争对手Teburoro Tito和Tewareka Tentoa排在最后，帮助Teannaki赢得了选举。但很显然，Teannaki的支持者中，并不是每个人都最讨厌Tito和Tentoa.

把他们的名字打出来是为了吐槽他们的名字——这个国家的政客是都和字母T过不去么2333

当然，此前提到过的投票机制也都不是抗策略的（为什么？），只是在波达投票法中战略投票更容易操纵选举结果罢了。

波达有个死对头叫孔多塞(Condorcet), 他提出了一个和凤南小学三年八班班长选举类似的例子，说明了波达投票制中失利候选人是否参选可能影响到最终结果的特点。他认为这是不合理的。但他不仅满足于做一个杠精，还提出了自己的解决方案：

孔多塞投票制避免了上文中波达的硬伤，即无关候选人是否参选会影响到最终结果。但它的缺点也很明显：孔多塞赢家不一定存在。

作为对孔多塞投票制的回击，孔多塞提出了孔多塞悖论（我锤我自己？）：

受到新冠疫情的影响，凤南小学三年八班的班主任不无遗憾地宣布，本届选举改成线上进行，希望大家踊跃参与积极投票。

于是，班里的297名学生积极响应，最终共有3名学生成功说服家长他们真的不是在玩电脑，从而参与到投票中。

他们的偏好排序如下：

武藏 李雷 \succ 韩梅梅 \succ 小刚

小次郎 韩梅梅 \succ 小刚 \succ 李雷

喵喵 小刚 \succ 李雷 \succ 韩梅梅

如果两两比较，那么李雷胜于韩梅梅，韩梅梅胜于小刚，小刚又胜于李雷。不管选择了谁，都存在一个可以让多数人更满意的候选人。

并不存在一个孔多塞赢家：三个候选人达成了李雷——韩梅梅——小刚的孔多塞循环。更重要的是，前面介绍过的投票机制，都无法跳出这个循环。

于是班主任开心地大笔一挥，选了最乖的那个。

事实上，孔多塞循环的出现绝非罕见。05年，维基百科的撰稿人发起了一次孔多塞票制的投票，关于是否应该在词条中称伊丽莎白女王为“殿下”等给出了五种不同的词条撰写方案。然而结果出人意料：方案1打败了方案4，方案4打败了方案3，方案3又打败了方案1. 可见即使投票人数足够，孔多塞循环也是有可能出现的。

于是，有人提出了一种解决方案：如果不存在一个孔多塞赢家的话，那么被击败次数最少的候选人当选。这也是孔多塞投票制在现实生活中主要的应用了。

最后再让我们介绍一种投票机制，以此引入一个经济学概念。

比如，有四名候选人，李雷、韩梅梅、小刚、小明，那么按这个顺序执行的配对消除法会先比较李雷和韩梅梅，胜者再与小刚比较，次轮比较中的胜者再与小明作比较。

这个投票机制的缺陷，也需要一个例子说明：

武藏 韩梅梅 \succ 小明 \succ 小刚 \succ 李雷

小次郎 李雷 \succ 韩梅梅 \succ 小明 \succ 小刚

喵喵 小刚 \succ 李雷 \succ 韩梅梅 \succ 小明

请大家试试李雷—韩梅梅—小刚—小明这个顺序衍生的配对消除法会产生怎么样的结果。

大家会发现，李雷击败了韩梅梅，随后被小刚击败，最终小明击败了小刚当选班长。那么这个结果有什么问题呢？

请思考20秒往下看。

班主任发现了盲点：尽管小明当选了班长，但每个人都喜欢韩梅梅多过小明。因此小明当选这个结果，一定不是对班集体最好的选择。

用经济学术语来说，小明当选班长这个结果不是符合帕累托效率(Pareto Efficiency)的：既然存在一个对所有人而言更好的选择——韩梅梅，那么小明这个选项一定不是最优的。

因此，是否公平我不知道，但这个连连看投票机制一定不是最有效率的。

而中学课本里就没有小明了的原因，大概是他把运气都花在这次选举上了，没考上初中了吧。

阿罗和同时代的一些经济学家、政治学家认为，帕累托效率和独立于无关选项应该是一个好的投票机制应该具有的基本特点。

但是，什么是一个投票机制呢？

不知道大家高中有没有学过数学。如果学过的话，应该还记得什么是一个函数吧。

你向一个函数，比如 f(x) = x^{2020.51} ，输入某些值，它会根据你的输入给你输出一个相对应的值。

你输入 1, 它就会反馈 1^{2020.51} = 1. 你输入 2, 你怎么这么无聊。

一个投票机制就像一个函数一样，它的输入是所有投票者对所有候选人的一个偏好排序（即一个偏好组合），输出的是选举结果。

如果没学过或者不记得的话，不妨想象一下我们每天都非做不可的四件事：吃喝拉撒。每天，我们都在输入各种食粮，输出各种植物的食粮。一个投票机制也是一样，它吃进去的是偏好组合，它拉出来的是选举结果。

注意两点：

对于一个投票机制的输出，大家则会想到两种选择：

自然，第一种机制比第二种更强大，但也更复杂。

这里也要注意一点：不管是上述哪一种机制，我们的输出中都不能有两名候选人持平——必须产生一个严格的排序，或一个唯一的胜者。

因此，多数票制和波达投票制等都不符合我们“投票机制”的定义，因为有可能出现平局。想让它们也成为“投票机制”，我们需要引入一种打破平局的方式，比如按照姓名拼音首字母的先后顺序（埃里克笑了，zzt哭了）。

接下来，再让我们回顾一下帕累托效率和独立于无关选项：

“每个人都赞成的事情，就是社会应该赞成的事情。”

如果每个人都喜欢李雷多过韩梅梅，那么一个好的机制就应该让李雷排在韩梅梅前面。除了韩梅梅，大家应该都觉得很合理吧。

前面看到的绝大部分机制，除了配对消除法，都是帕累托最优的。

这个性质，避免了投票者对无关候选人的偏好排序影响最终的投票结果。

听起来是不是很绕？

让我们换一种说法。

一个偏好组合(Preference Profile)是包含了所有人偏好排序的一个列表：

比如，当投票者只有两个（武藏，小次郎），候选人有三个（李雷，韩梅梅，小刚）的时候，

( 李雷 \succ 韩梅梅 \succ 小刚 , 李雷 \succ 韩梅梅 \succ 小刚 ) 和

( 韩梅梅 \succ 李雷 \succ 小刚 , 小刚 \succ 韩梅梅 \succ 李雷 )

就是两个不同的偏好组合，其中每个括号里前一个值是武藏的偏好排序，第二个值是小次郎的偏好排序。

假设我们现在有一个独立于无关选项的社会福利函数，任意一个偏好组合 P 和任意两个候选人（比如李雷、韩梅梅）。我们在这个社会福利函数中输入 P , 得到了一个总排序，其中李雷排在韩梅梅前面。

这时候，有一些投票者改变了主意，汇报了不一样的偏好排序，于是我们得到了一个新的偏好组合。但是在这个新的偏好组合中，每个人的偏好排序中李雷和韩梅梅的相对位置与原先一致——即原来把李雷排在韩梅梅前面的投票者，在改变主意后仍然把李雷排在韩梅梅前面；原来把李雷排在韩梅梅后面的投票者，改变主意后仍把李雷排在韩梅梅后面。

那么我们向这个社会福利函数输入新的偏好组合得到的总排序中，李雷仍然在韩梅梅前面。

接下来这一小部分，是上面提到的所有概念的数学模型化，不感兴趣的朋友们可以跳过这一段。

再模型化我们所关注的两条性质：

民主社会的初衷，是把做决定的权力从少数人手中转移到多数人手中，让最终的决定反映多数人的意愿。在一个民主的三年八班里，哪怕班主任喜欢李雷，也只能尊重大多数人的意愿选择喜欢一边灌水一边放水、没坐一会公交车就下车步行走5公里到学校的小明。

民主社会是独裁的反义词。

什么是独裁呢？在这个例子中，独裁指存在一个可以完全操纵投票结果的投票者。很明显，这样的一个投票者让所谓的民主投票失去了意义。

如果你关心数学意义的话，

对一个民主社会而言，非独裁是再基本不过的要求了。

让我们假设在凤南小学三年八班中有两个班级恶霸，这次班长选举完全由他俩说了算，剩下295名学生的话没有任何分量。很明显，没有任何人会觉得这是一个民主的机制（除了这俩恶霸：“我还要和另一个人商量，这多民主啊！”）但这样的投票机制仍然符合我们“非独裁”的条件。

在投票理论中，一个更强也更符合“民主”一词的条件是匿名性。

以下这个数学意义是我自己写的，应该没错：

换言之，投票者们是匿名投票的：计票者只能看到选票，看不到每张选票是谁投的。不管是小红投了韩梅梅一票，还是上周以作文题为“我的区长父亲”的优秀作文获得全区征文大赛第一名的袁华投了韩梅梅一票，都不会有任何区别。

很明显，匿名性蕴含着非独裁（如果一个投票机制具有匿名性，那么它一定是非独裁的，只有一个投票者不算）。因此很多时候，我们只需考虑范围更宽的非独裁性就够了。

前方高能!!!

1951年，阿罗证明了阿罗不可能定理：

证明不算极其复杂，但思路很奇妙。我把证明的大致步骤放在这里，有兴趣的朋友们可以试着自己证一下（我在有步骤提示的条件下仍花了三个小时），或者必应一下它的完整证明。

除此之外，印度经济学家阿马蒂亚森给出了一个十分绝妙的证明，但这里的空间太小写不下（他的做法还需要给两个定义，我懒）

我不知道大家看到这的时候是什么心情。

我猜大概率是内心毫无波澜——哦，所以呢，不存在完美的投票机制的事实可以让我们在下一次大选中击败懂王吗？

确实不能，但我第一次看到的时候也确实很震惊。数学上，我们只引入了两个很基本、自然的假设，可却推出了一个深刻的结果：当这两个假设都被满足的时候，这样看似民主又有效率的社会福利函数，不过是独裁者的障眼法罢了。

既然一个好的民主投票机制一定是独裁的，那么独裁社会就至少不差于民主社会。

在阿罗的眼里，一个完美的投票机制，大抵是不存在的。

讨论一个数学命题的经济学意义并非笔者擅长的事情（我比较擅长炉石），因此本章整合了一些印度经济学家阿马蒂亚.森(Amartya Sen)及美国经济学家埃里克.马斯金(Eric Maskin)的观点。

这一章的内容比较主观，我会把重点放在观点分析而非段子上。

在讲第一个观点前，要给大家科普一个经济学小知识。

在经济学中，有一个十分重要的概念叫做“效用”(Utility). 效用可以大致理解为满意度，做一件事情、获得一件物品都会带给一个人特定的效用。

效用可以是负的，想象一下在吃饭的时候吃到植物的食...算了算了。

效用存在的意义之一，是用来比较不同选项的优劣。它分为两种：基数效用(Cardinal Utility)和序数效用(Ordinal Utility).

前者的意思是，我们可以用数值来表示效用：在此时此刻吃一个糯米鸡可以给我带来5个单位的效用，吃一个烧卖可以给我带来2个单位的效用，以及还有一个例子，你们知道我想说什么。

后者则表示我们只能比较不同食物带来的效用孰高孰低，比如糯米鸡 \succ 烧卖 \succ ... 至于糯米鸡给我带来的效用比烧卖高多少，序数效用模型中是无法体现的。

基数效用比较的是绝对大小，序数效用比较的是相对大小。

我们的投票机制中考虑的是序数效用。因此，我们不会考虑，也没法考虑，“选李雷和韩梅梅给武藏带来的效用差异与选小刚和小明给小次郎带来的效用差异哪个差的更多？”

再让我们回忆一下帕累托最优的定义：

注意到我们考虑的范围是“所有投票者”。这意味着，哪怕297个人里有296个人喜欢李雷多过韩梅梅，我们的机制也可以允许我们选择韩梅梅（仔细想想，这并不违背PE和IIA）。

我们可以看出，在阿罗的模型中，我们没法进行人际间的效用比较(Interpersonal Utility Comparisons)，也没法对不同人所得到的效用进行加总。可这是否适用于现实社会，是存在疑问的。比如，布什当选总统这件事情给一名狂热的左翼分子带来的负效用，真的和给一个对政治漠不关心的人带来的效用大小一样吗？

我们可能只是选错了模型。事实上，阿马蒂亚森说，当我们允许人际间效用比较时，在福利经济学上会得到不少正面的结果。

第二，有人要问了，既然这么完美的社会福利函数不存在，那如果我们降低一点要求，不再需要选择一个候选人的总排序，只要选出一个胜者就好了（即考虑社会选择函数，）那情况还会这么悲观吗？

注意到帕累托效率和独立于无关选项不再适用于社会选择函数，它们被弱帕累托效率和单调性这两个条件替代了。我们不会展开讨论这两个条件。

答案是：是的，我们仍会得到一个悲观的结果：

第三，

阿罗不可能定理其实有两个暗藏的条件：1. 允许任何人有任意的偏好；2. 对于任意的偏好组合，我们都要选出一个严格的偏好排序。阿罗不可能定理只是说，符合这两个条件和定理中三个条件的投票不存在。

但是，第一个条件在理论上很完美，在现实中却有可能出问题。比如，没有什么人会喜欢植物的食粮多过虾饺吧。

再回到那个美国大选的例子。纳德尔是一个偏左翼的候选人，布什是一个偏右翼的候选人，而戈尔则介于两者之间。因此，喜欢纳德尔的投票者也更可能喜欢戈尔。

也因此，纳德尔 \succ 布什 \succ 戈尔 和 布什 \succ 纳德尔 \succ 戈尔这样的偏好，本应是不太常见的。

在经济学中，有一个词叫双峰偏好(Double-peaked preferences).

想象两座高峰和中间连接两者的一道峡谷。

对 i 来说， o_1 和 o_3 就是山峰， o_2 就是峡谷。

与之相对的是单峰偏好(Single-peaked preferences)：从一名投票者最喜爱的候选人开始向左或者向右，该投票者一定是越来越不满意的。

比如在这个例子中纳德尔 \succ 布什 \succ 戈尔 和 布什 \succ 纳德尔 \succ 戈尔就是双峰偏好，其余都是单峰偏好。

当所有投票者的偏好都是单峰且投票者数量为奇数（避免平局）时，孔多塞投票制性质特别好：它是一个符合弱帕累托效率、单调性的非独裁社会选择函数。

这一条道路，终于出现了一点光芒。

这是我写过最难写的一篇笔记，不仅因为例子太多，还因为各界对于阿罗不可能定理的主观评判太多，作为一个数学系学生的我确实不太擅长处理（没有黑数学系的意思，我也认识喜欢对社会现象、政治体制等进行深度思考的数学系朋友，但数学系的学生相对经济系、政治系学生而言不那么关注这些是客观事实）。我看了一篇讨论人际间效用比较的哲学文章并写了一大长串归纳，但最后还是决定删掉，毕竟我完全没有学过哲学，而且这也不是自己这篇文章应该关注的重点。

这篇文章真的很长，字数达到了一万字，花了笔者几个晚上。但笔者也在写作的过程中查询了许多资料，收获了很多东西。希望有耐心看完的读者们也能有所收获，比如了解到各种常见的投票机制，及获得在别人讨论民主体制时甩出这个定理来装逼的技能。

希望大家喜欢。

Game Theory II, Coursera, Stanford University

Maskin, "Arrow's impossibility theorem: Where do we go from here?"

Sen, "Arrow and the Impossibility Theorem"

Reilly, "Social Choice in the South Seas: Electoral Innovation and the Borda Count in the Pacific Island Countries"