我在知乎看到一个答案[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