小学数学故事：美国大选

　　2008年11月4日，美国总统大选让奥巴马成为美国历史上第一个黑人总统，也让这个日子永载史册。美国媒体在之前的宣传中纷纷称之为“你一生中最重要的一次投票”，——事实上，每次投票之前都会有类似的宣传出现，但是这一次也许是最贴切的。

　　既然有投票，就有事前的机关算尽，事后的败寇成王。美国人的情绪在那个特殊的夜晚激烈地动荡着，藕粉们（奥巴马的支持者）纷纷称之为美国历史的新纪元，麦片们（麦凯恩的支持者）愤愤不平地说奥巴马只不过靠巧言令色才窃得大位，稀饭们（希拉里的支持者）则黯然神伤，来来去去想的都是“要是希拉莉当时赢了民主党初选……”。而在大洋此岸的中国，借助互联网的帮助，大家也纷纷密切注视着这次大选中的种种风吹草动。在论坛里，在博客上，大家理直气壮地谈论着发生在另一个国家里的选举，在指点江山的快意之外，也心照不宣的把它视为某种意义上的借镜。由于众所周知的原因，我们对于投票这件事情的了解几乎总是匮乏的，隔岸观火，也不失为一个学习投票常识的办法。

　　“且慢，”也许你会有异议，“如果说选举过程中的政治操作需要学习还可以接受的话，投票本身还有什么知识可言？一人一票的统计就是了啊。”

　　当然不仅如此。正如我们所知，美国的选举制度并非是简单的一人一票。事实上，“一人一票”并不一定是个自然的办法——甚至也不一定是个好办法。

　　让我们从下面这个简单的例子开始。假设有一组人要从ABC三个候选人中选出一个来担任某项职务。大家对这三个人的内心偏好列如下表：

　　有2个人认为A优于B优于C

　　有3个人认为A优于C优于B

　　有2个人认为C优于B优于A

　　有4个人认为B优于C优于A

　　现在大家投票。按照每人投一票的原则，每个人给他心中最胜任的人选投上一票，结果是A得5票，B得4票，C得2票，排名是A高于B高于C，最后A当选。看起来没什么问题。

　　如果换一个规则，假定大家认为每人一票不足以反映民意，决定仍然按照上面的偏好顺序投票，但是每个人分别投两票给他认为最胜任和次胜任的人选，那么结果会有多大差别？计算一下就会发现，最后A得5票，B得8票，C得9票，排名是C高于B高于A，当选的是C，原先票数最高的A反而垫底！

　　上述怪诞的事实说明，在选民意志不变的情形下，选举规则的改变有时会在根本上颠覆（而非像直觉告诉我们的那样至多小幅改变）选举的结果。事实上，你很容易想到，除去上面所说的一票制和两票制，还有很多别的看似公平的选举方式，例如数学家J.Borda在1770年批评法兰西科学院选举制度时提出来的Borda计票法。Borda认为如果每个人只投一票，那么选民对自己心目中除最优者之外的选项的偏好顺序就完全无从在选举中得以表达，而每人投两票或者更多票也不公平，因为那抹煞了每个人心目中最优和次优的区别。他建议，比方说还是有三个候选人的情况下，每个人给心目中的最优者投两票，次优者投一票，第三名不投票，这是最能完整表达投票者偏好顺序的方式。如果你把这个规则应用到上面那个实例，结果会变成A得10票，B得12票，C得11票，排名是B高于C高于A，最后当选的是B。——又是一个新结果。

　　事实上，把上面的论述抽象化一点。无论是一票制，两票制，还是Borda投票制，都可以看成排序投票制的特例。所谓排序投票就是每个人给候选人在心中排好一个偏好次序，然后给每个次序上的人投一定票数。这听起来是很合理的办法，唯一的区别只是第几名到底投几票而已，而数学家D.Saari却在上世纪末给出了下面这个荒谬的定理：

　　如果有n名候选人，那么可以找到合适的一组选民，使得这组选民在偏好不变的情况下，由不同的排序投票制给出多达(n-1)(n-1)！种不同的投票结果（这是一个非常大的组合数）。不仅如此，如果n>3，那么可以找到合适的一组选民，使得在选民偏好不变的情况下任何候选人都通过选择一个合适的排序投票制当选。