《社会科学中的计算思维方法》《网络、群体与市场》教学课件-012(表决)

1、关于第十二周学习内容的延伸讨论表决模型、困惑、思路人群与网络社会网络中的计算思维方法本周线上内容表决在社会中的作用及其多种形式偏好关系：讨论表决制度的基础少数服从多数：形成群体决策的基础孔多塞悖论议程设置波达计数法阿罗不可能定理单峰偏好单峰偏好下的表决结果中位项定理结果驱动的表决不久前的一个真事参加某校校内的一个学科评估要从6个申请的学科中评出3个学校领导有倾向性，但校内自己难摆平，于是请若干外校人士一起组成9人委员会规则：每人投3票，达到2/3票数的学科算通过我们一次投出了：8，6，6，4，3，0而且前面三个正好是学校领导希望的！关于表决的初始问题人们为什么要表决？表决选项至少需要几个？黄金

2、规则？少数服从多数若干个人意见 集体意见寻找真相寻求主流意见2为什么会有“一票否决”？假设（你、我、他）三人要对甲、乙、丙三人投票选优你认为甲比乙好，乙比丙好，自然也就有甲比丙好我认为乙比丙好，丙比甲好，自然也就有乙比甲好他认为丙比甲好，甲比乙好，自然也就有丙比乙好甲乙乙丙丙甲?!?!个体理性不一定能导致群体的理性甲乙丙乙丙甲丙甲乙每一个局部都正确不一定全局就正确！关于偏好关系（选项3）A,B,C,DR1:AB,BC,CDR2:AB,DC,BAR3:AB,BD,ADR4:AB,AC,AD,BC,BD,CDR5: ABCD非对称完备传递R4传递性：对任意不相同的元素A, B, C，若有AB且BC

3、，则要有AC对与错？（邻座讨论）定义：如果存在 A, B, , X，有关系AB, B, , X, XA，则称该关系中存在一个“环”（回路）。给定一个偏好关系，假设它是非对称的、完备的，那么，该关系要么是传递的，要么存在一个环。假设有m（奇数）个表决者，n个候选项每人给出候选项集合上的一个完备且传递的偏好关系问题这些关系总共包含多少候选项对？按少数服从多数原则形成的集体偏好关系中一共包含多少候选项对？它是否一定完备？是否一定传递？进一步“体会个体意见群体意见”假设有4个候选项A, B, C, D，三个人要对它们进行表决，分别给出了下面的意见。按照少数服从多数原则（孔多塞原则），试判断其中是否存在

4、孔多塞悖论如果没有，则给出群体排序（第一个也称为孔多塞胜者，Condorcet winner）ABCD; DCBA; ACBD关于表决机制我们已经知道每个个体给出完备且传递的关系（全序），采用少数服从多数聚合方式，有可能（但不一定）出现孔多塞悖论还知道根据每个个体给出的全序，为回避孔多塞悖论，采用不同的议程设置两两比较（少数服从多数方式），有可能导致不同的集体排序结果如果个体给出的关系中不隐含有孔多塞悖论，是否也可能出现议程设置显现的矛盾？波达计数法的结果可能与孔多塞原则（Condorcet principle）的结果矛盾例如，三个选项，A, B, C，7人参加表决3人认为：A B C2人认为

5、：B C A1人认为：B A C1人认为：C A B按孔多塞原则A是胜者按波达计数法A=3*2+2*1+2*0=8B=3*2+3*1+1*0=9C=1*2+2*1+4*0=4理解单峰偏好候选项集合：A, B, C, D, E设在某属性下的序为 ACEBD 下面哪些候选项排序满足单峰偏好要求最爱第二第三第四第五ABCDEBCADEEDCBABCDAECBDEA但是不难验证B C D A E最爱第二第三第四第五ABCDEBCADEEDCBABCDAECBDEA这是为什么？这5个排序在属性序（A-B-C-D-E）下都是单峰偏好！进一步的问题就是：若没有孔多塞悖论，是否一定存在某种属性序，其下所有个体

6、排序都满足单峰性课堂作业： 计算集体排序ABCDEFACDBEFCDEFABDCAEBFBACDEFEFDCABDECAFB属性序：B，A，C，D，E，F问题这个方法（算法），针对满足单峰偏好性质的个体排序，给出了一个满足少数服从多数原则的群体排序。当然，如果不用这样一种办法，而是采用基本的两两比较、按少数服从多数原则确定群体偏好的方法，也可以得到相同排序结果。这种方法有什么优势呢？为什么这方法是对的即要说明，相继取出的那些“中间项”，在少数服从多数原则下，比其他所有还剩下的选项都要“大”。大于所有出现在排序表头的选项也大于没出现在排序表头的选项中间项胜出的一般图示每条线代表一个人此人将Xm排

7、第一选项按属性序排列排序?给定一组（许多）个体排序如果不知道它们是否“单峰”，有什么好一点的办法看（1）是否存在孔多塞悖论；（2）如果不存在，群体序该如何？办法之一两两比较，将结果表达为一个有向完全图无有向环存在出度和入度为0的节点从入度为0的节点开始，一个个删除如果删不下去了，就出现了孔多塞悖论；否则删除的顺序就是群体序其他表决方式例子假设13个人要对3件事进行组合投票：给定所有可能的支持（Y）或反对（N）组合，要求每人选一个。他们的选择如左（没人觉得应该是NNN）：Y N N Y N N Y N N N Y N N Y N N Y N N N Y N N Y N N Y Y Y N Y N

8、 Y N Y YY Y Y 但如果从这结果看人们的态度，恰好应该是NNN！Paradox of multiple electionsSocial Choice TheoryComputational social choice选择方式问题计算复杂性问题应用问题搜索排序，推荐，评级， ，凡需要从大量个体认识形成群体认识，即群体决策的场合有些大学（例如University of Amsterdam）开有专门的课程（Ulle Endriss教授）6天前设定的教学目标得到一些具体体会对社会科学与计算思维交叉的课程掌握部分教学内容网络、群体与市场熟悉一种教学方式基于慕课的混合式教学30%的人有兴趣且初步

9、有信心回校开课完整一门新课，或部分融入现有课程6. Communicates High Expectations Expect more and you will get more. High expectations are important for every one for the poorly prepared, for those unwilling to exert themselves, and for the bright and well motivated. Expecting students to perform well becomes a self-fulfilling property when teachers and institutions hold high expectations of themselves and make ext