投票理论和Arrow不可能性定理

chaotic elections我们想当然认为公平的制度,在逻辑推理面前不堪一击。投票理论的水也好深!

排序投票制
考虑一个简单的例子,假设选举有ABC三个候选人,选民对这三个人的内心偏好列如下:
2人认为A>B>C; 3人认为A>C>B; 2人认为C>B>A; 4人认为B>C>A
按照一票制,A得5票,B得4票,C得2票,A当选。
按照两票制(最优+次优),A得5票,B得8票,C得9票,C当选,原先票数最高的A反而垫底。
还有数学家J. Borda在法国大革命时期批评法兰西科学院选举制度时提出的Borda计票法。Borda认为如果每个人只投一票或者更多票不公平,他建议每個选民依照喜好排序候选人,在有三个候选人的情况下,每个人给心目中的最优者投两票,次优者投一票,第三名不投票。按照Borda计票法,结果会变成A得10票,B得12票,C得11票,最后当选的是B。

以上三者都可以看成排序投票制的特例,所谓排序投票制就是每个人给候选人在心中排好一个偏好次序,然后给每个次序上的人投一定票数。而数学家Donald G. Saari提出(暂没找到paper):

如果有n>3名候选人,可以使得在选民偏好不变的情况下,构造一个排序投票制让任何候选人都通过选择一个合适的排序投票制当选!

孔多塞制和孔多塞投票悖论
投票理论在法国大革命时期浮现成为学术界的一门研究领域,除了J. Borda外,还有另一位投票理论家孔多塞Condorcet,有意思的是他反对Borda计票法,他提出的是一种成双比对法,孔多塞制:将每个选项与所有其他的选项成对比较,一次一个,而击败所有其他选项的选项便是赢家。只要一个选项在大多数选票上的位置高于另一个选项,那么它便击败了那个选项。

当候选人n>2时,以投票的多数规则来确定社会或集体的选择可能产生循环的结果。假设有三个选举人对三个候选人倾向如下:A>B>C; B>C>A; C>A>B。多数人偏好A>B,多数也偏好B>C,按照逻辑上的一致性,这种偏好应当是可传递的transivity,即多数人偏好A>C。但实际正好相反,多数人偏好C>A。没有一个能够获得多数票而通过,这就是孔多塞投票悖论

投票制度的混沌性
考虑淘汰制的选举,假设选举有ABC三个候选人,选民对这三个人的内心偏好列如下:
35人认为A>C>B;33人认为B>A>C;32人认为C>B>A
可以有三种不同的选举顺序:
1. AB进行PK,A得到35票,B得到65票,B胜出。本来很想投C的人只能投给次优的B。然后BC进行PK,B只得到33票,C得到67票,C胜出。
2. AC进行PK,A得到68票,C得到32票,A胜出。然后AB进行PK,B胜出。
3. BC进行PK,B得到33票,C得到67票,C胜出。然后AC进行PK,A胜出。

所以在淘汰赛制中,选举制度最终结果和选举顺序不同,简单淘汰制度的选举容易被操纵,尤其是当选民的意向比较平均的时候,只要选举的顺序被精心安排,任一选手都有可能最后胜出!

同样是上文的例子,如果采用一票制,A得到35票,B得到33票,C得到32票,A胜出。假定排名最后的C突然退出选举,是否要因为退出一位排名最后的选举人进行重新选举?如果进行重新选举,则A得到35票,B得到65票,B反而胜出。

这个两例子反映出投票制度的混沌性,或者说结果对扰动的敏感依赖性:某一个次要竞争者的变化,也许会影响到重量级竞争者的崛起或者覆灭。一个类似但是复杂得多的例子是在2008年年初的民主党党内初选中,希拉里和奥巴马双雄鼎立,希拉里略占优势。而爱德华兹一直屈居第三,终于在“超级星期二”来临之前的1月底宣布退出竞争,他的退出很快打破了希拉里和奥巴马的平衡,部分地促成了奥巴马在超级星期二之后的十连胜,最终逼得希拉里退选。

Arrow不可能性定理
1972年诺贝尔经济学奖的获得者Kenneth Arrow在《社会选择与个人价值》中,考虑的是比选举更为细致的社会福利函数Social welfare function,给定一个集体中每个成员对候选人一组偏好顺序序列,那么一个“社会选择机制”能够在多好的程度上得到一个综合的排序,输出一个整合了各种意见的排序?

一个合理的选举制度,它必须满足一些条件:
1. 帕雷托最优
如果在每个人的排序中A都优于B,在输出结果中A也应当优于B。
2. 无关因素独立性
假设社会福利函数返回的排序中,A在B的前。但这时某些投票的人对A、B外的第三人C的看法变卦了,不应当影响到结果中A和B的相对排序,社会福利函数的结果A还是在B的前面。
3. 非独裁性
这个函数的输出意见不能总是等于同一个人的输入意见,不存在一个人的意见总是凌驾于所有人的意见之上。反过来,独裁性就是指社会福利函数最终返回的结果,恰好和某个投票人的个人意向完全相同,那么就说明那个人独裁了这一次的选举,“被独裁”的选民很有可能对独裁这件事并无兴趣或一无所知,就如鸽笼原理,只是恰好落到了他头上而已。

最后Arrow得出的结论是,只要有三个或更多的候选者,就不可能存在一个函数,或者说社会选择机制,同时满足帕雷托最优、无关候选人独立性以及非独裁性这三个条件。

三个条件里最苛刻的是其实是无关因素独立性,受制于投票机制的混沌特征,是非常难于满足的。所以不管是投票还是民主集中制,我们都不可能通过公共选择的方式获得一个所有人都认同的、逻辑一致的价值。

最后是一些参考:Arrow不可能性定理今天你想投票了吗社会选择理论

编程语言的网络

最近在上Coursera的SNA社交网络分析,翻之前学生做的大作业压力好大,有做知识网络Network map of Knowledge and Art,有做俄罗斯选举的投票网络,还有类似的哲学的发展网络。按照哲学家网络的思路,我拿编程语言的网络来练个手,每种语言是一个节点,如果语言B受语言A的影响,则B向A连边,比如Java和Python都有受Smalltalk的OO影响,smalltalk又受Lisp,Logo影响。

数据获取
数据来自DBpedia语义数据库,简单的说,它收集的是维基百科的数据,然后经过一些处理得到结构化的语义web。互联网发明人蒂姆·伯纳斯-李曾在TED演讲"关联数据",互联网最初的设计只是想把文档放在一起而已,但是现在互联网还是有巨大的可释放潜力,我们从网上得到的数据不是我们想要的数据。在DBpedia如果你去找John McCarthy,会包含了与John McCarthy相关的信息,它们被联系到了一起,比如他的导师、他所带出来的学生、出生年、出生地、获得的成就等,下一代搜索引擎比如Wolfram|Alpha就是这么工作的。
然后用SparQL,它将Web2.0和Semantic web两种新的web技术联系起来,你可以直接在web页写类似sql语句进行查询编程语言以及该编程语言收到那些语言的影响(要翻墙):

SELECT * WHERE {
?p a <http://dbpedia.org/ontology/ProgrammingLanguage>.
?p <http://dbpedia.org/property/influencedBy> ?influencedBy.
}

拿到数据初始化/归一化,导出为csv。

数据可视化
使用Gephi进行数据可视化,这是个开源的复杂网络分析软件,没教程也能上手。这里生成了552 nodes, 1011 edges的网络,平均路径长度3.126,Force Atlas Layout,使用HITS算法提炼枢纽节点,可见Lisp, Smalltalk, C, Java, Scheme, Pascal在语言发展中的地位,不过ALGOL和Fortran不是很大,估计是太古老太传说了,新语言出度没有传递给这两者。
颜色按Community分类:绿色是functional language和logic language,橙色是object-oriented,淡蓝色Javascript,Pascal和Ada,ALGOL在一起,Lisp和Scheme分家了,看看就好。

network

节点大小按Degree设置,标出了一些有代表性的语言 比如R,Logo, Prolog, COBOL
network

如果把C语言和他的邻居受C语言影响和影响C语言的节点筛选出来,C的入度有54是所有节点里最大的,庞大的C家族一目了然:
红色表示出度,C的前身是B,原型是ALGOL 60,受Fortran和PL/I影响用= operator来表示赋值,而非ALGOL的:= operator。
蓝色入度表示C影响了C++, Python, Perl, JavaScript等语言,大部分都借鉴了C的语法。
network

Python,胶水语言,借鉴了Perl, C++, Lisp, Java, Haskell, C, ALGOL, Dylan, Icon等等等等
network

Haskell出度14是最大的,除了Lisp, Scheme, ML/Standard ML好多不认识的语言,冷艳高贵orz
network

我把Lisp, C++, Smalltalk, Java, R, javascript也做了图,放在了豆瓣相册

最后感觉编程语言网络好看有余营养不足:没有时间信息,层次也没有树状清晰。不过可以像豆瓣代码大爆炸一样按时间添加节点效果会很赞。除了分析枢纽Hub节点和平均路径长度应该还有可以挖掘的地方。

O'Reilly动物丛书颜色分析

在上次O'Reilly情人节福利文章里提到O’Reilly动物丛书颜色和内容的联系,于是拿到了360本O’Reilly丛书的旧数据,使用Python+networkx+matplotlib进行分析:

按颜色关键词排序
对书名进行分词作为关键词,统计频次排序。这里篇幅限制列出了出现大于1次的keywords列表,很明显动物丛书颜色是有主题的,比如最新的Data Science Kit都是红色封面。

PMS 301C
微软系列
[('.net', 12), ('windows', 10), ('visual', 7), ('basic', 6), ('c#', 6), ('2000', 5), ('essentials', 4), ('excel', 3), ('win32', 3), ('services', 3), ('writing', 2), ('framework', 2), ('server', 2), ('security', 2), ('access', 2), ('macros', 2), ('active', 2), ('language', 2), ('vb.net', 2), ('system', 2), ('word', 2),('asp.net', 2), ('administration', 2), ('transact-sql', 2),('applications', 2)]
PMS 3272C
Web相关
[('web', 12), ('xml', 7), ('mx', 5), ('javascript', 4), ('apache', 4), ('php', 4), ('essentials', 3), ('flash', 3), ('xslt', 3), ('html', 3), ('actionscript', 3), ('services', 3), ('practical', 2), ('cd', 2), ('privacy', 2), ('perl', 2), ('bookshelf', 2), ('http', 2), ('applications', 2)]
PMS 313C
神兽Perl
[('perl', 25), ('best', 3), ('journal', 3), ('perl/tk', 3), ('regular', 2), ('graphics', 2)]
PMS 165C
Oracle系列
[('oracle', 31), ('pl/sql', 7), ('sql', 3), ('tuning', 2), ('sql*plus', 2), ('performance', 2), ('database', 2), ('essential', 2), ('dbas', 2)]
PMS 2607C
Java相关
[('java', 33), ('enterprise', 7), ('javaserver', 3), ('javabeans', 3), ('best',3), ('applications', 3), ('practices', 3), ('xml', 2), ('web', 2), ('jdbc', 2),('data', 2), ('struts', 2), ('weblogic', 2), ('vol.', 2), ('servlet', 2), ('pages', 2), ('database', 2), ('jakarta', 2), ('workbook', 2)]
PMS 246C
语言+工具
[('python', 6), ('c', 6), ('c++', 5), ('mysql', 3), ('shell', 3), ('awk', 3), ('gnu', 3), ('practical', 3), ('vi', 2), ('unix', 2), ('sed', 2), ('emacs', 2), ('uml', 2), ('editor', 2), ('sql', 2), ('using', 2), ('embedded', 2), ('cvs', 2),('software', 2)]
PMS 2725C
Mac OS X
[('mac', 7), ('x', 7), ('os', 7), ('unix', 4), ('cocoa', 3), ('geeks', 2), ('panther', 2)]
PMS Reflex Blue
网络通信
[('networks', 4), ('using', 4), ('cisco', 4), ('network', 3), ('internet', 3), ('sendmail', 3), ('system', 3), ('administration', 3), ('samba', 2), ('essential', 2), ('routers', 2), ('802.11', 2), ('dns', 2), ('lists', 2), ('wireless', 2),('protocols', 2)]

orelly

按书名关系可视化

按颜色聚类就没有意义了,所以就按书名建图:如果两本书书名有相同的关键词则连边。把无信息量水词pocket, reference,cookbook, programming, guide, definitive, learning, designing, managing, mastering, building加入stopwords,剩下书名包含的信息量更有限了,每个节点的度不大。

作图用了Fruchterman-Reingold force-directed algorithm,同其他书关系比较多的书将绘制的比较靠近中心,而关系较少的会在相对靠外的位置。可以看出橙色和紫色封面的书有比较好的聚类,因为橙色关键字是Oracle紫色关键字是Java,青色的有Perl系列的,右下粉色的是Python系列。

orelly-with-labels

PS1: 不是统计专业的,也不知道还有什么信息可以挖掘,计算closeness, betweenness, Hub节点在这里ms没有实际意义,再去解下最大团Maximum Clique啥的。
PS2: 要是能找到更全更新的O'Reilly动物丛书数据就好啦!

比赛中的数据可视化

上个月在Kaggle看到一个关于Kaggle自己的leaderboard数据可视化任务:表格形式反映比赛排名太枯燥,如何可视化地反映出比赛中随时间交替排名激烈的竞争场面?

To an observer, the leaderboard is a spreadsheet. They see funny team names, numbers with too many decimals, strange column titles, and none of the history behind the battle. We run a veritable nerd olympics, but instead of smashing the 100m world record, we're elbowing for a few decimal places of some esoteric quantity called a capped binomial deviance. It's faceless. It's cold. It fails to tell the story of the battle. And you know what that means?This means war.

提交上来的候选作品思路都差不多,时间为横轴排名为竖轴,可以一目了然看出排名随时间的变化趋势,并且也很容易看出一个队伍是从什么时间点加入比赛的,老外管这个叫Bumps Chart,还跟英国剑桥牛津的划船赛有关。后来Bumps Chart其实就曲线图,但是特别在只有两个时间点。

battles of the best

还有一个比较特别的作品使用Bubble Chart,横轴是每支队伍竖轴是比分,每个泡泡表示一个提交,加入比赛的时间点特别标出。想到ACM比赛就可以这么进行数据可视化处理(当然现在的表格表示挺好的):比赛队伍/通过的题目数/提交次数/程序耗时/时间有五维,比赛队伍用不同颜色泡泡表示,通过的题目数是竖轴,程序耗时是横轴,提交次数可以用泡泡大小来表示,最后时间轴左右拖动显示一个时间点的比赛状态。可以参照Hans Rosling在2006年TED大会上的演讲:数据可视化透视世界发展状况。
kaggle WaterGunRaceChart

O'Reilly情人节福利

oreilly

今年情人节O’Reilly给程序猿们也带来了福利:所有粉红色的电子书半价。FOREVER ALONE!

说到O’Reilly出品的动物丛书,程序猿无人不知。这系列书最显著的特点就是封面上手绘的动物,所以也有动物世界/饲养员指南的别名。考据癖有专门一篇文章解疑了为什么O’Reilly用动物形象做书籍封面,原文可见Origin of Species: A History of O'Reilly Animals

设计者Edie Freedman姐姐在设计动物丛书的第一本书时(上图中间),她接触到UNIX、vi、sed&awk、lex、yacc这些不知所云的词,让她觉得这些词都像来自于当时正流行的游戏“龙与地下城”,于是她心目中UNIX程序员的形象就是一个龙与地下城的玩家。Edie在19世纪的木版画中找到了灵感,画中诡异的动物刚好和那些高深的UNIX术语是绝配。还有一件更严肃的事情,出版动物丛书让Edie更加注意到生态问题。很多封面动物已经濒临灭绝,而在版画绘制的时期,这些动物还是大量存活的。O’Reilly也希望他们使用这些动物做封面能够引起人们对动物保护的关注。

关于O’Reilly动物丛书颜色和内容有没有联系,应该是有,不过没有查到具体说明和相似的问题,不过有所有O’Reilly丛书数据,可以根据颜色然后分析关键词,就先在这挖个坑。FOREVER ALONE!

close