社会计算012(表决)课件

关于第十二周学习内容的延伸讨论表决模型、困惑、思路人群与网络社会网络中的计算思维方法表决通过众人投票，形成对事物的群体判断一种基本的制度，体现在社会生活的方方面面“事物”被表决对象“众人”至少两个；表决制度的设计古老的话题谁是“众人”？投票的规则决定性判断形成的规则什么表决制度是一个合理的制度？合理的表决制度结果要体现集体的偏好，或者反映真实情况不容易被个别人的投票“操纵”信念的背后是信息，即参与人所掌握的关于表决对象的信息（因人而异），因此表决结果也可以看成是信息聚合的结果影响表决结果的两个方面投票同意不同意（O/X）对A的元素排序给A的每个元素打分如何投票？如何形成结果？给定侯选项：A=A1,A2,AN形成结果少数服从多数比例（1/2,2/3等）通过去掉一个最高分，去掉一个最低分给出一个（集体）排序分层表决（例如某些选举）偏好关系：讨论理性表决的基础对两个需要表决的备选项 X 和 Y，如果个体 i 选择 X（也称为偏向X），则记为一般地，给定一个有穷备选项集合X,Y,Z,W,U,V，我们可以问其中任何两个元素之间的偏好关系。参与表决的人，在有些关系上可能意见一致，在另一些上不一致称“X优于Y”或“X大于Y”对偏好关系的（合理）假设完备性（complete）对于给定的选项（X,Y），要么偏好X，要么偏好Y；不能两个都一样，或“无可奉告”传递性（transitive）假定有3个备选项（X,Y,Z），如果在（X,Y）比较中，偏好X；在（Y,Z）比较中，偏好Y；则在（X,Z）比较中，应该偏好X这等价于在集合元素之间有一个全序群体偏好的形成，A=A1,A2,An基本问题设每个表决者（V1,V2,Vm）分别给出了A上的一个完备且传递的偏好关系，如何综合它们，形成群体对这些候选项的一个合理偏好关系？什么叫“合理”？体现群体意见“少数服从多数”精神是合理性的基础，即若多数人都认为 X Y，则在群体意见中应该有 X Y。当只有两个侯选项（X,Y）设V1,V2,Vm为奇数个表决者，每个人给出 XiY 或 YiX。如果多数人偏好为XY，则群体偏好为 XY，否则群体偏好为 YX少数服从多数如果我们有三个候选项(X,Y,Z)少数服从多数如果我们有三个候选项（续）这个例子表明，尽管每个个体的偏好关系都是完备且传递的（全序），但结果不一定！少数服从多数孔多塞（Condorcet）悖论孔多塞在1700年研究表决问题的时候，发现在3个人对3个备选项（X,Y,Z）进行表决的场合，有可能每人偏好都满足完备性和传递性，但按少数服从多数原则得到的群体偏好却不一定满足传递性。一般地，从传递性个体偏好，按少数服从多数聚合方式，得出了非传递的群体偏好，称为孔多塞悖论。合理的个体行为 合理的聚合方式 不合理的群体结论！孔多塞悖论出现在许多实际场合假设一个人要上大学，她希望：大学排名好，班级人数少，奖学金高，但面对：大学全国排名班平均规模奖学金X440$3000Y818$1000Z1224$8000 XYZ YZX ZXY小插问假设有m（奇数）个表决者，n个候选项。每人给出候选项集合上的一个完备且传递的偏好关系。这些关系总共包含多少候选项对？按照少数服从多数原则形成的偏好关系中一共包含多少候选项对？它是否一定完备？是否一定传递？（这个问题的意义在于加深对偏好关系概念的体会）调整个体行为的假设？调整聚合方式？合理的个体行为 合理的聚合方式 不合理的群体结论！一种不同的聚合方式基于完备且传递的个体偏好关系，通过对侯选项两两进行“少数服从多数”对比只是聚合群体意见的一种方式“逐一胜出（淘汰）”是另外一种可能假定备选项的任意一个序列，X,Y,Z,沿着这个序列，开始比较X和Y（依照少数服从多数），然后胜者再和Z相比，这样就可以得到一个“最大的”对剩下的再进行这个过程，得到“次大的”合理的个体行为 合理的聚合方式 不合理的群体结论？！例子，设有：次序：X，Y，Z次序：Z，Y，X议程设置问题(Agenda Setting)积分制（另一种聚合群体意见的方式）波达计数法（Borda Count,1770）假设有 N 个候选项，个体 i 对候选项的排序对应一种赋值，偏好排在第一的赋值 N-1；以此类推，最后一个赋值为 0依据每个候选项得到的赋值和（积分），由高到低排序，从而形成群体偏好排序注若出现同样的积分，假定有一种外部约定的处理方法个体分数赋值显然还可以有其他各种方式积分制假设有2个个体（1,2）面对4个备选项（A,B,C,D）；个体的排序以及群体的积分如下第一偏好第一偏好第二偏好第二偏好第三偏好第三偏好第四偏好第四偏好个体个体1ABCD个体个体2BCAD得分得分A=3+1B=2+3C=1+2D=0+0群体偏好群体偏好BACD积分制合理吗？假设五个影评家（1,2,3,4,5）对两部影片（A,B）的排序影评家影评家公民凯恩公民凯恩教父教父110210310401501得分得分32这看起来没问题，相当于在两个备选项上采取少数服从多数规则。假设增加了一个低俗小说本质上，5个人都认为低俗小说是最差的，于是影评家影评家公民凯恩公民凯恩教父教父低俗小说低俗小说12102210321041205120得分得分870影评家影评家公民凯恩公民凯恩教父教父低俗小说低俗小说12102210321040215021得分得分672但个体4和5可能做一种策略性投票，既保持低俗小说总体最差，同时也使自己青睐的教父胜出我们遇到了困难？前面讨论的是“合理的个体偏好”“合理的聚合规则”不一定得到合理的结果，而且结果有可能被投票者“操纵”我们尝试了不同的“聚合规则”，但看来遇到了困难一般地，我们可以想像表决系统为一个函数，它取若干排序表（完备且传递的关系）为输入，要产生单个排序表输出。我们问，怎样才是“没有毛病的”？表决系统示意图在聚合规则上动脑筋似乎很难了还有没有可能？聚合规则个体序群体序对聚合规则的两个合理要求趋同性：对于任意2个侯选项（X,Y），如果所有个体都偏好X，则群体排序结果中也应该偏好X，称之为趋同性原理（unanimity principle）独立于无关项（IIA）：群体对侯选项（X,Y）的排序，仅取决于个体对它们的偏好，与个体对其他侯选项的看法无关。即，X和Y在群体排序中的结果，不能因为某一个个体调整了某个 Z 的相对位置而改变independence of irrelevant alternatives IIA要求示意例子如果对于V1给出 XYZUWV2给出 YXZWUV3给出 WUXYZ表决系统给出的结果中有“XY”，则它对下面的输入也应该给出“XY”V1给出 XZYUWV2给出 YXZWUV3给出 WUXYZ阿罗不可能定理在3个或更多侯选项的条件下，任何多于2人参与的表决系统，都不可能同时满足（1）趋同性；（2）IIA（独立于无关选项）；（3）非独裁性换句话说，若满足了（1）和（2），则群体排序一定就等于某个个体的排序又称之为阿罗悖论（社会选择与个人价值，1951）思考问题我们已经看到从不同角度提出的，表决系统综合个体偏好时应遵循的一些原则要求（听起来都是合理的）少数服从多数议程设置波达记数法趋同性IIA（独立于无关项）它们之间有什么联系吗？能否对个体行为提进一步的（合理）要求？合理的个体行为 合理的聚合方式 不合理的群体结论理解“合理的个体行为”假设（X,Y,Z）分别代表财政支出由低到高，我们来理解三个人表态的逻辑个体1：钱花得越少越好个体2：少了可能不够，多了可能浪费，中间较好；如果还不够，就多花点个体3：？（行为很难解释，尽管在形式上也有个全序）偏好偏好1偏好偏好2偏好偏好3个体个体1XYZ个体个体2YZX个体个体3ZXY 合理的个体行为 合理的聚合方式 不合理的群体结论导致以“两两比较”“少数服从多数”原则得到的群体偏好不传递：XY,YZ,ZX即出现孔多塞悖论单峰偏好 表决者的合理行为设想侯选项集合X2,X1,X5,XN的某种性质（P）有一种隐含的顺序（如支出预算数，个子高低，财富多少，考试分数高低等），如下所列 PX1 PX2 P XN所谓表决者的态度应该满足单峰偏好指的是若Xi被他排在了第一位，则对于kji，Xj要排在Xk的前面；且对于ijPBPEPAPC下面哪些候选项排序满足单峰偏好要求？最爱最爱第二第二第三第三第四第四第五第五ABCDEBEACDEBADCCAEBD单峰偏好定理：若所有选举人的排序都满足“单峰偏好”，则按照少数服从多数规则两两比较侯选项产生的群体偏好是完备且传递的。不失一般性，为方便起见，设特征序也就是元素下标序如何证明这样一个结论？“构造性方法”（constructive approach）1.给出一种具有操作性的方法，基于任何满足单峰性质的个体偏好集合，形成一种完备且传递的群体偏好（全序）2.证明该群体偏好相对于给定的个体偏好集合而言是符合少数服从多数原则的个体偏好完备且传递单峰群体偏好完备且传递少数服从多数从单峰个体排序形成群体排序的一种方法设N个候选项，X1,X2,XN，有某种特征序M个（奇数）表决人，他们在上述侯选项序上的偏好是（按该特征序）单峰的构造一个群体排序表（即一个完备且传递的关系），其中若XiXj，则在M个个体排序中的大部分都有XiXj。即两两都满足“少数服从多数”原则下面是一个流程，说明存在性和具体结果存在这样的群体排序即表明没出现孔多塞悖论单峰偏好下群体排序的形成要点：逐次找出“最大的”（群体意义）记L1,L2,LM为个体排序表，Li(1)为对应个体表中第一个（最大的）元素将Li(1),i=1,2,M按照X1,X2,XN的特征序排列（一共M个，有的X可能有多次出现）从如此排列的M个元素中取中间项为群体排序的第一项（最大的元素）从L1,L2,LM中删除该元素，留下的依然是单峰排序表，接着可以取出第二个，等等假设它们都满足以 X1 X2 X3 为特征序的单峰性考察这些表中第一个元素按该序排列的情况：X1,X1,X2,X2,X3X2是“中位项”，因此X2是第一个佼佼者从每个表中删除它，继续这种中位项提取，得第二佼佼者，例子：例子：个人排序表（个人排序表（M=5）再看前面的例子有3个个体和5个备选项，个体偏好排序如下：12345个体个体1ABCDE个体个体2BCDAE个体个体3CBADE不难验证，按照A,B,C,D,E的顺序，都是单峰的选择“最大的”：A，B，C B选择“次大的”：A，C，C C选择“第三大的”：A，A，D A类似地，相继得到D，E不难验证，这个结果符合两两比较得到的结果。为什么如此做是对的（中位项定理）即要说明，相继取出的那些“中间项”，在少数服从多数原则下，比其他所有还剩下的候选项都要大记L1,L2,LM为个体排序表，Li(1)为对应个体表中第一个（最大的）元素将Li(1),i=1,2,M按照X1,X2,XN的特征序排列（一共M个，有的X可能有多次出现）从如此排列的M个元素中取中间项为群体排序的第一项（最大的元素）中位项定理的证明只需说明，当Li(1),i=1,2,M按照X1,X2,XN 的序排列后，其中位项与其他M-1项中的不同元素在两两比较中均能基于M个个体排序中的情形，以少数服从多数原则胜出从一个例子看，若排列情况如下：X1,X1,X2,X2,X3 (注:它们是5个个体排序的头)为什么说5人中至少3人认为X2X1?中间那位如何认为？第4位如何认为？第5位如何认为？对称地，我们看到中间和左边的人都会认为X2X3。中间项胜出的一般图示思考问题给定M个满足单峰偏好性质的个体排序（设N个候选项），上述过程（算法）给出了一个高效生成满足少数服从多数原则的群体排序估计这个过程要用的计算步骤数（复杂性）如果不采用这个算法，而是采用基本的两两比较少数服从多数方法，试估计要用的步骤数（计算复杂性）作为信息汇集形式的表决（有时，客观上，侯选项中存在一个“真实”，但参与者对信息的掌握不一致或者有不同的解释，大家的目标是一致的，即希望达到那个真实）考虑下面这个例子以50%概率拿出其中一个坛子供三人表决用三人依次，随机取一个看看，放回；不交换意见每人给出关于坛子是1号还是2号的判断若多数对了，3人都得奖；否则，3人都受惩罚这表明，有些场合一个人的“不诚实”投票也许对大家都更好！考虑投票问题的两种思路信号驱动根据得到的信号，我该如何投票？（判断在给定信号下不同选项结果的概率）结果驱动我的一票在什么情况下起作用（can make difference）？我该如何投票，以使得那种情况发生时达到正确结果的可能性大些？（从而可能应该忽略信号）陪审团裁决制度美国的陪审团制度无罪假设，有罪推定对刑事案件，需要陪审团所有人都认为被告“有罪”才能定罪（一票否决）法院给陪审员的指导意见根据所得到的证据，只有“相当程度上怀疑被告有罪”才认为他有罪而不是“相比无辜而言有罪的可能性较大”你的一票在什么情况下有作用？设设Prguilty=Prinnocent=0.5Gsignal：有罪（G）信号；Isignal：无罪（I）信号Prguilty|Gsignal=q0.5,Prinnocent|Isignal=q0.5其他人都诚实投票你的一票有作用的情形：所有人都得到有罪（G）信号，就你自己得到无罪（I）信号。下面我们来说明，无论你得到什么信号，总投“有罪”票可能利于集体形成正确裁决设陪审团共有K个成员由于q0.5，最后这式子随k而趋向1。这也暗示，为了避免影响“大局”，人们会倾向于忽略得到的无辜信号。这就是美国陪审团制度的一个弱点。思考题（关于中位项定理）在前面的证明过程中，我们只是涉及到了在个人排序表第一项之间的比较。我们不难意识到，候选项集合（A=X1,X2,Xn）中的元素不一定都出现在某个个人排序表第一项。那么，中位项在排序表第一项之间的“最大”为什么就意味着也是所有A中元素的最大呢？A=X1,X2,XnM个表决者给出：L1,L2,LmL1(1),L2(1),Lm(1)，都是A中的元素，有些可能多次出现，也很可能有没出现的重新按照X1,X2,Xn的序排列，设Xi是中间的现在看某个Xj，不在任何L(1)中，为什么说m中有超过一半的人认为：XiXj?