第十二章群决策与社会选择 Group Decision-making and Social Choice Theory 主要参考文献56,118,169,185 512-1概述 为什么要研究群决策 A.在现实生活中 ·任何决策会影响一群人因此在公正、民主的社会中,重大的决策应尽量满足受该决 策影响的群众的愿望和要求.群众通过代表反映愿望和要求代表们构成各种委员会. ·行政机构中的领导班子 ·社会发展→信息和知识的积累及更新速度加快领导个人难以在掌和应付→智囊团和 咨询机构应运而生并广泛存在作用加强 委员会、代表大会、议会、协会、俱乐部,领导班子、组织,智囊团等等都是群群中的 成员各有偏好,要形成集体意见需要研究群决策和社会选择理论 B.世界上矛盾无处不在,人与人、组织与组织、国与国之间的矛盾如何解决如何避免冲 突升级需要研究协商、谈判、仲裁调解、合作对策等冲突分析方法因而冲突分析也是群 决策的主要研究内容 二、分类 涉及内容及解决办法 投票表决 社会选择社会选择函数 社会福利函数 委员会 激发创造性 集 专家判断采集意见 体 和 系统结构的探索 决 群体参与 仿真 策 实施与管理 一般均衡理论 递阶优化 群决策|多人决 组织机构决策 组织决策 管理 正规型 一般对策论 扩展型 特征函数 Nash 策冲 协商与谈判
12- 1 第十二章 群决策与社会选择 Group Decision-making and Social Choice Theory 主要参考文献 56，118，169，185 §12-1 概述 一、为什么要研究群决策 A. 在现实生活中 ● 任何决策会影响一群人,因此在公正、民主的社会中, 重大的决策应尽量满足受该决 策影响的群众的愿望和要求. 群众通过代表反映愿望和要求,代表们构成各种委员会. ● 行政机构中的领导班子 ● 社会发展→信息和知识的积累及更新速度加快,领导个人难以在掌和应付→智囊团和 咨询机构应运而生并广泛存在,作用加强. 委员会、代表大会、议会、协会、俱乐部, 领导班子、组织, 智囊团等等都是群,群中的 成员各有偏好, 要形成集体意见需要研究群决策和社会选择理论. B. 世界上矛盾无处不在, 人与人、组织与组织、国与国之间的矛盾如何解决,如何避免冲 突升级,需要研究协商、谈判、仲裁、调解、合作对策等冲突分析方法, 因而冲突分析也是群 决策的主要研究内容. 二、分类 涉及内容及解决办法 投票表决 社会选择 社会选择函数 社会福利函数 委员会 激发创造性 集 专家判断 采集意见 体 和 系统结构的探索 决 群体参与 仿真 策 Team theory 实施与管理 群 一般均衡理论 递阶优化 决 组织机构决策 组织决策 策 管理 ｜ 正规型 多 一般对策论 扩展型 人 特征函数 决 Nash 策 冲 协商与谈判 K-S
突分析 Mid-mid 均衡增量 主从对策与激励强制仲裁 仲裁与调解 最终报价仲裁 亚对策论 组合仲裁 三、社会选择的定义与方式 1.定义:(Luce& Raiffa) 社会选择就是根据社会中各成员的价值观及其对不同方案的选择产生社会的决策即把 社会中各成员对各种状况的偏好序集结成为单一的社会偏好模式 2.社会选择的常用方式 惯例、常规、宗教法规、职权、独裁者的命令、投票表决和市场机制」 其中 ●投票:少数服从多数,大多用于解决政治问题 ●市场机制本质是用货币投票,大多用于经济决策 ●独裁根据个人意志进行(取代社会选择 ●传统以惯例、常规、宗教法规等代替社会中各成员的意志 传统到独裁的演变:传统(无论惯例、常规还是宗教法规在开始时是社会上大部分公民 或成员认可的规则以及规定、法规),随着社会的发展,总有新的问题、新情况是原来的 规则(以及规定、法规所无法解决的解决这些新的问题新情况的新规则就要由社会上比 较有威望的某些人制订,这些人在解决新问题、新情况时就代替整个社会进行了选择只 要这些人不是以民主方式选举产生的,他们的权力就会逐渐增大,成为代替社会进行决策 的小团体这个小团体中最强有力的人物最终也就有可能成为独裁者 §122投票表决(选举 )Voting) 投票表决可分成两步:1.投票应简单易行 2.计票,应准确有效 非排序式投票表决 Non-ranked Voting Systems) (一)只有一人当选 1.候选人只有两个时:计点制 Spot vote) 投票每人一票计票:简单多数票 simple pluralit法则即相对多数) 2.候选人多于两个时 ①简单多数(相对多数) ②过半数规则绝对多数 Majority)第一次投票无人获得过半数选票时, 二次投票如法国总统选举 b.反复投票:i候选人自动退出如美国两党派的总统候选人提名竞选, i.得票最少的候选人的强制淘汰如奥运会申办城市的确定 12-2
12- 2 突 Mid-mid 分 均衡增量 析 主从对策与激励 强制仲裁 仲裁与调解 最终报价仲裁 亚对策论 组合仲裁 三、社会选择的定义与方式 1. 定义: ( Luce & Raiffa ) 社会选择就是根据社会中各成员的价值观及其对不同方案的选择产生社会的决策;即把 社会中各成员对各种状况的偏好序集结成为单一的社会偏好模式… 2. 社会选择的常用方式: 惯例、常规、宗教法规、职权、独裁者的命令、投票表决和市场机制. 其中: ●投票: 少数服从多数, 大多用于解决政治问题; ●市场机制:本质是用货币投票, 大多用于经济决策; ●独裁: 根据个人意志进行(取代)社会选择; ●传统:以惯例、常规、宗教法规等代替社会中各成员的意志. 传统到独裁的演变 : 传统(无论惯例、常规还是宗教法规)在开始时是社会上大部分公民 或成员认可的规则(以及规定、法规), 随着社会的发展, 总有新的问题、新情况是原来的 规则(以及规定、法规)所无法解决的,解决这些新的问题、新情况的新规则就要由社会上比 较有威望的某些人制订, 这些人在解决新问题、新情况时就代替整个社会进行了选择. 只 要这些人不是以民主方式选举产生的, 他们的权力就会逐渐增大, 成为代替社会进行决策 的小团体. 这个小团体中最强有力的人物最终也就有可能成为独裁者. §12.2 投票表决(选举)(Voting) 投票表决可分成两步: 1.投票,应简单易行 2.计票,应准确有效 一、非排序式投票表决(Non-ranked Voting Systems) (一)只有一人当选 1. 候选人只有两个时: 计点制(Spot vote) 投票: 每人一票;计票: 简单多数票(simple plurality)法则(即相对多数). 2. 候选人多于两个时 ① 简单多数(相对多数) ②过半数规则(绝对多数 Majority) 第一次投票无人获得过半数选票时, a.二次投票,如法国总统选举. b.反复投票: i.候选人自动退出,如美国两党派的总统候选人提名竞选; ii.得票最少的候选人的强制淘汰,如奥运会申办城市的确定
例12.1由11个成员组成的群,要在a、b、c、d四个候选人中选举一人设各成员心目 中的偏好序如下: 成员 234567891011 排序第一位 aaa bbbb ccc d 第二位ccc aaaaaaa 第三位 ddd cccc dd 第四位 bbb dddd bbb b 按简单多数票法则,b得4票当选 实际上虽然有4人认为b最好但是有7人认为b最差 虽然只有3人认为a最好但是其余8人认为a是第二位的 所以由a当选为宜 例12.2设各成员心目中的偏好序如下 成员i 1234567891011 排序第一位 bbbbbb aaaa a 第二位 aaaaaa ccc d d 第三位 ccc dddddd c c 第四位 ddd cccc bbb b 按简单多数票法则或过半数规则,b得6票当选 实际上虽然有6人认为b最好但是有5人认为b最差,虽然只有5人认为a最好但是其余 6人认为a是第二位的,所以由b当选未必合适 例12.3设各成员心目中的偏好序如下 成员 1234567891011 排序第一位 bbb cccc d d 第二位 aaaaaaaaa b d 第三位 d c d bbb d c b d 第四位 c d c ddd bb cc b 按过半数规则,第一次投票无人获得过半数选票c、b得票多,第二投票时6人认为c比b 优,c当选而在该问题中没有人认为a处于第二位以下,却有4人认为c最差 由上面三个例子可知,无论简单多数票法则、过半数规则还是二次投票都有不尽合理 之处 (二).同时选出二人或多人 1.单一非转移式投票表决( Single nontransferable voting) 投票人每人一票,得票多的候选人当选 如:日本议员选举采用选区制每选区当选人数超过2个,1890年起即用此法 2.复式选举( Multiple voting) 每个投票人可投票数-拟选出人数但对每个候选人只能投一票 弊端:在激烈的党派竟争中,实力稍强的党派将拥有全部席位因此该方法只能用于存在共 同利益的团体、组织内部,如党团组织和班干部的选举 12-3
12- 3 例12. 1 由 11 个成员组成的群, 要在 a、b、c、d 四个候选人中选举一人.设各成员心目 中的偏好序如下: 成员 i 1 2 3 4 5 6 7 8 9 10 11 排序 第一位 a a a b b b b c c c d 第二位 c c c a a a a a a a a 第三位 d d d c c c c d d d c 第四位 b b b d d d d b b b b 按简单多数票法则, b 得 4 票 当选. 实际上,虽然有 4 人认为 b 最好,但是有 7 人认为 b 最差; 虽然只有 3 人认为 a 最好,但是其余 8 人认为 a 是第二位的; 所以,由 a 当选为宜. 例12. 2 设各成员心目中的偏好序如下: 成员 i : 1 2 3 4 5 6 7 8 9 10 11 排序 第一位 b b b b b b a a a a a 第二位 a a a a a a c c c d d 第三位 c c c d d d d d d c c 第四位 d d d c c c c b b b b 按简单多数票法则或过半数规则, b 得 6 票当选. 实际上,虽然有 6 人认为 b 最好,但是有 5 人认为 b 最差; 虽然只有 5 人认为 a 最好,但是其余 6 人认为 a 是第二位的; 所以,由 b 当选未必合适. 例12. 3 设各成员心目中的偏好序如下: 成员 i : 1 2 3 4 5 6 7 8 9 10 11 排序 第一位 b b b c c c c d d a a 第二位 a a a a a a a a a b d 第三位 d c d b b b d c b d c 第四位 c d c d d d b b c c b 按过半数规则, 第一次投票无人获得过半数选票, c、 b 得票多,第二投票时,6 人认为 c 比 b 优, c 当选. 而在该问题中没有人认为 a 处于第二位以下,却有 4 人认为 c 最差. 由上面三个例子可知, 无论简单多数票法则、过半数规则 还是二次投票,都有不尽合理 之处. (二). 同时选出二人或多人 1.单一非转移式 投票表决(Single nontransferable voting) 投票人每人一票, 得票多的候选人当选. 如:日本议员选举采用选区制,每选区当选人数超过 2 个, 1890 年起即用此法. 2. 复式选举(Multiple voting) 每个投票人可投票数=拟选出人数 但对每个候选人只能投一票 弊端: 在激烈的党派竞争中,实力稍强的党派将拥有全部席位.因此该方法只能用于存在共 同利益的团体、组织内部, 如党团组织和班干部的选举
3.受限的选举( Limited voting) 每个投票人可投票数<拟选出人数对毎个候选人只能投一票 弊端:同上.1868年英国议会选举采用此法,1885年即取消 4.累加式选举( Cumulate voting) 每个投票人可投票数=拟选出人数这些选票由选举人自由支配可投同一候选人若干票 利:可切实保证少数派的利益 大多用于学校董事会的选举例英国(1870-1902)(注意公司董事会的选举与此不同) 5.名单制 (List system) 由各党派团体开列候选人名单,投票人每人一票,投给党团 此法于1899年用于比利时,以后被荷兰、丹麦、挪威和瑞典等国采用 计票分两种:(1).最大均值法 (2).最大余额法 例12.424000人投票选举5人,A、B、C、D四个党派分别得8700、6800、5200、3300 票,如何分配议席? (1)最大均值法 A党首先分得第一席第二席分给各党派时,各党派毎-议席的均值如下: 党派得票除数均值(每一议席的得票均值) A 8700 2 4350 B 6800 6800 5200 D 3300 由于B党的均值最大B党得第二席分第三席时各党派每一议席的均值如下: 党派得票除数均值 B 6800 5200 5200 C党得第三席,分第四席时各党派毎一议席的均值如下 党派得票除数 均值 B 6800 3400 5200 由于A党的均值最大,A党得第四席分第五席时各党派毎一议席的均值如下: 党派得票除数均值 A 8700 2900 B 6800 3400 5200 2600 3300 B党的均值最大B党得第五席.最后AB各得2席,C得1席 (2).最大余额法
12- 4 3. 受限的选举(Limited voting) 每个投票人可投票数＜拟选出人数 对每个候选人只能投一票 弊端: 同上. 1868 年英国议会选举采用此法, 1885 年即取消. 4. 累加式选举(Cumulate voting) 每个投票人可投票数=拟选出人数.这些选票由选举人自由支配,可投同一候选人若干票 利: 可切实保证少数派的利益. 大多用于学校董事会的选举,例:英国 (1870-1902).(注意: 公司董事会的选举与此不同.) 5. 名单制(List system) 由各党派团体开列候选人名单, 投票人每人一票, 投给党团. 此法于 1899 年用于比利时, 以后被荷兰、丹麦、挪威和瑞典等国采用. 计票分两种: ⑴. 最大均值法; ⑵. 最大余额法 例12. 4 24000 人投票,选举 5 人, A、B、C、D 四个党派分别得 8700、6800、5200、3300 票, 如何分配议席? (1)最大均值法: A 党首先分得第一席.第二席分给各党派时, 各党派每一议席的均值如下: 党派 得票 除数 均值(每一议席的得票均值) A 8700 2 4350 B 6800 1 6800 C 5200 1 5200 D 3300 1 3300 由于 B 党的均值最大 B 党得第二席.分第三席时 各党派每一议席的均值如下: 党派 得票 除数 均值 A 8700 2 4350 B 6800 2 3400 C 5200 1 5200 D 3300 1 3300 C 党得第三席, 分第四席时各党派每一议席的均值如下: 党派 得票 除数 均值 A 8700 2 4350 B 6800 2 3400 C 5200 2 2600 D 3300 1 3300 由于 A 党的均值最大, A 党得第四席.分第五席时各党派每一议席的均值如下: 党派 得票 除数 均值 A 8700 3 2900 B 6800 2 3400 C 5200 2 2600 D 3300 1 3300 B 党的均值最大 B 党得第五席. 最后 A B 各得 2 席 , C 得 1 席. ⑵. 最大余额法:
首先计算Q=NK的值:Q=240005=4800,用各党派得票数除以Q并计算余数: 党派得票除数分得席位余额 ABCD 4800 2000 5200 33004800 3300 按每4800票得一席A、B、C党各得一席,剩余2席,因为A、D两党的余额大最后A 党得2席,B、C和D党各得一席 可以证明,最大均值法对大党有利;最大余额法对小党有利 6.简单可转移式选举( Single nontransferable voting) 常常用于3-6个席位的选区投票人每人一票现况值Q=N(K+1),得票数大于Q的候选 人人选得票最少的候选人被淘汰,由未被淘汰的未当选候选人在下一轮中竞争剩余席位 仍以例12.4说明N=24000K=5,故Q-N(K+1)=24000/6=4000设各党派候选人的第 次投票得票数为: 候选人 A AA B2 得票数:4100410050041002700405011503300 其中,A1,A2,B1,C1第一次投票后可入选,A3被淘汰B2,C2,D1通过第二次 投票竟争最后一席这时Q=240002=12000.支持A党的可转移投票方向,他们在让谁入 选上有决定性影响 7.认可选举( Approval vote) 毎个投票人可投任意张选票,但他对毎个候选人只能投张票得票最多的前K个候 选人当选.如职称评定,评奖,评先进等 (三).其它投票表决(选举方法 资格认定 (1).候选人数M=当选人数K即等额选举,用于不存在竟竞争或不允许竞争的场合. (2).不限定入选人数如学位点评审职称评定,评奖等目的不是排序而是按某种标 准来衡量被选对象 2.非过半数规则 (1)2/3多数,例美国议会推翻总统否决需要2/3多数 (2)2/3多数→60%多数,例如希腊议会总统选举第一次需要2/3多数第二次要60%多 (3)3/4多数美国宪法修正案需要3/4州议会的批准 (4过半数支持,反对票少于1/3.例如1993年前我国博土生导师的资格认定 (5)一票否决,安理会常任理事国的否决权 二、偏好选举与投票悖论( Paradox of voting) 1.记号N={1,2,…,,n}表示群即投票人的集合, A= 备选方案(候选人)集合 12-5
12- 5 首先计算 Q=N/K 的值 : Q=24000/5=4800, 用各党派得票数除以 Q 并计算余数: 党派 得票 除数 分得席位 余额 A 8700 4800 1 3900 B 6800 4800 1 2000 C 5200 4800 1 400 D 3300 4800 0 3300 按每 4800 票得一席,A、B、C 党各得一席, 剩余 2 席,因为 A、D 两党的余额大,最后 A 党得 2 席, B、C 和 D 党各得一席. 可以证明, 最大均值法对大党有利; 最大余额法对小党有利. 6. 简单可转移式选举(Single nontransferable voting) 常常用于 3-6 个席位的选区.投票人每人一票. 现况值 Q=N/(K+1), 得票数大于 Q 的候选 人人选,得票最少的候选人被淘汰, 由未被淘汰的未当选候选人在下一轮中竞争剩余席位. 仍以例 12.4 说明. N=24000, K=5, 故 Q=N/(K+1)=24000/6=4000, 设各党派候选人的第 一次投票得票数为: 候选人: A 1 A 2 A 3 B 1 B 2 C 1 C 2 D 1 得票数: 4100 4100 500 4100 2700 4050 1150 3300 其中, A 1 ,A 2 , B 1 , C 1 第一次投票后可入选, A 3 被淘汰, B 2 , C 2 , D 1 通过第二次 投票 竞争最后一席.这时 Q=24000/2=12000. 支持 A 党的可转移投票方向, 他们在让谁入 选上有 决定性影响. 7. 认可选举( Approval vote ) 每个投票人可投任意张选票, 但他对每个候选人只能投一张票. 得票最多的前 K 个候 选人当选. 如职称评定, 评奖, 评先进等. (三). 其它投票表决(选举)方法 1. 资格认定 ⑴. 候选人数 M= 当选人数 K 即等额选举, 用于不存在竞争或不允许竞争的场合. ⑵. 不限定入选人数 如学位点评审,职称评定, 评奖等. 目的不是排序.而是按某种标 准来衡量被选对象. 2. 非过半数规则 ⑴2/3 多数, 例美国议会推翻总统否决需要 2/3 多数. ⑵2/3 多数60%多数, 例如希腊议会总统选举,第一次需要 2/3 多数,第二次要 60% 多 数. ⑶3/4 多数, 美国宪法修正案需要 3/4 州议会的批准. ⑷过半数支持, 反对票少于 1/3. 例如 1993 年前我国博士生导师的资格认定. ⑸一票否决, 安理会常任理事国的否决权. 二、偏好选举与投票悖论 ( Paradox of voting ) 1. 记号 N={ 1, 2,… ,n } 表示群,即投票人的集合; A={ a 1 , … ,a m } 备选方案(候选人)集合;
成员(投票人)i的偏好 群的排序 nk或Na,>ak)群中认为a,优于ak的成员数 采用上述记号,过半数规则可以表示为 对a,A∈A若nk>n则a,>a,;若nk=则a,~aa 2. borda法(1770年提出) 由每个投票人对m个候选人排序,排在第一位的得m-1分,排在第二位的得m-2分 根据各候选人所得总分多少确定其优劣 3. Condorcet原则(1785年提出) 寸候选人进行成对比较,若某个候选人能按过半数规则击败其它所有候选人,则称为 Condorcet候选人;若存在 Condorcet候选人,则由其当选 用上述记号表示即若nk>nkak∈A!a,},则a,当选 例12.5群由60个成员组成A={a,b,c},群中成员的态度是 23人认为 a>c>b(即a优于c,c优于b,a也优于b) 人认为 b>>a 16人认为 c>b>a 2人认为 cra a与b相比N(a>b)=25,N(b>a)=35因此有b>a 与c相比Na>c)=23,Nc>a)=37因此有c>ca b与c相比N(b>c)=19,Nc>b)=41因此有c>cb 由于候选人c能分别击败a与b,所以c是 Condorcet候选人由c当选 但是,常常不存在 Condorcet候选人 4.多数票循环(投票悖论) 例12.6若群中60个成员的态度是 23人认为 a>b>c 17人认为 b>c>a 2人认为 b>a>c 8人认为 c>b>a 10人认为 c>a>b 由于N(a>b)=33,N(b>a)=27因此有a>cb N(b>c)=42,Nc>a)=18因此有b>cc N(a>c)=25,N(c>a)=35因此有c>G 每个成员的偏好是传递的,但是按过半数原则集结得到的群的排序并不传递出现多数 票循环这种现象称作 Condorcet效应(也叫投票悖论) 5.出现 Condorcet效应的概率 成员数N 12-6
12- 6 i , ～ i 成员(投票人) i 的偏好; ～ G , G 群的排序. n jk 或 N(a j a k ) 群中认为 a j 优于 a k 的成员数 采用上述记号, 过半数规则可以表示为: 对 a j ,a k ∈A 若 n jk ＞n kj 则 a j G a k ; 若 n jk =n kj 则 a j ～G a k 2. Borda 法( 1770 年提出) 由每个投票人对 m 个候选人排序, 排在第一位的得 m-1 分, 排在第二位的得 m-2 分,… 根据各候选人所得总分多少确定其优劣. 3. Condorcet 原则( 1785 年提出) 对候选人进行成对比较, 若某个候选人能按过半数规则击败其它所有候选人, 则称为 Condorcet 候选人; 若存在 Condorcet 候选人,则由其当选. 用上述记号表示,即: 若 n jk ＞n kj ∨ a k ∈A\{ a j }, 则 a j 当选. 例12. 5 群由 60 个成员组成, A={ a, b, c }, 群中成员的态度是: 23 人认为 a c b (即 a 优于 c ,c 优于 b, a 也优于 b) 19 人认为 b c a 16 人认为 c b a 2 人认为 c a b a 与 b 相比 N(a b)=25, N(b a)=35 因此有 b G a a 与 c 相比 N(a c)=23, N(c a)=37 因此有 c G a b 与 c 相比 N(b c)=19, N(c b)=41 因此有 c G b 由于候选人 c 能分别击败 a 与 b, 所以 c 是 Condorcet 候选人,由 c 当选. 但是,常常不存在 Condorcet 候选人. 4. 多数票循环(投票悖论) 例12. 6 若群中 60 个成员的态度是: 23 人认为 a b c 17 人认为 b c a 2 人认为 b a c 8 人认为 c b a 10 人认为 c a b 由于 N(a b)=33, N(b a)=27 因此有 a G b N(b c)=42, N(c a)=18 因此有 b G c N(a c)=25, N(c a)=35 因此有 c G a 每个成员的偏好是传递的, 但是按过半数原则集结得到的群的排序并不传递,出现多数 票循环,这种现象称作 Condorcet 效应(也叫投票悖论) 5. 出现 Condorcet 效应的概率 成员数 N : 3 5 7 11 15 25 ∞
方案数m=30556069407500798082084308 411114 1755 5 1620 2513 6 8 114887 7914 三、策略性投票(操纵性) 1.小集团控制群 例百人分蛋糕 2.谎报偏好而获益 例127群由30个成员组成A={ab,c},群中成员的态度是 14认为 a>b>c 4人认为 b>a>c 4人认为 b>c>a 8人认为 c>b>a 根据 Borda法和 Condorcet原则都应由b当选,但是,若认为a>b>c的14人中有8人撒谎, 称他们认为a>c>b,则按 Borda法,将由a当选 3.程序(议程)问题例12.6所述问题后参加表决的方案获胜 四、衡量选举方法优劣的标准 ①能否充分利用各成员的偏好信息 ②若存在 Condorcet候选人,应能使其当选 ③能防止策略性投票 §123社会选择函数 引言 1.仍以例12.5为例群由60个成员组成A={a,b,c},群中成员的态度是 23人认为 19人认为 b>c> 16人认为 c>>a IA. Gibbard, Manipul ation of vot ing schemes: a general result, 1973, Econometrica (41)91-103 2 M. A. Satterthweitz, Strategy proofness and Arrew's conditions, 1975,J.Eco Theor y(10)187-217 12-7
12- 7 方案数 m= 3 .0556 .0694 .0750 .0798 .082 .0843 .0877 4 .111 .14 .15 .1755 5 .16 .20 .22 .2513 6 .20 .25 .27 .3152 8 .4152 10 [1] .4887 15 .6087 20 .6811 30 .7914 49 .8405 三、策略性投票(操纵性) 1.小集团控制群 例: 百人分蛋糕 2. 谎报偏好而获益 例 12.7 群由 30 个成员组成, A={ a, b, c }, 群中成员的态度是: 14 认为 a b c 4 人认为 b a c 4 人认为 b c a 8 人认为 c b a 根据 Borda 法和 Condorcet 原则,都应由 b 当选, 但是, 若认为 a b c 的 14 人中有 8 人撒谎, 称他们认为 a c b , 则按 Borda 法, 将由 a 当选. 3. 程序(议程)问题 例 12.6 所述问题: 后参加表决的方案获胜. 四、衡量选举方法优劣的标准 ①能否充分利用各成员的偏好信息 ②若存在 Condorcet 候选人,应能使其当选. ③能防止策略性投票 §12.3 社会选择函数 一、引言 1. 仍以例 12.5 为例:群由 60 个成员组成, A={ a, b, c }, 群中成员的态度是: 23 人认为 a c b 19 人认为 b c a 16 人认为 c b a 1 A. Gibbard, Manipulation of voting schemes: a general result, 1973,Econometrica (41)91-103. 2 M. A. Satterthweitz, Strategy proofness and Arrew’s conditions , 1975, J. Eco. Theory (10)187-217
人认为 c>a>b 根据 Condorcet原则 当选 根据简单多数规则 当选 根据过半数(二次投票规则b当选 该例中一共只有三个候选人,采用不同选举方法时,这些候选人都有可能当选.那么这 些方法中究竟何者合理?据何判断选举方法的合理性? 2例12.6表明多数票循环不可避免,问题是:出现多数票循环时该谁当选」 研究社会选择问题的理论家提出:应该采用某种与群中成员偏好有关的数量指标来反映群 即社会对各方案的总体评价.这种数量指标称为社会选择函数 社会选择函数的几个性质 0.记号 在对xy比较时 1若 若 1若 群中各成员的偏好分布D=(D1…Dn) 偏好分布的集合 -1,0,1} 社会选择函数F(D)=f(D1…Dn)VD∈D 即F:{-1,0,1}"→{-1,0,1} 明确性( Decisiveness) D≠0→F(D)≠0 2.中性( Neutralit又称对偶性对侯选人的公平性 3.匿名性( Anonymity)又称平等原则各成员的权力相同 f( D )=f(D 其中σ是(1,…,n)的新排列 4.单调性( Monotonicity)又称正的响应 若D≥D’则F(D)≥F(D”) 5.—致性( Unanimity)又称 Weak pareto性 6.齐次性( Homogeneity) 对任意正整数mF(mD)=F(D) 7. Pareto性 D,∈{1,0} for alli and d= I for some k→F(D)= D=0 for all I→F(D)=0 社会选择函数 12-8
12- 8 2 人认为 c a b 根据 Condorcet 原则 c 当选 根据简单多数规则 a 当选 根据过半数(二次投票)规则 b 当选 该例中一共只有三个候选人, 采用不同选举方法时, 这些候选人都有可能当选. 那么这 些方法中究竟何者合理?据何判断选举方法的合理性? 2 例 12.6 表明多数票循环不可避免, 问题是: 出现多数票循环时该谁当选? 研究社会选择问题的理论家提出：应该采用某种与群中成员偏好有关的数量指标来反映群 (即社会)对各方案的总体评价. 这种数量指标称为社会选择函数. 二、社会选择函数的几个性质 0. 记号 在对 x,y 比较时 1 若 x i y D i = 0 若 x ～ i y -1 若 y i x 群中各成员的偏好分布 D = ( D 1 ,… ,D n ) 偏好分布的集合 Ð = { -1, 0, 1 } n 社会选择函数 F(D) = f( D 1 ,… ,D n ) D ∈ Ð 即 F : { -1, 0, 1 } n → { -1, 0, 1 } 1. 明确性 (Decisiveness) D≠ 0 → F(D) ≠ 0 2. 中性 (Neutrality)又称对偶性 对侯选人的公平性 f( -D 1 ,… ,-D n ) = - f( D 1 ,… ,D n ) 3. 匿名性 (Anonymity) 又称平等原则 各成员的权力相同 f( D 1 ,… ,D n ) = f( D (1) ,… ,D (n) ) 其中σ 是 (1, … ,n)的新排列 4. 单调性 (Monotonicity)又称正的响应 若 D ≥ D’ 则 F ( D )≥ F ( D’ ) 5. 一致性 (Unanimity)又称 Weak Pareto 性 f ( 1, 1,… , 1) = 1 or f ( -1, -1,… , -1) = -1 6. 齐次性(Homogeneity) 对任意正整 数 m F ( mD ) = F ( D ) 7. Pareto 性 D i ∈ { 1, 0 } for all I and D = 1 for some k → F ( D ) = 1 D i = 0 for all I → F ( D ) = 0 三、社会选择函数
1. Condorcet-函数 f。(x)=mnN(x>;y) y∈A\{x} f。(.)值愈大愈优 例12.6群中60个成员的态度是 23人认为 a>b>c 17人认为 b>c>a 2人认为 b 8人认为 b 0人认为 c>a>b N(a>b)=33Na>c)=25因此f(a)=25 N(b>a)=27,Nb>c)=42,因此f(b)=27 N(c>a)=18N(c>a)=35,因此f(c)=18 Condorcet-函数值还可以用下法求得 根据各方案成对比较结果列出表决矩阵 矩阵中各行最小元素:2 18 即 Condorcet-函数值 Condorcet函数满足性质1~ 2. Borda-函数 f。(x)=∑Nx>,y) f,(x)即表决矩阵中ⅹ各元素之和,f,()值愈大愈优 例2.6中方案abc的 borda-函数值分别是58,69,53,,b>a>。c borda-函数满足性质1~6 3 Copeland-函数 根据各方案两两比较的胜负次数的差来定 fc(x)=M{yy∈A且x>cy}-M{yy∈A且y>x} fc()值愈大愈优例126中方案abc的 Copeland函数值均为0,三者平局 Copeland函数满足性质1~6 Nanson函数 用 borda-函数求解,每次淘汰 Borda函数值最小的方案 A+1=A,X∈A,;fb(x)≤f,()且对某些yfb(x)。b>。c
12- 9 1. Condorcet-函数 f c (x) = min yA\{x} N( x i y ) f c ( .) 值愈大愈优. 例12. 6 群中 60 个成员的态度是: 23 人认为 a b c 17 人认为 b c a 2 人认为 b a c 8 人认为 c b a 10 人认为 c a b N(a b)=33, N(a c)=25 因此 f c ( a ) = 25 N(b a)=27, N(b c)=42, 因此 f c ( b ) = 27 N(c a)=18, N(c a)=35, 因此 f c ( c ) = 18 ∴ b G a G c Condorcet-函数值还可以用下法求得: 根据各方案成对比较结果列出表决矩阵 -- 33 25 矩阵中各行最小元素: 25 N = 27 -- 42 27 35 18 -- 18 即 Condorcet-函数值. Condorcet-函数满足性质 1~6. 2. Borda-函数 f b (x) = yA x \{ } N( x i y ) f b (x) 即表决矩阵中 x 各元素之和, f b ( .) 值愈大愈优. 例12. 6 中方案 a ,b ,c 的 Borda-函数值分别是 58, 69, 53, ∴ b G a G c Borda-函数满足性质 1~6. 3. Copeland-函数 根据各方案两两比较的胜负次数的差来定 f cp (x) = M{y: y ∈A 且 x G y}- M{y: y ∈A 且 y G x} f cp ( .) 值愈大愈优. 例 12.6 中方案 a ,b ,c 的 Copeland 函数值均为 0, 三者平局. Copeland-函数满足性质 1~6. 4. Nanson 函数 用 Borda-函数求解, 每次淘汰 Borda-函数值最小的方案: 即: A 1 = A , A j+1 = A j \{ x∈A j ; f b (x) ≤ f b (y),且对某些 y f b (x) ＜f b (y) } 直到 A j+1 = A j 为止. 例12. 6 中 f b (c) 的 Borda-函数值最小, ∴ A 2 = A 1 \{ c } = { a, b } A 3 = A 2 \{ b } = { a } ∴ a G b G c
anson函数不满足性质(4 5. Dodgson函数( C.J. Dodgson,英,1832-1898) 使某个候选人成为 Condorcet候选人需要N中成员改变偏好的总选票数 N个成员m个候选人记nk=N(a,>;ak n为偶数时n=n2n为奇数时n=(n+1)2nn=0 no-no 」=1,…,m 例126中,abc的 Dodgson函数值分别为5,3,12,b>ca>cc Dodgson函数不满足(4) 6 Kemeny函数 使社会排序与各成员对方案的偏好序有最大的一致性 首先定义 ①社会选择排序矩阵L={l/k} a A上的每一线性序都对应一个L 记 N(a = n(ak N ②比例矩阵M={mk m ik=(n+nk/2)/n ③投票矩阵E=MM 义= 即,群中认为a,>ak的成员的比例与群的排序1k的内积它反映群的排序与成员排序 的一致性 Kemeny函数fk=max 7Cook- Seiford函数 设成员i把方案j排在r位,方案j的群体序为K 则成员I与群体序的总偏差 Iri-KI 各成员排序与群体序的总偏差dk=∑∑|rnKl 数学规划min∑∑d 12-10
12- 10 Nanson 函数不满足性质(4). 5. Dodgson 函数(C.J.Dodgson, 英，1832— 1898) 使某个候选人成为 Condorcet 候选人需要 N 中成员改变偏好的总选票数. N 个成员,m 个候选人 记 n jk = N (a j i a k ) n 为偶数时 n0 =n/2 n 为奇数时 n0 =(n+1)/2 n jj = 0 f (a j ) = |n n | (n n ) jk jk k m 0 0 1 − + − 2 = j=1,… ,m 例 12.6 中, a,b,c 的 Dodgson 函数值分别为 5, 3, 12, ∴ b G a G c Dodgson 函数不满足 (4). 6.Kemeny 函数 ·使社会排序与各成员对方案的偏好序有最大的一致性. 首先定义： ①社会选择排序矩阵 L = {l jk } 1 a j G a k l jk = 0 a j ～ G a k -1 a k G a j A 上的每一线性序都对应一个 L 记 n jk = N (a j G a k ) nkj = N (a k G a j ) n jk * = N (a j ～ G a k ) ②比例矩阵 M = {m jk } m jk = ( n jk + n jk * /2)/n ③投票矩阵 E = M-M T e jk = n n n n jk kj − 定义 = j k e jk l jk 即, 群中认为 a j a k 的成员的比例与群的排序 l jk 的内积, 它反映群的排序与成员排序 的一致性. Kemeny 函数 f k = max 。 7.Cook-Seiford 函数 设成员 i 把方案 j 排在 r ij 位, 方案 j 的群体序为 K 则成员 I 与群体序的总偏差 : j | r ij -K | 各成员排序与群体序的总偏差 d jk = i j | r ij -K | 数学规划 min j k d jk p jk s.t. j p jk = 1