我在知乎看到一个答案[1]讲阿罗不可能性定理（Arrow’s impossibility theorem），但是讲得不够科普，所以有人疑惑发问。我写了个评论回答他，但是被和谐叻。搜了一下阿罗不可能性定理的“科普向”文章，乱七八糟的[2][3][4]。所以把我写的评论贴过来好了，刚好这博客都要长草了。
资质（……）：上过唐平中先生的 Game Theory 课；唐在 2009 年给出了阿罗不可能性定理的巧妙的又一个证明[5]（上面的知乎答案就是讲的这个证明），并在 Game Theory 的一次课上详解了该 paper。
肯尼斯·约瑟夫·阿罗（Kenneth Joseph Arrow）于2017年2月21日去世，R.I.P.
评论：
24 天前
外行人看不太懂……怎么就……社会福利……独裁者………可以解释一下吗………
我：
Abstract: 社会福利函数指的是这样的选举制度：选票和选举结果都是候选人集合上的全序。定义一个投票人 i 是独裁者，如果无论其他投票人怎样投票，社会福利函数输出的序总和 i 写在选票上的序一样。如果一个社会福利函数可以出现独裁者，那么说这个社会福利函数是 dictatorial 的。阿罗不可能定理说，如果候选人数 >=3，那么任何 unanimous 的、IIA 的社会福利函数都必然是 dictatorial 的。
Full text:
这里所说的“选举”是：n 个投票人，m 个候选人；每个投票人的选票是 m 个候选人上的一个全序（而非像选区级人大代表那样“支持一个或部分候选人”）。
选举，按照要选出啥结果，（至少）有两种分类：
通过社会选择函数（social choice function）来选出一个获胜者，比如选总统；
通过社会福利函数（social welfare function）来决定候选人上的一个全序，比如25个政治局委员投票来给七长老排名（什么鬼）。
一个选举机制就是一个社会福利函数 W : L^n -> L 或一个社会选择函数 C : L^n -> O，其中 O 为候选人集合，L 为 O 上的全序的集合。选举机制设计，就是设计 W 或 C，关心如何综合大家意见、把 n 个全序变成一个全序（或一个点）。
注意到社会福利函数的值域也是候选人上的全序。定义一个投票人 i 是社会福利函数 W 里的独裁者，如果无论其他投票人怎样投票，W 输出的序总是和 i 写在选票上的序一样。
如果一个社会福利函数可以出现独裁者，那么说这个社会福利函数是 dictatorial 的。一个平凡的例子是，“总是输出第 301 号投票人的序”。
阿罗不可能定理说，如果候选人数 >=3，那么任何 unanimous 的、IIA 的社会福利函数都必然是 dictatorial 的。
Unanimous 和 IIA 的定义可以看唐平中的文章[5]的 2. Arrow’s theorem 这一节的开头，就半页 :)
[1] https://www.zhihu.com/question/24239308/answer/112972302
[2] https://www.zhihu.com/question/20324062/answer/148764648
[3] https://www.zhihu.com/question/20324062/answer/31731351
[4] http://www.guokr.com/question/452481/
[5] Tang P, Lin F. Computer-aided proofs of Arrow's and other impossibility theorems[J]. Artificial Intelligence, 2009, 173(11): 1041-1053. http://www.cs.cmu.edu/~kenshin/arrow_aij.pdf
