2012年8月12日

投票操纵可以避免吗?——从达米特说起

2011 年 12 月 26 日,以研究毛泽东而蜚声海外的中国历史学高华不幸去世(你可能没听说过这个名字,但你一定听说过《红太阳是怎样升起的》这本书)。一天后,远在地球另一端的、以诠释弗雷格而闻名于世的英国哲学家达米特(Michel Dummett)撒手人寰。

在分析哲学界,达米特是当之无愧的泰斗级人物。一个念分析哲学的人如果不知道达米特的大名,就像一个研究毛泽东的人不知道高华一样,那简直等于进了一间黑屋而没有摸到大厅的开关,或者干脆连进门的钥匙都没摸到。

你一定想不到的是,达米特这样一个绅士级别的、晚年还获得了爵士称号的老学究,竟然是塔罗牌的资深玩家。作为世界扑克协会的元老级成员,他写过 8 本关于塔罗牌的书,几乎和他的哲学著作一样多。不过人家毕竟还是老学究,虽富英式幽默,但绝不八卦,对于塔罗牌最为人所熟知的、也最富娱乐性的占卜功能,他老人家不屑一顾。在他写的 8 本塔罗牌的书里,有一多半都是关于塔罗牌历史的。通过对塔罗牌前世今生的仔细考察,他发现塔罗牌的占卜玩法是 18 世纪才出现的,而在此之前,塔罗牌和我们通常扑克牌的玩法差不多,都属于竞技策略型的游戏。他有一本书的名字就叫:《塔罗牌的 12 种玩法》。在他已是学界泰斗时,达米特还写了一本为考生和其他人准备的《语法与写作指南》。这一看上去有点掉价的的举动,其实出自达米特深切的人文关怀,他希望借此能改善普罗大众的文字修养,减少文盲的存在。

达米特的第一本重要著作、也是他的成名作——《弗雷格:语言哲学》(Frege: Philosophy of Language)直到他 48 岁时才出版。相比康德 57 岁才发表连法国贵妇都用来装点门面(用现在的话叫装B)的《纯粹理性批判》,达米特似乎还不算晚,但康德在 31 岁就发表了提出星云假说的《自然通史与天体论》。这样比起来,达米特是真正的大器晚成。那么,年轻时的达米特都干啥了呢? 玩扑克牌去了吗?或许吧。不过那些关于塔罗牌的书其实都是后来才写的。年轻时的达米特在干一件吃力不讨好的事:反抗种族主义。鉴于种族主义当时在英国大行其道(这次的伦敦奥运会大概让人对此并不陌生),他认为做愤青比做学者更有价值。直到达米特认为自己在反种族主义事业中已经做不出什么贡献了,他才开始投身哲学。弗雷格成了他的首要研究对象。而让他万分震惊的是,弗雷格这个被认为是绝对理性的人,竟然是一个极端的种族主义者。这件事让他感到,关于人类的某些事情似乎还是不知为妙。

如果青年达米特只是个愤青,那就太对不住他牛津大学的博士头衔了。所以在愤青之余,青年达米特还干了一件事:研究怎么投票(貌似离愤青也不太远)。尽管他的第一本关于投票理论的书直到 1984 年才出版(在这本书中,达米特设计了一种全新的投票方法:比例博尔达投票法。),但早在上世纪五、六十年代,达米特就和 Robin Farquharson 一起合写过关于投票理论的重要文章。今天很少有人知道,投票理论中一个最重要的不可能性定理——Gibbard-Satterthwaite 定理,其实差一点就是达米特的囊中之物,它本该叫 Dummett-Farquharson 定理。事实上,这个定理的内容正是由他们两人一起提出的。

那么,这个和达米特相提并论的、名字听起来像国际通用骂人语的 Farquharson 又是何许人也呢?简单来说,他是一个才华横溢的、英年早逝的、几乎被后人遗忘的、遭上天嫉妒而疯掉的、命运极其悲惨的南非天才。按照 Dummett 的看法,如果不是因为遭受精神病的折磨,在社会选择领域,他原本可以成为和阿罗并驾齐驱的奠基者。

Farquharson 的求学经历和阿马蒂亚·森有点类似,他先在国内读完本科,然后又去英国牛津大学拿了一个学士学位。在牛津读本科期间,他对美国参议院的选举产生了浓厚兴趣。让他惊讶的是,选举结果通常是违背大部分人意愿的。当同一党派的参选人过多,导致选票分散到该党派不同竞选者身上时,简单的多数投票法就很容易造成这种后果。下面是众多真实案例中的一个:

1971 年,美国康乃尔大学所在地举行市长选举,共有 2 名民主党人和 3 名共和党人参选。最后获胜的是一位民主党人,但他只得了 29.1% 的选票,与之最接近的一位共和党人以 28.9% 的微弱劣势败北。最糟糕的是,3 名共和党人一共获得了 60.7% 的选票,换言之,在该市大部分人都支持共和党人的情况下,最后竟然让一个民主党人当选了。

可以预见的是,如果共和党少一个人参选,那么很可能当选的就是共和党人而不是民主党人。另一个与之等价的方法是,某些支持共和党的选民不是把票投给自己最喜欢的那个共和党人,而是投给那个人气最旺的共和党人,这样就会让某位共和党人当选。尽管这个结果不是他们最满意的,但至少要比让一个民主党人当选好得多。这种通过不诚实的投票,而获得让自己更满意的结果的行为叫做策略操纵。很显然,能够进行策略操纵的投票规则是不令人满意的,因为这会让诚实者吃亏而让欺骗者得利。同时,如果策略操纵是有利可图的,那么投票结果就很难反映人们的真实意愿。因此,如何避免策略操纵,成为投票理论中一个极为迫切的问题。

现代投票理论,以及更一般的社会选择理论虽然诞生于 1950 年代,但其真正繁荣是在 1970 年代。在此之前,除了阿罗外,Farquharson 几乎没有任何现代文献可以借鉴。而让 Farquharson 吃惊的是,阿罗竟然完全回避了投票中的策略操纵问题。在既无名师指导,也几乎没有人可以交流的情况下(当时牛津大学只有他的导师支持他研究这玩意,其他人都不感兴趣),Farquharson 只能从其他渠道获取灵感。他一方面将研究的触角伸向更久远的历史,找到了继孔多塞和博尔达之后的又一位研究过投票理论的重要人物:Charles Dodgson(因为《爱丽丝漫游奇境》这本儿童小说,他的笔名 Lewis Carrol 更为人熟知),另一方面将目光投向了刚兴起不久的、由摩根斯坦和冯·诺伊曼开创的博弈论。这两方面的探索都给了他重要启发。

1958年,Farquharson 完成了题为《投票理论》(Theory of Voting)的博士论文。这篇继阿罗之后填补空白的重要论文拖了 10 年之久都未能出版。原因颇让人纠结: Farquharson 坚持要求他的书用彩色印刷,而以当时的技术和成本,没有哪家出版社愿意这么干。最终,直到 1969年,耶鲁大学出版社以黑、白、红三色印刷出版了 Farquharson 的杰作。甫一出版,这本书就获得了美国艺术与科学院颁发的年度社会科学著作奖。

1961年,Farquharson 与达米特在经济学顶级杂志 Economitrica 共同署名发表了一篇重要文章:Stability of Voting。在这篇文章中,他们将 Ducan Black 的单峰偏好定理的条件弱化了。Ducan Black 的定理指出了:在什么样的条件下,民主投票制是没有问题的(这就是那个阿罗最初认为是自己的全新发现,后来在一本杂志中得知已被人抢先证明了的结果),而 Farquharson 与达米特的工作则相当于给民主投票制划出了更大的可以合理使用的范围。尽管达米特谦虚的表示这篇论文只有最后两三页才是他写的,但达米特的贡献却是实质性的。Farquhason 虽然猜想到了 Ducan Black 的定理条件可以弱化,但未能证明,于是求助于达米特。证明最终是由达米特完成的。同样是在这篇文章中,他们提出了防止策略操纵是不可能的这一猜想,更准确的表述是,在竞选者超过 2 个的情况下,如果投票者只对竞选者给出线性排序(不是打分),那么不存在一种投票规则可以同时满足以下 4 个条件:

  1. 决断性:即投票结果只能选出一个人当选,不能同时选出多个人当选。
  2. 完满性(surjective):即每个竞选者都有当选的可能,不能出现无论选民如何投票,有人总是不能当选的情况。
  3. 非独裁性:即投票结果不能由一个人说了算。
  4. 防策略操纵性:即没有人可以通过改变自己的投票(在其他人保持不变的情况下)而获得更有利于自己的结果。

Farquharson 和达米特当时都没有去证明这个猜想。前者是没有条件从事学术研究了,他在 1950 年代中期就开始受狂躁抑郁症的折磨。1955 年的一个晚上,就在牛津大学的评审委员们投票决定给 Farquharson 一个职位时,Farquharson 给牛津大学打来一个电话,声称自己有一个重大发现,此发现可以解决数学、数理逻辑、经济学以及投票理论中的诸多难题,并让听电话的人找纸和笔记下来。这个电话让学校意识到 Farquharson 已经精神失常,最终没有给他这个职位。自此以后,Farquharson 再也没有获得稳定的大学职位。此后他过了一段嬉皮士的生活,期间一度沦为街头流浪汉。1973 年,年仅 43 岁的他被一起火灾责任事故殃及而烧成重伤,送至医院后抢救无效死亡,一个天才就这样悲催的离开了人世。

那么达米特又为何没有去证明自己提出的猜想呢?原因是他错误的估计了证明的难度。直到若干年后,当他准备写一本关于投票理论的书而向阿马蒂亚·森索要相关文献时,才得知这个猜想已被证明,而且被证明了两次(分别被 Allan Gibbard 和 Mark Satterthwaite 于 1973 年和 1975 年独立证明)。这让达米特大受刺激,于是决定在不看已有证明的情况下单挑,结果达米特一口气给出了 3 种不同的证明。直到晚年在一篇纪念 Farquharson 的文章中,达米特还对此耿耿于怀。是啊,早知道证明这么简单,当初动手证一下就没 Gibbard 和 Satterthwaite 两人什么事儿了。对我们这些普通人来说,如此一来至少有一个好处,那就是这个定理的名字不会那么难记了。

2012年8月10日

将博客导入到 Blogger 的问题及其非完美解决

Blogger 的设置中虽然有从其他博客导入的功能,但每次都会提示服务器错误之类。网上的很多办法都不管用,最后找到一个可以勉强解决问题的方案。

如果你是想从 wordpress.com 导入到 blogger,则先在 wordpress 中导出你的文章和评论,然后访问这里,进行转换,最后再利用 blogger 的导入功能。导入后文章会处于草稿状态,不会直接发布,需要手动发布。由于 blogger 有防垃圾功能,好像一次导入文章数量不能超过 50 篇,我的文章数量恰好不够 50 篇,所以没出现问题。如果有问题,则需要对 xml 文件进行分割,分割方法请自行 google。

如果想从其他博客搬家至 blogger,则不能直接利用上面的转换方法(我试过博客园未成功),一个或许可行的方法是先将其导入到 wordpress,然后再从 wordpress 导入到 blogger。

Blogger 的其他功能都很赞,其自定义模板的功能既足够灵活又容易上手。但是导入功能做的这么差实在是不应该,这会阻碍很多人将博客搬至这里。

利用 MathJax 在博客中写数学公式

终于找到了比较完美的在博客中支持 LaTeX 的方案。wordpress.com 虽然也支持 LaTeX,但是有 2 个缺点:
  1. wordpress.com 是利用 wordpress 的wp latex 插件支持 latex 的,必须使用 \$latex \$ 这样的格式,而不能直接使用 \$ \$ 来输入公式,这使得无法直接利用在其他地方已写好的 tex 源码;
  2. 生成的公式是图片格式的,不支持矢量缩放和拷贝。
今天发现了一个在线生成 LaTeX 的利器:MathaJax,它支持多种数学公式语言,其中也包括 LaTeX,并且生成的公式支持矢量缩放和拷贝(拷贝方法参见这里)。但要在博客上获得 MathJax 的支持,必须要求博客空间提供自定义模板的功能,而大部分比较 popular 的国内免费博客空间,如新浪、网易、百度等都不提供该功能。下面提供两种解决方案:

方案一:墙内免费博客空间博客园支持自定义模板。当你在博客园开通博客后,在博客管理的“设置”页面的“页首Html代码”处拷入下面的代码即可:

<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
  inlineMath: [['$','$'], ['\\(','\\)']],
  processEscapes: true
  },
TeX: {
            equationNumbers: {
                autoNumber: ["AMS"],
                useLabelIds: true
            }
        },
        "HTML-CSS": {
            linebreaks: {
                automatic: true
            },
            scale: 85
        },
        SVG: {
            linebreaks: {
                automatic: true
            }
        }
});
</script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
其中的 scale: 85 是指公式大小的缩放比例,你可以根据需要进行调整。这样设置后你不但可以直接像在 LaTeX 中那样写行内公式和行间公式,而且还可以使用 LaTeX 的公式自动编号和引用的功能。不过目前还不支持定理环境。

这里是一个测试页面,可以看到生成的公式还是非常漂亮的。这里是我翻译和稍作改写的阿罗不可能性定理的证明。在 Ubuntu 下的 Chrome 浏览器、Firefox 浏览器和 Windows 下的 Firefox 浏览器下测试均显示正常,但在 IE 浏览器中公式下标会有显示不完整的情况,不知是不是我的个别现象,大家也帮忙测试一下。

方案二:墙外博客空间 www.blogger.com 是 google 提供的博客服务,具有较强的可定制性,开通后在自定义模板的 html 代码中找到 </head>,在这之前填入上面的代码即可。

利用 MathJax 生成数学公式仍然有两个缺点:
  1. 生成公式的速度较慢;
  2. 在 RSS 阅读器中只能显示公式的源码,必须点击文章的原始链接才能看到公式,这个在某种意义上也可以看作是优点,因为方便了代码的重用。
本文中的代码参考了http://zhiqiang.org/blog/it/mathjax-make-mathematics-beautiful.html,特此致谢!关于更多对 MathJax 的定制,请参考 MathJax 的帮助文档。

2012年8月9日

利用 ScribeFire 扩展“一稿多投”

这里的“一稿多投”是指,你在编辑器写好文章后一次性发布到你的多个博客站点,而不必采用复制、粘贴这样的低级方法。这对于有多个博客需要同时打理的作者来说是很现实的需求,特别是在网络审查作威作福的情况下,同时在墙外建一个博客备份是很有必要的。这里推荐的 ScribeFire 扩展可以帮你解决这个问题。

ScribeFire 扩展有 Firefox、Chrome、Safari、Opera 各种版本(我用的是 Chrome 版,Firefox 版功能最强),你可以通过这几种浏览器登录 ScribeFire 后点击 Install Now 安装。

安装后你需要将你的博客地址以及用户名、密码等信息添加进去(Chrome 版请点击左上角的“添加新博客”)。不同的博客站点设置有所不同。

最简单的是其中预置的一些比较知名的博客站点,如 blogger(被墙了)和 wordpress(也被墙了),这些你只要输入你的博客网址后,点“下一步”,然后输入你博客的用户名和密码即可。

其他的设置则要稍微麻烦一点,需要手工输入 API 地址。网易和新浪博客的 API 地址如下:
  • 网易:http://os.blog.163.com/api/xmlrpc/metaweblog/
  • 新浪:http://upload.move.blog.sina.com.cn/blog_rebuild/blog/xmlrpc.php
博客园(cnblogs)的设置:输入博客网址后,选择博客类型为 MetaWebblog,输入 API 地址,该地址可以在博客园的“管理-设置”页面的最下面找到,一般形如:http://www.cnblogs.com/用户名/services/metaweblog.aspx。另一种方法是在输入网址时填入:http://用户名.cnblogs.com(而不是你的博客的真实网址:http://www.cnblogs.com/用户名),然后点击下一步,软件会自动填写好 API 地址。

利用 micolog 在 GAE 搭建的博客的设置请参考这里,注意将相应位置改成你自己的 id,其中的登录用户名和密码需要预先在你的博客中设置。

遗憾的是我没有找到如何设置发布到 diandian 博客的方法,但貌似有人在 diandian 也测试成功了。

本文参考了以下网页,特此致谢:

2012年8月7日

测试 LaTeX

This is an array.

\begin{array}{cc}
a & b \\
c & d
\end{array}

In equation \eqref{eq:sample}, we find the value of an interesting integral:
\begin{equation}
\int_0^\infty \frac{x^3}{e^x-1}\,dx = \frac{\pi^4}{15} \label{eq:sample}
\end{equation}

2012年8月5日

阿罗不可能性定理的证明

首先引入一些必要的记号和定义。令有穷集 $N=\{1,\ldots,n\}$ 为 $n$ 个投票者构成的集合,令 $X$ 为所有备选项构成的集合,每个投票者 $i$ 对 $X$ 的排序记作 $\succeq_i$,所有投票者对 $X$ 的一组排序 $(\succeq_1,\ldots,\succeq_n)$ 记作 $\vec{\succeq}$,称为一个排序组合。一个投票规则 $V$ 的作用就是,输入一个排序组合 $\vec{\succeq}$,则返回一个社会排序 $V(\vec{\succeq})$。
阿罗意义上的投票规则要求,每个投票者的排序 $\succeq_i$ 和最后得到的社会排序 $\succeq_V$ 都是弱序,即要满足下面两个性质:
  1. 传递性:对任意 $x,y,z\in X$,若 $x\succeq y$ 且 $y\succeq z$,则 $x\succeq z$;
  2. 完全性:对任意 $x,y\in X$,要么 $x\succeq y$,要么 $y\succeq x$(由完全性知,弱序也满足自反性,即对任意 $x\in X$,$x\succeq x$)。
我们称满足这些条件的投票规则为阿罗投票规则(阿罗称之为社会福利函数)。
任给弱序 $\succeq$,我们用 $\succ$ 表示其中的严格排序,即 $x\succ y$ 当且仅当 $x\succeq y$ 且并非 $y\succeq x$。我们用 $x\succeq_{V}y$ 表示,在社会排序 $V(\vec{\succeq})$ 中 $x$ 至少和 $y$ 一样好。类似的,$x\succ_V y$ 表示,在社会排序 $V(\vec{\succeq})$ 中 $x$ 严格好于 $y$。
一个阿罗投票规则 $V$ 是独裁的,意指存在某个独裁者 $i\in N$,使得对任意排序组合 $\vec{\succeq}$,对任意 $x,y\in X$,只要 $x\succ_i y$,则 $x\succ_V y$,即社会排序 $\succeq_V$ 中的严格排序完全等同于独裁者 $i$ 的严格排序。现在严格表述阿罗不可能性定理如下:
定理(阿罗不可能性定理):若 $X$ 中的备选项超过两个,则不存在非独裁的阿罗投票规则 $V$ 能同时满足下面两个条件:
帕累托条件(即一致同意性):对任意排序组合 $\vec{\succeq}$,对任意备选项 $x,y\in X$,若 $N$ 中投票者一致认为 $x$ 严格好于 $y$,则在社会排序 $\succeq_V$ 中也有 $x$ 严格好于 $y$;
独立性条件:对任意排序组合 $\vec{\succeq},\vec{\succeq'}$,对任意备选项 $x,y\in X$,若排序组合 $\vec{\succeq}$ 与 $\vec{\succeq'}$ 关于 $x,y$ 的个体排序相同,则 $\succeq_V$ 和 $\succeq'_V$ 关于 $x,y$ 的社会排序也相同。
换言之,在备选项超过两个的情况下,同时满足帕累托条件和独立性条件的阿罗投票规则一定是独裁的。为了证明这个定理,我们先引入两个重要概念。
定义 1(决定性联盟):给定投票规则 $V$,称非空集 $G\subseteq N$ 在 $V$ 下关于 $(x,y)$ 是决定的,若对任意排序组合 $\vec{\succeq}$,只要 $G$ 中的投票者一致认为 $x$ 严格好于 $y$,则社会排序 $\vec{\succeq}$ 中也有 $x$ 严格好于 $y$;称 $G$ 是 $V$ 的决定性联盟,若 $G$ 在 $V$ 下关于所有 $(x,y)$ 都是决定的。
易见,若单点集 $\{i\}$ 是 $V$ 的决定性联盟,则 $i$ 是 $V$ 的独裁者。下面的证明本质上源自 1998 年诺贝尔经济学奖得主 Amartya Sen,他将阿罗的原始证明整理得更清晰了(阿罗的原始证明难以看出独立性条件在证明中的使用)。证明思路如下:
  1. 根据定义,若 $V$ 满足帕累托条件,则 $N$ 是 $V$ 的决定性联盟。
  2. 先证明关于决定性联盟的收缩引理:若非单点集 $G$ 是 $V$ 的决定性联盟,则 $G$ 的某个真子集 $G'$ 也是 $V$ 的决定性联盟。
  3. 由于 $N$ 是有穷的,根据 1、2 归纳可得,存在由一个人构成的决定性联盟,即独裁者。
该证明包含了帕累托条件的明确使用,而独立性条件的使用则暗藏在收缩引理的证明中。为了证明收缩引理,需要引入另一个概念:弱决定性联盟。
定义 2(弱决定性联盟):给定投票规则 $V$,称非空集 $G\subseteq N$ 在 $V$ 下关于 $(x,y)$ 是弱决定的,若对任意排序组合 $\vec{\succeq}$,只要 $G$ 中的成员一致认为 $x$ 严格好于 $y$,且 $G$ 外的成员(若有的话)一致认为 $y$ 严格好于 $x$,则社会排序 $\succeq_V$ 中也有 $x$ 严格好于 $y$。
显然,若 $G$ 在 $V$ 下关于 $(x,y)$ 的决定的,则 $G$ 也在 $V$ 下关于 $(x,y)$ 也是弱决定的。反之是否成立呢?如果 $V$ 满足帕累托条件和独立性条件,则反过来不仅成立,而且我们还有如下更强的结论:
引理 1(扩展引理):设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。若 $G$ 在 $V$ 下关于 $(a,b)$ 是弱决定的,则 $G$ 是 $V$ 的决定性联盟(即 $G$ 在 $V$ 下关于任意 $(x,y)$ 都是决定的)。
这个结论有些令人意外,其证明需要使用独立性条件。
证明:设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。设 $G$ 在 $V$ 关于 $(a,b)$ 是弱决定的,任给 $(x,y)$,我们证明 $G$ 在 $V$ 下关于 $(x,y)$ 是决定的。不妨设 $x,y$ 与 $a,b$ 均不相同(相同的情况类似可证)。任给排序组合 $\vec{\succeq}$,使得 $G$ 中所有成员一致认为 $x$ 严格好于 $y$,只需证 $x\succ_V y$。考虑如下的排序组合 $\vec{\succeq'}$,其中
  • $G$ 中的投票者认为:$x\succ' a\succ' b\succ' y$
  • $G$ 之外的投票者认为:$x\succ' a$,$b\succ' y$,$b\succ' a$,且对 $x,y$ 的排序与 $\vec{\succeq}$ 保持一致
易见,$G$ 中成员一致认为 $a$ 严格好于 $b$,且 $G$ 外的成员一致认为 $b$ 严格好于 $a$,由于 $G$ 在 $V$ 下关于 $(a,b)$ 是弱决定的,故 $a\succ'_{V}b$。由于在 $\vec{\succeq'}$ 中所有人都认为 $x$ 严格好于 $a$,$b$ 严格好于 $y$,据帕累托条件有,$x\succ'_{V}a$,$b\succ'_V y$,据社会排序的传递性可得,$x\succ'_V y$。注意到 $\vec{\succeq}$ 与 $\vec{\succeq}$ 关于 $x,y$ 的个体排序是一样的,由独立性条件有,$x\succ_V y$,证毕。
有了扩展引理,现在我们可以证明下面的收缩引理了。
引理 2(收缩引理):设 $V$ 是满足帕累托条件和独立性条件的阿罗投票规则。若非单点集 $G$ 是 $V$ 的决定性联盟,则 $G$ 的某个真子集 $G'$ 也是 $V$ 的决定性联盟。
证明:由于 $G$ 是非单点集,故可将 $G$ 划分成两个不相交的非空子集 $G_{1}$ 和 $G_{2}$。考虑满足如下条件的排序组合 $\vec{\succeq}$(由于备选项超过两个,故可以做到):
  • $G_{1}$ 中的投票者认为:$x\succ y\succ z$;
  • $G_{2}$ 中的投票者认为:$y\succ z\succ x$;
  • $G$ 之外的投票者(如果有的话)认为:$z\succ x\succ y$。
注意到 $G$ 中所有投票者都认为 $y$ 严格好于 $z$,由 $G$ 是 $V$ 的决定性联盟可得,$y\succ_V z$。现在分别考虑两种情况(由于 $\succeq_V$ 是完全的,故有且仅有两种情况):
  1. $x\succ_{V}z$。任给排序组合 $\vec{\succeq'}$,使得 $G_{1}$ 中的成员在 $\vec{\succeq'}$ 中一致认为 $x$ 严格好于 $z$,且 $G_1$ 外的成员一致认为 $z$ 严格好于 $x$,此时 $\vec{\succeq'}$ 和 $\vec{\succeq}$ 关于 $x,z$ 的个体排序相同,故由独立性条件可得,$x\succ'_{V}z$,这意味着 $G_{1}$ 在 $V$ 下关于 $(x,z)$ 是弱决定的,再据扩展引理有,$G_{1}$ 是 $V$ 的决定性联盟。
  2. $z\succeq_{V}x$。此时,据 $\succeq_{V}$ 的传递性有 $y\succ_{V}x$。同理于情况 1 可证,$G_{2}$ 是 $V$ 的决定性联盟。
综合 1、2,故总有 $G$ 的真子集是决定性联盟,证毕!

2012年8月3日

侠之大者:阿马蒂亚·森与自由悖论

“如果你因失去太阳而流泪,那么你也将失去群星”,这句国人耳熟能详的名人名言出自印度诗人泰戈尔的《飞鸟集》。泰戈尔不仅以诗著名,他还因不满僵化的英国殖民教育,创办了自己的学校。这位第一个获得诺贝尔文学奖的亚洲人大概不会料到,他的学校会走出亚洲第一个(也是迄今唯一的)诺贝尔经济学奖得主,而这位幸运儿的大名正是泰戈尔亲自拟定的,他的名字叫阿马蒂亚·森(Amartya Sen)。

少年英雄

与作为倒闭银行家的儿子阿罗不同,森出生于书香门第,父亲和外公都是大学教授。从小混迹于茵茵校园,除了投身学术,森想不出还有第二条路可以走。他在泰戈尔创办的学校里读完小学和中学,自由驰骋于梵文、数学和物理之间。9 岁时他目睹了 1943 年的孟加拉大饥荒,三百万人丧生的惨剧给他幼小的心灵以巨大震撼,17 岁中学毕业的他就选定了经济学作为自己的主攻方向,开始严肃思考贫困、公正、社会福利等他的国家以及整个人类都面临的重大问题。20 岁时他以最优异的成绩在印度获得经济学学士学位,3 年后他又以最优异的成绩获得英国剑桥大学的学士学位,在他刚成为剑桥大学的博士生时,年仅 23 岁的他就被任命为印度 Jadavpur 大学经济学系首任系主任。

才华横溢的森获得剑桥大学的优秀奖学金,这笔钱允许他在 4 年里做任何他想做的研究。森做了一个大胆决定:研习哲学。事后证明,这是一个相当明智的决定,为他日后在经济学、政治学、伦理学等领域向人类贡献前所未有的深刻洞见奠定了坚实的基础。没有这 4 年的内力修为,森仍然会是一名出色的剑客,但决不会成为一代武林宗师。

由于剑桥大学不怎么待见社会选择理论,森直到博士毕业回到印度,才有机会开展这方面的研究。他对世界最重要的贡献之一——自由悖论(又称帕累托自由不可能性定理)是在印度本土做出的。

自由悖论

“自由,自由,多少罪名假汝名以行”,罗曼·罗兰的这句名言至今仍振聋发聩。森是如何界定自由这个一望而知又难以琢磨的概念的呢?森认为,尽管自由并不是你想干什么就能干什么,但至少在某些私人领域,这个条件是可以得到满足的。例如,相比躺着睡,我更喜欢趴着睡,我这个口味虽然重了点,但不碍别人什么事。如果有两个社会状态 xy,除了在 x 中我趴着睡而在 y 中我躺着睡以外,其他都一样,那么社会应该偏好或选择 x 而不是 y。每个人都有这样一些让社会遵从自己口味的私人领域(或社会状态),这一点看上去毫无争议。

然而,森发现,这个条件与另一个毫无争议的条件——帕累托条件(即一致同意性条件)竟然不能被同时满足。帕累托条件要求,如果每个人都认为 xy 好,那么社会也要认为 xy 好。帕累托条件通常被认为是效率的体现,在自由主义者看来,自由是效率的保障。计划经济之所以不如市场经济在配置资源上更有效率,就是因为后者比前者拥有更多自由。然而森的定理表明,自由不但不是效率的保障,甚至会妨碍效率。这真是见了鬼了!

实际上,森证明了一个更强的结论。首先,他重新定义了社会整合机制。他没有像阿罗一样,要求社会整合机制在输入一组线序后,也返回一个线序,而是只要求返回一个非空集合。即社会整合机制根据个体偏好,选出最好的(可以是多个)备选项,森称这样的社会整合机制为“社会选择函数”。其次,在社会选择函数的框架下,森重新表述了自由性条件和帕累托条件,使得这两个条件都变得更弱了。

自由性条件:至少有两个个体是自由的。某个个体是自由的,意指对该个体而言,存在一对社会状态(或备选项)x, y,使得该个体能根据自己关于 x, y 的偏好,决定哪个备选项不能入选社会选择的结果集:若个体认为 x > y,则 y 不能入选;反之,则 x 不能入选。

帕累托条件:若每个人都认为 x > y,则 y 不能入选社会选择的结果集。

帕累托自由不可能性定理(Sen 1970):没有社会选择函数能同时满足自由性条件和帕累托条件。

这个结果尽管看上去令人惊讶,但证明却异常简单。假设存在满足这两个条件的社会选择函数,根据自由性条件,存在个体 A 和 B,A 关于某一对备选项 a, a' 有否决权,B 关于某一对备选项 b, b' 有否决权,不妨设 b, b' a, a' 均不相同(相同的情况类似可证)。考虑如下一组排序:

A:b' > a > a' > b > 其他选项
B:a' > b > b' > a > 其他选项
其他个体:与 A 排序一样(或与 B 排序一样)

根据自由性条件,对任意社会选择函数,a' 和 b' 都不能入选。另一方面,由于所有人都认为 a' > bb' > a,故据帕累托条件,ab 也不能入选。最后,由于每个人都认为 a > 其他选项,故据帕累托条件,所有其他选项也不能入选,这与社会选择函数必须返回非空集矛盾,证毕!

名噪江湖

凭借自由悖论一举成名的森几乎在英美所有顶尖大学都担任过教授或访问教授(其中包括哈佛大学、剑桥大学、牛津大学、斯坦福大学、伦敦经济学院、耶鲁大学、加州大学伯克利分校、麻省理工大学、康乃尔大学等),拥有超过 90 所大学的名誉学位,并曾出任英国剑桥大学三一学院院长、美国经济学会会长和国际经济学会会长(至少在经济学领域,这近似于武林盟主了)。

值得一提的是,尽管大部分时间在英美等国工作和生活,森至今仍保持印度国籍(也是其唯一国籍,即使印度承认双重国籍),而他的印度身份还曾给他带来过不少麻烦。

一次,时任剑桥大学三一学院院长的森从国外旅行回到英国,伦敦机场的官员仔细审核了森的护照,发现住址一栏写的是“剑桥三一学院院长公寓”,这位官员怎么也想不到,赫赫有名的三一学院的院长是眼前这位印度佬,于是问森是不是院长的亲密朋友(否则怎么能与院长共处一室呢),森思考了一下“自己是不是自己的朋友”这个哲学问题,踌躇片刻后给出了肯定的回答,官员见森迟疑半晌,更加怀疑森是非法移民,于是盘问起森迟疑的原因。当然,这戏剧性的一幕最终妥善收场。

森不但坚持做一名印度公民,而且每年都要回国参与印度的公共事务。由于他对贫困、饥荒、不平等、剥夺等问题的研究,他被人们尊称为“经济学的良心”,这是比诺贝尔奖得主更来之不易的称谓。正如行走江湖,见面被人称呼一声“大侠”不难,而被唤作“侠之大者”的,恐怕就没有几个了。

2006 年《时代》杂志评选他为 60 年来的亚洲英雄。
2010 年《时代》杂志评选他为世界最有影响的百人之一。
2012 年他获得美国政府颁发的国家人文科学奖章,成为获得该奖的首位非美国公民。

1970 年,森曾在哈佛大学与阿罗和罗尔斯共同开设“社会公正”课程,42 年后的今天,已年届 80 的他,仍然以每学期两门课程的工作量,奋战在哈佛大学的教学第一线。