《学科课程教师培训班第23章》由会员分享，可在线阅读，更多相关《学科课程教师培训班第23章（29页珍藏版）》请在金锄头文库上搜索。
1、表决（voting） “制度中的计算”之二,（第23章）,一个表决问题的例子,以50%概率拿出其中一个坛子供三人表决用 三人依次，随机取一个看看，放回；不交换意见 每人给出关于坛子是1号还是2号的判断 若多数对了，3人都得奖；否则，3人都受惩罚,（信号驱动 vs 结果驱动）,表决，票决,通过众人投票，形成对事物的群体判断 一种基本的制度，体现在社会生活的方方面面 “事物” 包含若干对象，至少两个 “众人” 至少两个；,表决制度的设计古老的话题 谁是“众人”？ 投票的规则 决定性判断形成的规则,什么表决制度是一个合理的制度？,合理的表决制度,能形成体现集体信念（或者反映真实情况）的结果 不容易被
2、个别人的投票“操纵” ,信念的背后是信息，即参与人所掌握的关于表决对象的信息（因人而异），因此表决结果也可以看成是信息聚合的结果,影响表决结果的两个方面,投票 同意不同意（O/X） 对A的元素排序 给A的每个元素打分 ,如何投票 ？,如何形成结果 ？,给定备选项：A = A1, A2, , AN,形成结果 少数服从多数 比例（1/2, 2/3等）通过 去掉一个最高分，去掉一个最低分 给出一个（集体）排序 ,分层表决（例如某些选举）,偏好关系：理性表决的基础,对两个需要表决的备选项 X 和 Y，如果个体 i 选择 X（也称为偏向X），则记为,一般地，给定一个有穷备选项集合X,Y,Z,W, U,V
3、，我们可以问其中任何两个元素之间的偏好关系。 参与表决的人，在有些关系上可能意见一致，在另一些上不一致,称“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上的一个完备且传递的偏好关系，如何综
4、合它们，形成群体对这些候选项的一个合理偏好关系？ 什么叫“合理”？ 体现群体意见 “少数服从多数”精神是合理性的基础，即若多数人都认为 X Y，则在群体意见中应该有 X Y。 完备且传递？,当只有两个侯选项（X,Y）,设V1, V2, , Vm为奇数个表决者，每个人给出 XiY 或 YiX。如果多数人偏好为XY，则群体偏好为 XY，否则群体偏好为 YX,少数服从多数,如果我们有三个候选项(X,Y,Z),少数服从多数,如果我们有三个候选项（续）,这个例子表明，尽管每个个体的偏好关系都是完备且传递的（全序），但结果不一定！,少数服从多数,孔多塞（Condorcet）悖论,存在3个人对3个备选项（X
5、, Y, Z）进行表决的情形，即使每人偏好都满足完备性和传递性，按少数服从多数原则得到的群体偏好却不一定满足传递性，这就是孔多塞于1700年讨论的现象。 一般地，从传递性个体偏好，按少数服从多数聚合方式，有可能得出非传递性群体偏好，称为孔多塞悖论,合理的个体行为 合理的聚合方式 不合理的群体结论！,调整个体行为的假设？调整聚合方式？,孔多塞悖论出现在许多实际场合,假设一个人要上大学，她希望：大学排名好，班级人数少，奖学金最高，但面对：,XYZ YZX ZXY,改变聚合方式？,基于个体的完备且传递的偏好关系，通过对侯选项两两同时进行“少数服从多数” 对比只是聚合群体意见的一种方式 “逐一胜出（淘
6、汰）”是另外一种可能 假定备选项的任意一个序列，X,Y,Z, 沿着这个序列，开始比较X和Y（少数服从多数），然后胜者再和Z相比，这样就可以得到一个“最大的” 对剩下的再进行这个过程，得到“次大的”,合理的个体行为 合理的聚合方式 不合理的群体结论？！,“议程设置”问题,积分制（另一种聚合群体意见的方式）,波达计数法（Borda Count, 1770） 假设有 N 个候选项，个体 i 对候选项的排序对应一种赋值，偏好排在第一的赋值 N-1；以此类推，最后一个赋值为 0 依据每个候选项得到的赋值和（积分），由高到低排序，从而形成群体偏好排序 注 若出现同样的积分，假定有一种外部约定的处理方法 个
7、体分数赋值显然还可以有其他各种方式,积分制,假设有2个个体（1, 2）面对4个备选项（A, B, C, D）；个体的排序以及群体的积分如下,积分制合理吗？,假设五个影评家（1, 2, 3, 4, 5）对两部影片（A, B）的排序,这看起来没问题，相当于在两个备选项上采取少数服从多数规则。,假设增加了一个低俗小说,本质上，5个人都认为低俗小说是最差的，于是,但个体4和5可能做一种策略性投票，既保持低俗小说总体最差，同时也使自己青睐的教父胜出,我们遇到了困难？,前面讨论的是“合理的个体偏好”“合理的聚合规则”不一定得到合理的结果，而且结果有可能被投票者“操纵” 我们尝试了不同的“聚合规则”，但看来
8、遇到了困难,一般地，我们可以想像表决系统为一个函数，它取若干排序表为输入，产生一个排序表为输出。我们问，为使这函数的输出“合理”，需要有什么要求。,表决系统示意图,在聚合规则上动脑筋似乎很难了 能否对个体偏好提进一步的要求？,聚合规则,个体序,群体序,理解“合理的个体行为”,假设（X, Y, Z）分别代表财政支出由低到高，我们来理解三个人表态的逻辑 个体1：钱花得越少越好 个体2：少了可能不够，多了可能浪费，中间较好；如果还不够，就多花点 个体3：？（行为很难解释，尽管在形式上也有个全序）,合理的个体行为 合理的聚合方式 不合理的群体结论,导致以“两两比较”“少数服从多数”原则得到的群体偏好不
9、传递：XY, YZ, ZX 即出现孔多塞悖论,单峰偏好 选举人的合理行为,设想备选项集合X2, X1, X5, XN的某种性质（P）有一种隐含的顺序（如支出预算数，个子高低，财富多少，考试分数高低，饭量的大小等），如下所列 PX1 PX2 P XN 所谓选举人的态度应该满足单峰偏好指的是 若Xi被他排在了第一位，则对于kji，Xj要排在Xk的前面；且对于ijk，Xj要排在Xk的前面 即选择了一个“最爱”后，对其他选项的偏爱程度应参照所关注的性质在两边随与这个最爱的距离下降 （左右两边相互之间没有要求）,单峰偏好（例）,候选项集合：A, B, C, D, E 所关注的性质：PA=5, PB=8,
10、 PC=4, PD=9, PE=6 即：PDPBPEPAPC 下面哪些候选项排序满足单峰偏好要求？,单峰偏好,定理：若所有选举人的排序都满足“单峰偏好”，则按照少数服从多数规则两两比较侯选项产生的群体偏好是完备且传递的。,如何证明这样一个结论？,“构造性方法”（constructive approach） 给出一种具有操作性的方法，基于任何满足条件的个体偏好集合，形成一种完备且传递的群体偏好（全序） 证明该群体偏好相对于给定的个体偏好集合而言是符合少数服从多数原则的,个体偏好完备且传递单峰,群体偏好完备且传递,少数服从多数,从单峰偏好个体排序形成群体排序,设 N个候选项，X1, X2, XN，
11、有某种特征序 M个（奇数）表决人，他们在上述侯选项序上的偏好是（按该特征序）单峰的 求一个群体排序表（即一个完备且传递的关系），其中若XiXj，则在M个个体排序中的大部分都有XiXj。 即两两都满足“少数服从多数”原则 下面是一个流程，说明存在性和具体结果,存在这样的群体排序即表明没出现孔多塞悖论,单峰偏好下群体排序的形成,要点：逐次找出“最大的”（群体意义） 记L1, L2, , LM为个体排序表，Li(1)为对应个体表中第一个（最大的）元素 将Li(1), i=1,2,M按照X1, X2, XN的特征序排列（一共M个，有的X可能有多次出现） 从如此排列的M个元素中取中间项为群体排序的第一项
12、（最大的元素） 从L1, L2, , LM中删除该元素，留下的依然是单峰排序表，接着可以取出第二个，等等,假设它们都满足以 X1 X2 X3 为特征序的单峰性 考察这些表中第一个元素按该序排列的情况：X1, X1, X2, X2, X3 X2是“中位项”，因此X2是第一个佼佼者 从每个表中删除它，继续这种中位项提取，得第二佼佼者，,例子： 个人排序表（M=5）,再看前面的例子,有3个个体和5个备选项，个体偏好排序如下：,不难验证，按照A, B, C, D, E的顺序，都是单峰的,选择“最大的”：A，B，C B,选择“次大的”：A，C，C C,选择“第三大的”：A，A，D A,类似地，相继得到D
13、，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个个体排序中的情形
14、，以少数服从多数原则胜出 从一个例子看，若排列情况如下： X1, X1, X2, X2, X3 因每个体排序都是“单峰”，从上列中间位置开始往右的个体排序中都有X*X2X1，而从它往左的个体排序中都有X*X2X3 。 即超过一半人认为X2X1，超过一半人认为X2X3 。,中间项胜出的一般图示,中位项定理的另一个角度的图示说明,给定一个满足单峰性质的个人排序集合（奇数）,对这M个表，按照它们第一项的内容，依据侯选项的特征序，重新排列，即下图中有: PXnPXmPXt,Xm是中位项，按照单峰要求，也就是，左边一半都会认为XmXt，同理，右边一半都认为XmXn,这就是说，对于任何其他X，总有一半以上
15、的人认为Xm要比较好些，也就是说，Xm要比所有其他侯选项都好（即它是最好的）。,Xm,Xm,Xt,Xn,要点小结,表决是一类基本制度，有丰富的应用场景 表决的功能是将若干个体意见综合为一个群体意见 “合理个体意见”“合理聚合规则”，不一定导致“合理群体意见” 孔多塞悖论：以两两比较关系为基础，个体偏好关系的传递性，在少数服从多数原则下，不一定产生群体关系的传递性 在要求个体偏好同时也满足单峰性质前提下，不会出现孔多塞悖论,基本内容,图论与社会网络 博弈论基础与应用 网络中的市场和策略性相互作用 信息网络和World Wide Web 网络动力学的总体模型 网络动力学的结构模型 制度及其聚和行为,弱关系的优势,结构平衡,从众的理性,小世界,三元闭包,物以类聚，人以群分,匹配市场,拍卖市场,中介市场,关系中的权力,反复改进原理,HITS&PageRank,阿罗不可能定理,布雷斯悖论,信息不对称的市场,流行性的起源,应用数学和计算机科学的基础知识，讨论社会学与经济学的经典问题。,
