第十一章博弈模型课件.ppt

《第十一章博弈模型课件.ppt》由会员分享，可在线阅读，更多相关《第十一章博弈模型课件.ppt（80页珍藏版）》请在三一办公上搜索。

1、第十一章 博弈模型,11.1 进攻与撤退的抉择11.2 让报童订购更多的报纸11.3 “一口价”的战略 11.4 不患寡而患不均 11.5 效益的合理分配 11.6 加权投票中权力的度量,第十一章 博弈模型11.1 进攻与撤退的抉择,单一决策主体,决策变量目标函数约束条件,决策主体的决策行为发生直接相互作用 (相互影响),博弈模型,非合作博弈,合作博弈,三要素,多个决策主体,决策问题（Decision Problem）,军事、政治、经济、企业管理和社会科学中应用广泛,单一决策主体决策变量目标函数约束条件决策主体的决策行为发生直,1944年6月初，盟军在诺曼底登陆成功. 到8月初的形势：,背景,

2、11.1 进攻与撤退的抉择,双方应该如何决策 ？,1944年6月初，盟军在诺曼底登陆成功.背景11.1 进,模型假设,博弈参与者为两方（盟军和德军）,盟军有3种使用其预备队的行动：强化缺口，原地待命，东进；德军有2种行动：向西进攻或向东撤退.,博弈双方完全理性，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多.,完全信息静态博弈,共同知识(以上信息双方共有),双方同时做出决策,模型假设 博弈参与者为两方（盟军和德军） 盟军有3种使用其预,博弈模型,博弈参与者集合N=1,2(1为盟军，2为德军),用u1(a1，a2)表示对盟军产生的结果，即净胜场次，称为盟军的效用函数.,盟军行

3、动a1 A1=1,2,3(强化缺口/原地待命/东进)； 德军行动a2 A2=1,2(进攻/撤退)。 (行动：即纯战略),支付矩阵（Payoff Matrix）,完全竞争: 零和博弈 (常数和博弈),u2(a1，a2)对应 -M,博弈模型 博弈参与者集合N=1,2(1为盟军，2为德军),博弈的解的概念：纳什均衡 (NE: Nash Equilibrium),不存在(纯)NE,(纯战略)纳什均衡,Nash: 1994年获诺贝尔经济学奖,NE: 单向改变战略不能提高自己效用，即每一方的战略对于他方的战略而言都是最优的,称为最优反应.,(纯)NE: a*=(a1*, a2*) =(2, 2),非常数和

4、博弈(双矩阵表示),博弈的解的概念：纳什均衡 (NE: Nash Equilib,混合战略（策略：Strategy),盟军的混合战略集,期望收益,盟军,德军,S1=p=(p1, p2, p3) |,德军的混合战略集,S2= q=(q1, q2) |,完全信息静态博弈有限博弈矩阵博弈 (2人)零和博弈常数和博弈,混合战略（策略：Strategy) 盟军的混合战略集 期望收,模型求解,理性推理：不管自己怎么做，另一方总是希望尽量使自己得分尽量低.（二人零和博弈，完全竞争）,盟军,德军,线性规划,从一个给定的战略中期望得到的赢得，总是采用该策略时他们可能得到的最坏的赢得！,盟军可以用min pM来衡

5、量策略p的好坏,max U1(p) = min pM,min U2(q) = max MqT,德军可以用max MqT来衡量策略q的好坏,(p*, q*): 混合(策略)纳什均衡(Mixed NE),p2*=3/5，p3*=2/5,q1*=1/5，q2*=4/5,最优值均为2/5,模型求解理性推理：不管自己怎么做，另一方总是希望尽量使自己得,占优(dominate)：盟军的行动2占优于1 （前面的非常数和博弈M类似）,混合策略似乎不太可行! 但概率可作为参考. -现实：盟军让预备队原地待命（行动2），而德军没有选择撤退（行动2），结果德军大败.,模型评述,博弈规则至关重要的，如参与人决策的时间

6、顺序、决策时拥有哪些信息等.,多人(或非常数和)博弈问题，一般不能用上面的线性规划方法求解，而通过纳什均衡的定义求解.,占优(dominate)：盟军的行动2占优于1 混合策略似乎,小结：博弈模型的基本要素,参与人,理性假设,行动顺序（静态、动态）,信息结构（完全、不完全）,行动空间（及战略空间）,效用函数,参与者完全理性(最大化效用),其他因素,纳什均衡,单向改变战略不能提高自己效用,小结：博弈模型的基本要素 参与人 理性假设 行动顺序（静态、,11.2 让报童订购更多的报纸,报童模型回顾,订购价w，零售价p，处理价v（pwv0）需求量：密度函数f(x)、分布函数F(x), F(0)=0,订

7、购Q份报纸，期望销售量为,期望存货量,期望利润,最优订购量Qr,Qr(w),11.2 让报童订购更多的报纸 报童模型回顾订购价w，零售,11.2 让报童订购更多的报纸,问题,假设报社报纸成本价为c，wcv, w*,完全信息动态博弈：常称Stackelberg Game (两阶段) 子博弈完美均衡: (w*，Qr(w),一般w*c Qr(w*) Q* 整体利润有损失,能否改善(协调)？,假设报社与报童联合，整体利润最大,11.2 让报童订购更多的报纸 问题假设报社报纸成本价为,价格折扣协议模型,折扣方案wd(Q) 下，报童效用(期望利润),达到协调,假设报社与报童联合，整体期望利润,关于Q的减函

8、数(非线性),，报童利润 ，报社利润利润的任意分配比例都可达到,价格折扣协议模型 折扣方案wd(Q) 下，报童效用(期望利润,模型一 回收价格协议,原订货量,达到协调,整体最优,b，报童利润 ，报社利润利润的任意分配比例都可达到,回收价b (pwbv),回收协议模型,模型一 回收价格协议 原订货量达到协调整体最优b,模型二 回收数量协议,报社回收,达到协调,报童回收,，报童利润, 报社利润; 利润任意分配都可达到,按批发价回收，比例为,报童利润,回收协议模型,模型二 回收数量协议 报社回收 达到协调报童回收，,模型评述,协议参数的确定：不能单方决定双方谈判（合作博弈）,还有很多其他类型的协议，

9、也可以达到协调,一种更简单的协议批发价w成本c收取一定加盟费,如何评价比较协议的优缺点？,是否能达到协调,是否能任意分配利润,协议执行成本有多高,模型评述 协议参数的确定：还有很多其他类型的协议，也可以达到,11.3 “一口价”的战略,背景,为了节省“讨价还价”时间，考虑“一口价”模式.,双方同时报价：若买价卖价，则以均价成交; 否则不成交.,问题,双方应如何报价？,双方总能成交吗？（效率估计）,“讨价还价”很浪费买卖双方的宝贵时间.,11.3 “一口价”的战略 背景 为了节省“讨价还价”时,模型假设与建立,卖方知道物品对自己的价值，但买方不知道.,买方知道物品对自己的价值，但卖方不知道.,双

10、方都知道（如猜出）对方价值的分布信息.,卖方价值vs, 买方价值vb, 均服从U0,1 (均匀分布),卖方报价ps, 买方报价pb, pb ps时成交价p (pb+ps)/2,成交效用：卖方U1=p- vs, 买方U2= vb p; 不成交: 0,双方完全理性(最大化自己的期望效用 ).,以上为双方的共同知识.,模型假设与建立 卖方知道物品对自己的价值，但买方不知道. 买,卖方报价ps ps(vs)买方报价pb pb(vb),双方战略,战略组合( ps(vs), pb(vb) 何时构成均衡？,定义在0，1区间上、取值也在0，1区间上的非减函数.,不完全信息静态博弈（静态贝叶斯博弈）,贝叶斯纳什

11、均衡,单向改变战略不能提高自己效用.,信息非对称（不完全信息）,模型假设与建立,卖方报价ps ps(vs)双方战略战略组合( ps(vs),均衡条件,具体战略(函数)形式不同，均衡就可能不同.,单一价格战略,卖方：买方：,双方战略互为最优反应，所以构成贝叶斯纳什均衡！,模型假设与建立,均衡条件具体战略(函数)形式不同，均衡就可能不同.单一价格战,单一价格战略效率为,x(1-x)/0.50.5,x0.5效率最大(1/2),对给定的(vs, vb)，当vsvb时称为交易是有利的.,在给定的战略组合下，有利的全部交易中能够实际发生交易的比例称为该战略的交易效率.,单一价格战略,单一价格战略效率为x(

12、1-x)/0.50.5x0.5对给,线性价格战略,卖方报价ps(vs) as+csvs;买方报价pb(vb) ab+cbvb,双方战略互为最优反应，构成贝叶斯纳什均衡！,买方：,买方: (同理),线性价格战略卖方报价ps(vs) as+csvs;双方战,不成立时也适用（不唯一）,线性价格战略,vb,vs1pb(vb)ps(vs)3/43/41/4pb,评述,效率（线性价格战略）,效率为1/4*3/4 =9/16,可以证明，线性均衡效率最大.,不存在使所有有利的交易都成交的均衡战略组合.,信息的不完全（非对称信息）降低了交易效率.,包含了交易价值(交易给双方带来的效用之和，即vbvs)大于1/4

13、的所有有效交易.,评述效率（线性价格战略）效率为可以证明，线性均衡效率最大.不,11.4 不患寡而患不均,最后通牒博弈(Ultimatum Game),问题,甲乙两人就分配笔钱（如100元）进行博弈.,甲首先提出分配方案 (分给乙的钱: s).,现实中的情况果真如此吗？多数s总额的4050%s越小，越容易被乙拒绝,完全信息动态博弈：均衡结果是(s=0,乙接受); 如果要求严格均衡，则s=分钱.,如果乙接受，则按此分配 ；否则双方什么也得不到.,公平：利他互惠？,自私：理性非理性？,11.4 不患寡而患不均最后通牒博弈(Ultimatu,模型假设与建立,1. 每个参与者都喜欢对所有参与者公平的结

14、果；,2. 每个参与者自己受到不公平对待时的“愤怒”，胜过其他参与者受到不公平对待时的“愧疚”,否则，xixj=1-xi时，i(x)xi-i (xi -xj)= i -(2i -1)xi关于xi的系数非正 （过分“愧疚” ）,效用函数,财富总额为1接受提议：甲乙所得x1=1-s, x2= s；否则：x1=x2=0,模型假设与建立1. 每个参与者都喜欢对所有参与者公平的结果；,模型求解,如果不接受，则x1=x2=0; U1(s)=U2(s)=0 .,若s1/2,则x2 x1,乙的最优反应,乙的最优反应（给定s）,如果接受，则x1=1-s, x2=s.,若s1/2,则x2x1,U2(s)0,1/2

15、0,易知,(s1/2, 两者一致),模型求解如果不接受，则x1=x2=0; U1(s)=U2(s,模型求解,Case 1: 甲知道乙的2,若s1/2,则x2 x1,甲的决策,s=1/2时达到最大值1/2,甲的决策(只需考虑乙接受情形),均衡: (s*,接受),s*严格小于50%; 是乙的“愤怒”系数2的增函数.,模型求解Case 1: 甲知道乙的2 若s1/2,则x2,模型求解：甲的决策,Case 2: 甲不知道乙的2, 但知道2知道分布F(2),若s1/2,则x2 x1,甲的决策,若s1/2,则x2 x1,U1(s)=1-s-1(2s-1) 同前,期望效用,乙接受概率,s*,模型求解：甲的决

16、策Case 2: 甲不知道乙的2, 但知道,模型解释,甲永远不会提出大于/的方案s,乙拒绝过小的方案s,很好地解释了实际中的最后通牒博弈,乙接受概率随s增加不减,参考文献,模型解释 甲永远不会提出大于/的方案s 乙拒绝过小的方案,11.5 效益的合理分配,例,甲乙丙三人合作经商，若甲乙合作获利7元，甲丙合作获利5元，乙丙合作获利4元，三人合作获利11元. 又知每人单干获利1元.问三人合作时如何分配获利？,记甲乙丙三人分配为,解不唯一,(5，3，3)(4，4，3)(5，4，2),11.5 效益的合理分配例甲乙丙三人合作经商，若甲乙合作获,(1) Shapley合作对策, I,v n人合作对策，v

17、特征函数,n人从v(I)得到的分配，满足,v(s) 子集s的获利,(1) Shapley合作对策 I,v n人合作对,公理化方法,s子集 s中的元素数目， Si 包含i的所有子集,由s决定的“贡献”的权重, i 对合作s 的“贡献”,Shapley合作对策,公理化方法s子集 s中的元素数目， Si 包含i的所,三人(I=1,2,3)经商中甲的分配x1的计算,1/3 1/6 1/6 1/3,1 1 2 1 3 I,1 7 5 11,0 1 1 4,1 6 4 7,1/3 1 2/3 7/3,x1=13/3,类似可得 x2=23/6, x3=17/6,1 2 2 3,三人(I=1,2,3)经商中甲

18、的分配x1的计算 1/3,合作对策的应用 污水处理费用的合理分担,污水处理，排入河流.,三城镇可单独建处理厂，或联合建厂(用管道将污水由上游城镇送往下游城镇).,Q污水量，L管道长度建厂费用P1=73Q0.712管道费用P2=0.66Q0.51L,合作对策的应用 污水处理费用的合理分担20km38km河,污水处理的5 种方案,1）单独建厂,总投资,2）1, 2合作,3）2, 3合作,4）1, 3合作,总投资,总投资,合作不会实现,污水处理的5 种方案1）单独建厂总投资2）1, 2合作3）2,5）三城合作总投资,D5最小, 应联合建厂,建厂费：d1=73(5+3+5)0.712=453 12 管

19、道费：d2=0.66 50.51 20=30 23 管道费：d3=0.66 (5+3)0.51 38=73,D5,城3建议：d1 按 5:3:5分担, d2,d3由城1,2担负,城2建议：d3由城1,2按 5:3分担, d2由城1担负,城1计算：城3分担 d15/13=174C(1),不同意!,D5如何分担？,5）三城合作总投资D5最小, 应联合建厂 建厂费：d1=73,特征函数v(s)联合(集s)建厂比单独建厂节约的投资,三城从节约投资v(I)中得到的分配,Shapley合作对策,特征函数v(s)联合(集s)建厂比单独建厂节约的投资三城,计算城1从节约投资中得到的分配x1,x1 =19.7,

20、城1 C(1)-x1=210.4, 城2 C(2)-x2=127.8, 城3 C(3)-x3=217.8,x2 =32.1, x3=12.2,x2最大，如何解释？,计算城1从节约投资中得到的分配x11,优点：公正、合理，有公理化基础。,如n个单位治理污染, 通常知道第i方单独治理的投资yi 和n方共同治理的投资Y, 及第i方不参加时其余n-1方的投资zi (i=1,2, ,n). 确定共同治理时各方分担的费用.,其他v(s)均不知道, 无法用Shapley合作对策求解,Shapley合作对策小结,若定义特征函数为合作的获利(节约的投资)，则有,缺点：需要知道所有合作的获利，即要定义I=1,2,

21、n的所有子集(共2n-1个)的特征函数，实际上常做不到.,优点：公正、合理，有公理化基础。如n个单位治理污染, 通常知,求解合作对策的其他方法,例. 甲乙丙三人合作经商，若甲乙合作获利7元，甲丙合作获利5元，乙丙合作获利4元，三人合作获利11元. 问三人合作时如何分配获利？,设只知道无 i 参加时n-1方合作的获利全体合作的获利求解合,（1）协商解,将剩余获利 平均分配,模型,以n-1方合作的获利为下限,求解, xi 的下限,（1）协商解11将剩余获利 平,（2）Nash解,为现状点（谈判时的威慑点）,在此基础上“均匀地”分配全体合作的获利B,模型,（2）Nash解 为现状点（谈判时的威慑点）

22、在此基础上,（3）最小距离解,模型,第i 方的边际效益,若令,（3）最小距离解模型 第i 方的边际效益若令3）最小距离解,（4）满意解,di现状点(最低点)ei理想点(最高点),模型,（4）满意解di现状点(最低点)模型4）基于满意度的解,（5）Raiffi 解,与协商解x=(5,4,2)比较,（5）Raiffi 解与协商解x=(5,4,2)比较,求解合作对策的6种方法（可分为三类）,Shapley合作对策,A类,B类,协商解,Nash解,最小距离解,求解合作对策的6种方法（可分为三类）Shapley合作对策A,例：有一资方(甲)和二劳方(乙,丙), 仅当资方与至少一劳方合作时才获利10元，应

23、如何分配该获利？,Raiffi解,C类,例：有一资方(甲)和二劳方(乙,丙), 仅当资方与至少一劳,B类：计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者.,C类： 考虑了分配的上下限，又吸取了Shapley的思想，在一定程度上保护弱者.,A类：公正合理；需要信息多，计算复杂.,求解合作对策的三类方法小结,B类：计算简单，便于理解，可用于各方实力相差不大的情况；一般,11.6 加权投票中权力的度量,背景,“一人一票”显示投票和表决的公正.,股份制公司每位股东投票和表决权的大小由所占有的股份多少决定.,一些国家、地区的议会、政府的产生，由所属的州、县等各个区域推出的代表投票决

24、定.,代表投票的权重取决于所代表区域的人口数量.,经济或政治机构权力的分配,11.6 加权投票中权力的度量 背景“一人一票”显示,背景,典型案例: 美国总统选举实行的选举人制度,美全国50个州和华盛顿特区共538张选举人票.,获选举人票数一半以上的总统候选人当选总统.,各州选举人票数与该州在国会的参、众议员数相等.,参议员每州两位，众议员人数由各州人口比例确定.,各州人口悬殊巨大使各州选举人票数相差很大.,(如加利福尼亚州选举人票55张，阿拉斯加州只3张),背景典型案例: 美国总统选举实行的选举人制度 美全国50个,背景,典型案例: 美国总统选举实行的选举人制度,总统候选人在各州内进行普选，获

25、得相对多数选票的候选人得到该州的全部选举人票.,48个州和华盛顿特区都实行“胜者全得” ：,在加利福尼亚州以微弱多数普选获胜的总统候选人可得到全部55张选举人票.,若有几个人口多的州如此，在选举人投票中就可能使各州累计得票最多的候选人反而不能获胜.,选举结果违反全国多数人的意愿.,2000年布什与戈尔进行的竞选中，戈尔最终败给布什！,背景典型案例: 美国总统选举实行的选举人制度 总统候选人在,问题,由若干区域(如省、县等)组成的机构中，每区代表的数量按照人口比例分配，进行投票选举和表决时，每区的全体代表投相同的票.,每区各派一位代表(投票人)，按照他们所代表的各区人口比例赋予投票的权重.,如何

26、度量每位代表的投票对最终结果的影响力(权力).,介绍两种合理的、度量权力的数量指标. 通过实例给出它们的应用. 调整投票人的权重使其权力大致与代表的人口成比例.,加权投票中权力的度量,背景,问题由若干区域(如省、县等)组成的机构中，每区代表的数量按照,加权投票与获胜联盟,例1 一县5区(A, B, C, D, E )人口为 60, 20, 10, 5, 5 (千人).,每区一位代表按人口比例分配其投票权重为12, 4, 2, 1, 1.,按简单多数规则(权重之和超过总权重一半)决定投票结果.,将A区分成人口相等的3个子区A1，A2，A3,每区代表的投票权重为4，4，4，4，2，1，1,决定投票

27、结果的区域集合：A1，A2，A3 ，A1, A2, B, A1, A3, C, D, A1, B, C, E , A1, A3, B, D ， ,A区代表是独裁者(能决定投票结果), 其他代表都是傀儡.,改革,加权投票与获胜联盟 例1 一县5区(A, B, C, D,加权投票与获胜联盟,加权投票系统,投票人集合N=A，B，C, (n人),权重w1, w2, ，wn,定额q 投赞成票的投票人权重之和 q时决议通过.,w=w1+ w2,+wn，一般 w/2qw,对简单多数规则且权重取整数，q为大于w/2的最小整数,S=q: w1, w2, ，wn,获胜联盟 权重之和定额q的投票人子集.,极小获胜联

28、盟如果没有它的一个真子集也是获胜联盟.,获胜联盟集W,极小获胜联盟集Wm,加权投票与获胜联盟 加权投票系统投票人集合N=A，B，C,加权投票与获胜联盟,例2 某系一委员会由主任A 、教授B 、学生C组成，投票权重为w1, w2, w3.,几种加权投票系统：,S(1)=3: 3, 1, 1,Wm=(A),极小获胜联盟集Wm,A是独裁者, B,C是傀儡,S(2)=2: 1, 1, 1,Wm=(AB, AC, BC),A,B,C权力相同,S(3)=4: 2, 2, 1,Wm=(AB),S(4)=3: 2, 1, 1,Wm=(AB ,AC),A,B权力相同,C是傀儡,B,C权力相同,A有否决权,Wm=

29、(AB ,AC),5: 3, 2, 2 , ,S与Wm或W的关系参看习题,加权投票与获胜联盟 例2 某系一委员会由主任A 、教授B,加权投票与获胜联盟,每个投票人的投票对结果的影响不直接依赖于他的权重.,每个投票人对结果的影响才是他的权力最重要的度量.,(相对)权力指标为k =(k1, k2, k3),S(1)=3: 3, 1, 1,Wm=(A),S(2)=2: 1, 1, 1,Wm=(AB, AC, BC),S(3)=4: 2, 2, 1,Wm=(AB),S(4)=3: 2, 1, 1,Wm=(AB ,AC),k(1) =(1, 0, 0 ),k(2)=(1, 1, 1 ),k(3)=(1,

30、 1, 0 ),k(4)=,例2 某系一委员会由主任A 、教授B 、学生C组成，投票权重为w1, w2, w3.,(?, 1, 1 ),寻找公平、合理的度量投票人权力的数量指标.,加权投票与获胜联盟 每个投票人的投票对结果的影响不直接依赖于,权力指标（Power index）,S=q: w1, w2, ，wn,G=(N, W),度量投票人权力的数量指标应该具有的性质：,1. 每个投票人i 有一个非负实数ki作为他的权力指标.,2. 当且仅当 (i是傀儡)时ki=0.,4. 当投票人i和j在W中“对称”时ki=kj.,5. 归一化 (不是必须).,满足这些性质的数量指标并不唯一.,Shapley

31、权力指标,Banzhaf 权力指标,3. 若权重wiwj, 则kikj.,权力指标（Power index） S=q: w1, w2,Shapley权力指标,S(4)=3: 2, 1, 1,例2,3位投票人的全排列: ABC, ACB, BAC, BCA, CAB, CBA,主任A,教授B,学生C的加权投票系统,ABC: 从A增至AB时AB变为获胜联盟,ACB: 从A增至AC时AC变为获胜联盟,BCA:从BC增至BCA时BCA变为获胜联盟,ABCACB BAC BCA CAB CBA,BAC: 从B增至BA时BA变为获胜联盟,A下有4条横线，B, C下各有1条横线,Shapley指标（4，1，

32、1）,（4/6, 1/6, 1/6）,Shapley权力指标 S(4)=3: 2, 1, 1,Shapley权力指标,写出投票人的共n!个全排列;,对每一个排列由左向右依次检查，若某位投票人加入时该集合变成获胜联盟，称该投票人为决定者(Pivot);,将每位投票人在所有排列中的成为决定者的次数除以n!定义为他们的Shapley权力指标.,=/ n!, =(1, 2, ,n),n人加权投票系统,S(4)=3: 2, 1, 1,例2,W=（AB ,AC, ABC）,=(4/6, 1/6, 1/6),Shapley权力指标 写出投票人的共n!个全排列; 对,Shapley权力指标,例3 某股份公司4

33、个股东分别持有40%, 30%, 20%, 10%的股份, 公司的决策需经持有半数以上股份的股东的同意才可通过, 求4个股东在公司决策中的Shapley指标.,4个股东A,B,C,D的加权投票系统 S=6: 4，3，2，1,A,B,C,D 有4!=24个全排列，找出决定者，下划横线：,决定者次数=(10, 6, 6, 2),=(5/12, 3/12, 3/12, 1/12),Wm=(AB ,AC, BCD）,B和C对称, 2=3,ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDA

34、B CDBA DABC DACB DBAC DBCA DCAB DCBA,保留B在C之前的12个排列统计A,B(C),D为决定者的次数.,简化,Shapley权力指标 例3 某股份公司4个股东分别持有,Banzhaf 权力指标,S(4)=3: 2, 1, 1,例2,Shapley指标=(4/6, 1/6, 1/6),W=(AB ,AC, ABC）,获胜联盟,AB: 由于A的加入才成为获胜联盟,由于B的加入才成为获胜联盟,AC: 由于A的加入才成为获胜联盟,由于C的加入才成为获胜联盟,ABC: 由于A的加入才成为获胜联盟,AB,AC,ABC,A下有3条横线，B, C下各有1条横线,Banzhaf

35、指标（3，1，1）,（3/5, 1/5, 1/5）,Banzhaf 权力指标 S(4)=3: 2, 1, 1,Banzhaf 权力指标,写出投票人的获胜联盟集W;,对每一个获胜联盟检查每位投票人是否决定者;,将每位投票人在所有获胜联盟中的成为决定者的次数归一化, 定义为Banzhaf权力指标=(1,2, ,n).,n人加权投票系统,例3,4个股东A,B,C,D的加权投票系统 S=6: 4, 3, 2, 1,W=（AB ,AC, ABC, ABD, ACD, BCD, ABCD）,AB AC ABC ABD ACD BCD ABCD,=（5，3，3，1）,=(5/12, 3/12, 3/12,

36、1/12),=(5/12, 3/12, 3/12, 1/12),Banzhaf 权力指标 写出投票人的获胜联盟集W; 对,Banzhaf 指标,Shapley指标,投票人的全排列,对排列由左向右检查决定者,统计每人在所有排列中的决定者次数,投票人的获胜联盟集,对获胜联盟检查决定者,统计每人在所有获胜联盟中的决定者次数,每个排列中有且只有一个决定者,每个组合中没有或有(几个)决定者,(=/ n!) 已归一化,需归一化才得到,都满足度量权力的数量指标应该具有的性质.,Banzhaf 指标 Shapley指标 投票人的全排,加权投票与权力指标的应用,例4 拳击比赛设2个5人裁判组, 每人一票. 若第

37、1组以5:0 或4:1判选手甲胜, 则甲胜; 若以3:2判甲胜, 则第2组再判; 除非第2组以0:5或1:4判甲负, 其他情况最终都判甲胜.,将以上裁判规则用加权投票系统表示; 计算系统的Shapley指标和Banzhaf指标.,设两组10人同时裁判, 组成N=A, A, A, A, A, B, B, B, B, B,极小获胜联盟Wm =,3A2B ,S=q: a, a, a, a, a, 1, 1, 1, 1, 1,(4A ,2A4B),第1组5人权重各2, 第2组人权重各1, 按简单多数规则执行.,加权投票与权力指标的应用 例4 拳击比赛设2个5人裁判组,例4,极小获胜联盟Wm =,3A2

38、B ,(4A ,2A4B),一个B在所有排列中的决定者次数/ 10！,(3A1B)B(2A3B),(2A3B)B(3A1B),一个A的Shapley指标,=(0.1365, , 0.1365, 0.0635, , 0.0635),计算S=8: 2, 2, 2, 2, 2, 1, 1, 1, 1, 1 的Shapley指标,一个B的 Shapley指标,只需考察,例4极小获胜联盟Wm =3A2B , (4A , ,例4,计算S=8: 2, 2, 2, 2, 2, 1, 1, 1, 1, 1 的Banzhaf指标,考察A，B可能成为决定者的那些获胜联盟类型和个数,A为决定者的次数与B为决定者的次数

39、之比 840:400,=(0.1355, , 0.1355, 0.0645, , 0.0645),=(0.1365, , 0.1365, 0.0635, , 0.0635),w=(0.1333, , 0.1333, 0.0667, , 0.0667),对比,总和 840,总和 400,例4计算S=8: 2, 2, 2, 2, 2, 1, 1,例5 “团结就是力量”吗？,40位议员组成议会, “民主党”(M)11席, “共和党”(G)14席,独立人士(D) 15席, 投票采取简单多数规则, 21票通过.,在独立和党派结盟情况下计算议员的Shapley指标.,1. 独立投票系统 S(1)=21;1

40、,1,1,每位议员的Shapley指标相等：i=1/40, i=1, ,40,“民主党”、”共和党”、独立人士议员的Shapley指标：M=11/40=0.275, G=14/40=0.350,D=15/40=0.375,通过党派结盟能加强权力吗?,例5 “团结就是力量”吗？40位议员组成议会, “民主,2. “民主党”(M)11 位议员结盟系统S(2) =21;11,1,1,例5 “团结就是力量”吗？,计算M,M= 11/30=0.367,在余下的1-11/30=19/30中G和D的Shapley指标按照14:15分配,G= (19/30)*(14/29)=0.306,D=0.327,对比

41、S(1)=21;1,1,1 :M=0.275, G=0.350,D=0.375,“民主党“结盟使M增加 , G,D减少.,2. “民主党”(M)11 位议员结盟系统S(2) =21,例5 “团结就是力量”吗？,3. “共和党”14位议员也结盟, 系统S(3) =21;11,14,1,1,D (j7, i8 ),M(j7, i8 ),G (j 7),(i, j)对应左下方方格,共272个(除对角线).,对角线以下方格G在M之前加入,数决定者方格:M49, G100, D123,M=49/272=0.180G= 100/272=0.368D=0.452,例5 “团结就是力量”吗？3. “共和党”1

42、4位议员也,例5 “团结就是力量”吗？,不论”民主党”是否结盟，”共和党”结盟总比单干好.,“共和党”一旦结盟，”民主党”不结盟更好.,从”民主党”角度看, 应该尽量保持大家都是单干的局面, 若率先结盟会诱使”共和党”也结盟, 结果会败得很惨.,从独立人士角度看, 若只有”民主党”或”共和党”结盟自己都有损失, 但若两个党均结盟, 反而可得渔翁之利 .,例5 “团结就是力量”吗？“共和党”不结盟“共和党”结,两种权力指标的公理化,Shapley指标1954年提出, 1975年公理化.,Banzhaf指标1965年提出, 1979年公理化.,投票人集合I=1, 2, , n, 投票系统S=q:

43、w1, w2, ，wn,Banzhaf 指标,Shapley指标,I的任一子集S对应一个实值、单调函数v, 若S为获胜联盟v(S)=1, 否则v(S)=0. 若i在S中是决定者,两种权力指标的公理化 Shapley指标1954年提出, 1,两种权力指标的公理化,公理化Bz是/2n-1, 未归一化, =(3/4,1/4,1/4),称绝对Banzhaf指标, 通常比更能反映投票人权力的真实性.,用公理化公式计算例2 S(4)=3: 2, 1, 1的指标Sh和Bz,与定义得到的=(4/6, 1/6, 1/6), =(3/5, 1/5, 1/5) 比较.,两种权力指标的公理化 i=Ai=Bi=CA B

44、A C,两种权力指标的概率解释,投票人对结果的影响力 投票人能左右结果的概率.,例2 S(4)=3: 2, 1, 1,RA 事件“A能左右结果”,可解释为在各位投票人独立地、以1/2的概率投赞成或反对票的条件下, 每位投票人能左右结果的概率.,Banzhaf 指标,两种权力指标的概率解释 投票人对结果的影响力 投票人能左,两种权力指标的概率解释,例2 S(4)=3: 2, 1, 1,每位投票人独立投赞成票的概率, q=1-p投反对票概率,Shapley指标,在0, 1均匀分布,A, B, C能左右结果的概率,可解释为在各位投票人独立且 0, 1均匀概率分布地投赞成票的条件下，每位投票人能左右结

45、果的概率.,两种权力指标的概率解释 例2 S(4)=3: 2, 1,调整加权投票系统,例1 人口60, 20, 10, 5, 5 (千人), 比例p=(12, 4, 2, 1, 1),以p为权重简单多数规则下投票系统S=11: 12, 4, 2, 1, 1 ,Banzhaf指标=(1, 0, 0, 0, 0)与p相差很大.,投票人对结果的权力与他所代表的人口比例失调.,调整加权投票系统的目的: 寻求一组权重和定额, 使加权投票系统S= q: w1, w2, ，wn的Banzhaf指标与人口比例p相近似, 且当n较大时近似程度很高 .,在权重不变而增大定额q的情况下, 借助分析极小获胜联盟的办法

46、, 寻找与p相近似的加权投票系统.,调整加权投票系统 例1 人口60, 20, 10, 5,调整加权投票系统,例1 人口比例 p=(12, 4, 2, 1, 1),系统S=11: 12, 4, 2, 1, 1 ,权重不变、增大定额, 寻找与p相近似的投票系统.,Banzhaf指标=(1, 0, 0, 0, 0),=(11/21, 5/21, 3/21, 1/21, 1/21 ),S=15: 12, 4, 2, 1, 1 ,这个是人口比例 p的一个不错的近似!,2=3=4=5,2=3,1234= 5,3=4=5,(1, 0, 0, 0, 0),调整加权投票系统 例1 人口比例 p=(12, 4,

47、 2,调整加权投票系统,合适地定义与p之间的“距离”(与p看作n维空间的两个点)作为衡量近似程度的指标.,按照实际需要确定该指标的一个“阈值”,1）给出权重w和定额q的初值;,2）编程计算及与p的距离, 距离小于阈值时停止,否则转3；,3）改变w和q, 转2.,当n较大时调整权重和定额, 寻找与p近似的投票系统.,每调整一次权重和定额, 必须使极小获胜联盟的结构有所变化, 才有可能改进.,调整加权投票系统 合适地定义与p之间的“距离”(与p看,任何一个构造和规则有明确定义的投票系统都可用极小获胜联盟来描述, 并常可表示成加权投票系统(如例4).,权力度量模型评述,存在即使确定了极小获胜联盟也无

48、法表为加权投票系统的情况. Hilliard给出区别加权与非加权投票系统的数学方法, 并提供权重和定额的算法，或者指明不存在权重和定额的矛盾教材参考文献35.,两种权力指标常常给出相同或近似的结果, 从理论上区分它们的数学公理既不直观, 使用时也不具说服力,所以在应用中公理化方法并不能解决选择哪个指标的问题.,任何一个构造和规则有明确定义的投票系统都可用极小获胜联盟来,权力度量模型评述,道理上更浅显, 容易口头解释, 更易为实际工作者接受.,作为对策论中著名的Shapley值方法的副产品在数学界更有市场.,适于设计投票系统, 在代表尚未选出之前假定所有投票意愿的等可能性是合理的.,适于评价投票系统, 代表已经选出, 他们的立场为众人所知.,在加权投票系统中定义量化的权力指标，是将数学应用于社会政治领域的一个有意义的范例.,提出与“计量经济学”类似的新学科“计量政治学”.,Shapley指标,Banzhaf指标,权力度量模型评述 道理上更浅显, 容易口头解释, 更易为实际,