数学模型第四版姜启源第十一章.ppt

第十一章第十一章 博弈模型博弈模型11.1 进攻与撤退的抉择进攻与撤退的抉择11.2 让报童订购更多的报纸让报童订购更多的报纸11.3 “一口价一口价”的战略的战略 11.4 不患寡而患不均不患寡而患不均 11.5 效益的合理分配效益的合理分配 11.6 加权投票中权力的度量加权投票中权力的度量 单一决策主体单一决策主体决策变量决策变量目标函数目标函数约束条件约束条件决策主体的决策决策主体的决策行为发生直接相行为发生直接相互作用互作用(相互影响相互影响)博弈模型博弈模型非合作博弈非合作博弈合作博弈合作博弈三要素三要素博弈模型博弈模型(Game Theory)多个决策主体多个决策主体优化模型优化模型(Optimization)决策问题（Decision Problem）静态、动态静态、动态信息完全、不完全信息完全、不完全军事、政治、经济、企业管理和社会科学中应用广泛军事、政治、经济、企业管理和社会科学中应用广泛 1944年年6月初，盟军在诺曼底登陆成功月初，盟军在诺曼底登陆成功.到到8月初的形势：月初的形势：背背景景11.1 进攻与撤退的抉择进攻与撤退的抉择双方应该如何决策双方应该如何决策？强强 化化缺口缺口盟军盟军(预备队预备队)撤退撤退进攻进攻德军德军盟军盟军(加加)盟军盟军(英英)盟军盟军(美一美一)盟盟军军(美美三三)东进东进原地原地待命待命模型假设模型假设 博弈参与者为两方（盟军和德军）博弈参与者为两方（盟军和德军）盟军有盟军有3种使用其预备队的行动：强化缺口，原地待种使用其预备队的行动：强化缺口，原地待命，东进；德军有命，东进；德军有2种行动：向西进攻或向东撤退种行动：向西进攻或向东撤退.博弈双方博弈双方完全理性完全理性，目的都是使战斗中己方获得，目的都是使战斗中己方获得的净胜场次（胜利场次减去失败场次）尽可能多的净胜场次（胜利场次减去失败场次）尽可能多.盟盟军胜军胜1场场盟盟军败军败2场场东进东进无无战战斗斗盟盟军胜军胜2场场原地待命原地待命无无战战斗斗盟盟军胜军胜1场场强强化缺口化缺口向向东东撤退撤退向西向西进进攻攻盟盟军军德德军军完全信息完全信息静态博弈静态博弈 共同知识共同知识(以上信息双方共有以上信息双方共有)双方同时做出决策双方同时做出决策博弈模型博弈模型 博弈参与者集合博弈参与者集合N=1,2(1为盟军，为盟军，2为德军为德军)用用u1(a1，a2)表示对盟军产生的结果，即净胜场次，表示对盟军产生的结果，即净胜场次，称为盟军的称为盟军的效用函数效用函数.盟盟军胜军胜1场场盟盟军败军败2场场东进东进无无战战斗斗盟盟军胜军胜2场场原地待命原地待命无无战战斗斗盟盟军胜军胜1场场强强化缺口化缺口向向东东撤退撤退向西向西进进攻攻盟盟军军德德军军 盟军行动盟军行动a1 A1=1,2,3(强化缺口强化缺口/原地待命原地待命/东进东进)；德军行动德军行动a2 A2=1,2(进攻进攻/撤退撤退).(行动：即纯战略行动：即纯战略)支付矩阵支付矩阵（Payoff Matrix）完全竞争完全竞争:零和博弈零和博弈 (常数和博弈常数和博弈)u2(a1，a2)对应对应 M博弈的解博弈的解的概念：的概念：纳什均衡纳什均衡(NE:Nash Equilibrium)不存在不存在(纯纯)NE(纯战略纯战略)纳什均衡纳什均衡Nash:1994年获诺贝尔经济学奖年获诺贝尔经济学奖NE:单向改变战略不能提高自己效用，单向改变战略不能提高自己效用，即每一方的战略即每一方的战略对于他方的战略而言都是最优的对于他方的战略而言都是最优的,称为称为最优反应最优反应.(纯纯)NE:a*=(a1*,a2*)=(2,2)非常数和非常数和博弈博弈(双矩双矩阵表示阵表示)混合战略（策略：混合战略（策略：Strategy)盟军的盟军的混合战略混合战略集集 期望收益期望收益盟军盟军德军德军 S1=p=(p1,p2,p3)|德军的德军的混合战略混合战略集集 S2=q=(q1,q2)|完全信息静态博弈完全信息静态博弈有限博弈矩阵博弈有限博弈矩阵博弈(2人人)零和博弈零和博弈常数和博弈常数和博弈 模型求解模型求解理性推理：理性推理：不管自己怎么做，另一方总是希望使自不管自己怎么做，另一方总是希望使自己得分尽量低己得分尽量低.（二人零和博弈，完全竞争）（二人零和博弈，完全竞争）盟军盟军德军德军线性线性规划规划 从一个给定的战略中期望得到的赢得，总是从一个给定的战略中期望得到的赢得，总是采用该策略时他们可能得到的最坏的赢得！采用该策略时他们可能得到的最坏的赢得！盟军可以用盟军可以用min pM来衡量策略来衡量策略p的好坏的好坏 max U1(p)=min pM min U2(q)=max MqT 德军可以用德军可以用max MqT来衡量策略来衡量策略q的好坏的好坏(p*,q*):混合混合(策略策略)纳什均衡纳什均衡(Mixed NE)p2*=3/5，p3*=2/5q1*=1/5，q2*=4/5最优值均为最优值均为2/5占优占优(dominate)：盟军的行动：盟军的行动2占优于占优于1 （前面的非常数和博弈（前面的非常数和博弈M类似）类似）混合策略似乎不太可行混合策略似乎不太可行!但但概率概率可作为可作为参考参考.-现实现实：盟军让预备队原地待命（行动：盟军让预备队原地待命（行动2），而德军），而德军没有选择撤退（行动没有选择撤退（行动2），结果德军大败），结果德军大败.模型评述模型评述 博弈规则博弈规则至关重要的，如参与人决策的时间顺序、至关重要的，如参与人决策的时间顺序、决策时拥有哪些信息等决策时拥有哪些信息等.多人多人(或非常数和或非常数和)博弈问题，一般不能用上面的线性博弈问题，一般不能用上面的线性规划方法求解，而通过纳什均衡的定义求解规划方法求解，而通过纳什均衡的定义求解.小结：博弈模型的基本要素小结：博弈模型的基本要素 参与人参与人 理性假设理性假设 行动顺序（静态、动态）行动顺序（静态、动态）信息结构（完全、不完全）信息结构（完全、不完全）行动空间（及战略空间）行动空间（及战略空间）效用函数效用函数 参与者完全理性参与者完全理性(最大化效用最大化效用)其他因素其他因素纳什均衡纳什均衡单向改变战略不能提高自己效用单向改变战略不能提高自己效用11.2 让报童订购更多的报纸让报童订购更多的报纸 报报童童模模型型回回顾顾订购价订购价w，零售价，零售价p，处理价，处理价v（pwv0）需求量：密度函数需求量：密度函数f(x)、分布函数、分布函数F(x),F(0)=0订购订购Q份报纸，期望销售量为份报纸，期望销售量为 期望存货量期望存货量期望利润期望利润 最优订购量最优订购量Qr Qr(w)问题问题假设报社报纸成本价为假设报社报纸成本价为c，wcv w*完全信息动态博弈：常称完全信息动态博弈：常称Stackelberg Game(两阶段两阶段)子博弈完美均衡子博弈完美均衡:(w*，Qr(w)一般一般w*c Qr(w*)wbv)回收协议模型回收协议模型 模型二模型二 回收数量协议回收数量协议 报社回收报社回收 达到协调达到协调报童回收报童回收，报童利润，报童利润,报社利润报社利润;利润任意分配都可达到利润任意分配都可达到 按批发价回收，比例为按批发价回收，比例为 报童利润报童利润回收协议模型回收协议模型 模型评述模型评述 协议参数的确定：协议参数的确定：不能单方决定不能单方决定双方谈判（合作博弈）双方谈判（合作博弈）还有很多其他类型的协议，也可以达到协调还有很多其他类型的协议，也可以达到协调一种更简单的协议一种更简单的协议批发价批发价w成本成本c收取一定加盟费收取一定加盟费如何评价比较协议的优缺点？如何评价比较协议的优缺点？是否能达到协调是否能达到协调是否能任意分配利润是否能任意分配利润协议执行成本有多高协议执行成本有多高11.3 “一口价一口价”的战略的战略 背景背景 为了节省为了节省“讨价还价讨价还价”时间，考虑时间，考虑“一口价一口价”模式模式.双方同时报价双方同时报价：若买价：若买价卖价，则以均价成交卖价，则以均价成交;否则不成交否则不成交.问题问题 双方应如何报价？双方应如何报价？双方总能成交吗？（效率估计）双方总能成交吗？（效率估计）“讨价还价讨价还价”很浪费买卖双方的宝贵时间很浪费买卖双方的宝贵时间.模型假设与建立模型假设与建立 卖方知道物品对自己的价值，但买方不知道卖方知道物品对自己的价值，但买方不知道.买方知道物品对自己的价值，但卖方不知道买方知道物品对自己的价值，但卖方不知道.双方都知道（如猜出）对方价值的分布信息双方都知道（如猜出）对方价值的分布信息.卖方价值卖方价值vs,买方价值买方价值vb,均服从均服从 0,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区间上的非减函数区间上的非减函数.不完全信息静态博弈（静态贝叶斯博弈）不完全信息静态博弈（静态贝叶斯博弈）贝叶斯纳什均衡贝叶斯纳什均衡单向改变战略不能单向改变战略不能提高自己效用提高自己效用.信息非对称（不完全信息）信息非对称（不完全信息）模型假设与建立模型假设与建立均衡条件均衡条件具体战略具体战略(函数函数)形式不同，均衡就可能不同形式不同，均衡就可能不同.单一价格战略单一价格战略卖方：卖方：买方：买方：双方战略互为最优反应，所以构成双方战略互为最优反应，所以构成贝叶斯纳什均衡贝叶斯纳什均衡！模型假设与建立模型假设与建立单一价格战略效率为单一价格战略效率为x0.5效率最大效率最大(3/4)对给定的对给定的(vs,vb)，当，当vsxj=1-xi时，时，i(x)xi-i(xi-xj)=i-(2i-1)xi关于关于xi的系数非正的系数非正（过分（过分“愧疚愧疚”）效用函数效用函数财富总额为财富总额为1接受提议：甲乙所得接受提议：甲乙所得x1=1-s,x2=s；否则：；否则：x1=x2=0 模型求解模型求解如果不接受，则如果不接受，则x1=x2=0;U1(s)=U2(s)=0.若若s1/2,则则x2 x1乙的最优反应乙的最优反应乙的最优反应（给定乙的最优反应（给定s）如果接受，则如果接受，则x1=1-s,x2=s.若若s1/2,则则x2x1U2(s)01/20 s 当当 s 接受接受;否则，不接受否则，不接受易知易知(s1/2,两者一致两者一致)模型求解模型求解Case 1:甲知道乙的甲知道乙的2 若若s1/2,则则x2 x1甲的决策甲的决策s=1/2时达到最大值时达到最大值1/2甲的决策甲的决策(只需考虑乙接受情形只需考虑乙接受情形)若若s1/2,则则x2 x1但但 s 均衡均衡:(s*,接受接受)s*严格小于严格小于50%;是乙的是乙的“愤怒愤怒”系数系数2的增函数的增函数.模型求解：甲的决策模型求解：甲的决策Case 2:甲不知道乙的甲不知道乙的2,但知道但知道2的分布的分布F(2)若若s1/2,则则x2 x1甲的决策甲的决策 若若s1/2,则则x2 x1U1(s)=1-s-1(2s-1)同前同前期望效用期望效用乙接受概率乙接受概率s*模型解释模型解释 甲永远不会提出大于甲永远不会提出大于/的方案的方案s 乙拒绝过小的方案乙拒绝过小的方案s很好地解释了实际中的最后通牒博弈很好地解释了实际中的最后通牒博弈.乙接受概率随乙接受概率随s增加不减增加不减参考文献参考文献11.5 效益的合理分配效益的合理分配例例甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，元，三人合作获利三人合作获利11元元.又知每人单干获利又知每人单干获利1元元.问三人合作时如何分配获利？问三人合作时如何分配获利？记甲乙丙三人分配为记甲乙丙三人分配为解不唯一解不唯一(5，3，3)(4，4，3)(5，4，2)(1)Shapley合作对策合作对策 I,v n人合作对策，人合作对策，v特征函数特征函数n人从人从v(I)得到的分配，满足得到的分配，满足v(s)子集子集s的获利的获利公理化方法公理化方法 s 子集子集 s中的元素数目，中的元素数目，Si 包含包含i的所有子集的所有子集由由 s 决定的决定的“贡献贡献”的权重的权重 Shapley值值 i 对合作对合作s 的的“贡献贡献”Shapley合作对策合作对策三人三人(I=1,2,3)经商中甲的分配经商中甲的分配x1的计算的计算 1/3 1/6 1/6 1/31 1 2 1 3 I1 7 5 11 0 1 1 4 1 6 4 7 1/3 1 2/3 7/3x1=13/3类似可得类似可得 x2=23/6,x3=17/61 2 2 3合作对策的应用合作对策的应用 污水处理费用的合理分担污水处理费用的合理分担20km38km河流河流三城镇地理位置示意图三城镇地理位置示意图123 污水处理，排入河流污水处理，排入河流.三城镇可单独建处理厂，三城镇可单独建处理厂，或联合建厂或联合建厂(用管道将污水用管道将污水由上游城镇送往下游城镇由上游城镇送往下游城镇).Q1=5Q3=5Q2=3Q污水量，污水量，L管道长度管道长度建厂费用建厂费用P1=73Q0.712管道费用管道费用P2=0.66Q0.51L污水处理的污水处理的5 种方案种方案1）单独建厂）单独建厂总投资总投资2）1,2合作合作3）2,3合作合作4）1,3合作合作总投资总投资总投资总投资合作不会实现合作不会实现5）三城合）三城合作总投资作总投资D5最小最小,应联合建厂应联合建厂 建厂费：建厂费：d1=73(5+3+5)0.712=453 12 管道费：管道费：d2=0.66 50.51 20=30 23 管道费：管道费：d3=0.66 (5+3)0.51 38=73D5城城3建议：建议：d1 按按 5:3:5分担分担,d2,d3由城由城1,2担负担负城城2建议：建议：d3由城由城1,2按按 5:3分担分担,d2由城由城1担负担负城城1计算：计算：城城3分担分担 d1 5/13=174C(3),城城2分担分担 d1 3/13+d3 3/8=132C(1)不同意不同意!D5如何分担？如何分担？特征函数特征函数v(s)联合联合(集集s)建厂比单独建厂节约的投资建厂比单独建厂节约的投资三三城从城从节约投资节约投资v(I)中得到的分配中得到的分配 Shapley合作对策合作对策计算计算城城1从从节约投资中得到的分配节约投资中得到的分配x11 1 2 1 3 I 0 40 0 640 0 0 250 40 0 39 1 2 2 31/3 1/6 1/6 1/3 0 6.7 0 13 x1=19.7,城城1 C(1)-x1=210.4,城城2 C(2)-x2=127.8,城城3 C(3)-x3=217.8三城在总投资三城在总投资556中的分担中的分担x2=32.1,x3=12.2x2最大，如何解释？最大，如何解释？优点：优点：公正、合理，有公理化基础公正、合理，有公理化基础.如如n个单位治理污染个单位治理污染,通常知道第通常知道第i方单独治理的投资方单独治理的投资yi 和和n方共同治理的投资方共同治理的投资Y,及第及第i方不参加时其余方不参加时其余n-1方的方的投资投资zi(i=1,2,n).确定共同治理时各方分担的费用确定共同治理时各方分担的费用.其他其他v(s)均不知道均不知道,无法用无法用Shapley合作对策合作对策求解求解Shapley合作对策小结合作对策小结若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有缺点：缺点：需要知道所有合作的获利需要知道所有合作的获利,即要定义即要定义I=1,2,n的的所有子集所有子集(共共2n-1个个)的特征函数，实际上的特征函数，实际上常做不到常做不到.设只知道设只知道无无 i 参加时参加时n-1方合作的获利方合作的获利全体合作的获利全体合作的获利求解合作对策的其他方法求解合作对策的其他方法例例.甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元，甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人合作获利合作获利11元元.问三人合作时如何分配获利？问三人合作时如何分配获利？（1）协商解）协商解11将剩余获利将剩余获利 平均分配平均分配 模型模型以以n-1方合作的获利为下限方合作的获利为下限求解求解 xi 的下限的下限（2）Nash解解 为现状点（谈判时的威慑点）为现状点（谈判时的威慑点）在此基础上在此基础上“均匀地均匀地”分配全体合作的获利分配全体合作的获利B模型模型平均分配获利平均分配获利B2）Nash解解 1）协商解）协商解（3）最小距离解）最小距离解模型模型 第第i 方的边际效益方的边际效益若令若令3）最小距离解）最小距离解 1）协商解）协商解（4）满意解）满意解di现状点现状点(最低点最低点)ei理想点理想点(最高点最高点)模型模型4）基于满意度的解）基于满意度的解 1）协商解）协商解（5）Raiffi 解解与协商解与协商解x=(5,4,2)比较比较求解合作对策的求解合作对策的6种方法（可分为三类）种方法（可分为三类）Shapley合作对策合作对策A类类B类类协商解协商解Nash解解 最小距离解最小距离解满意解满意解di现状现状,ei理想理想B类类4种方法相同种方法相同例：有一资方例：有一资方(甲甲)和二劳方和二劳方(乙乙,丙丙),仅当资方与至少仅当资方与至少一劳方合作时才获利一劳方合作时才获利10元，应如何分配该获利？元，应如何分配该获利？Raiffi解解C类类B类：类：计算简单，便于理解，可用于各方实计算简单，便于理解，可用于各方实力相差不大的情况；一般来说它偏袒强者力相差不大的情况；一般来说它偏袒强者.C类：类：考虑了分配的上下限，又吸取了考虑了分配的上下限，又吸取了Shapley的思想，在一定程度上保护弱者的思想，在一定程度上保护弱者.A类：类：公正合理；需要信息多，计算复杂公正合理；需要信息多，计算复杂.求解合作对策的三类方法小结求解合作对策的三类方法小结11.6 加权投票中权力的度量加权投票中权力的度量 背景背景“一人一票一人一票”显示投票和表决的公正显示投票和表决的公正.股份制公司每位股东投票和表决权的大小由所股份制公司每位股东投票和表决权的大小由所占有的占有的股份股份多少决定多少决定.一些国家、地区的议会、政府的产生，由所属的一些国家、地区的议会、政府的产生，由所属的州、县等各个区域推出的代表投票决定州、县等各个区域推出的代表投票决定.代表投票的权重取决于所代表区域的代表投票的权重取决于所代表区域的人口人口数量数量.经济或政治机构权力的分配经济或政治机构权力的分配 背景背景典型案例典型案例:美国总统选举实行的选举人制度美国总统选举实行的选举人制度 美全国美全国50个州和华盛顿特区共个州和华盛顿特区共538张张选举人票选举人票.获选举人票数获选举人票数一半以上一半以上的总统候选人当选总统的总统候选人当选总统.各州各州选举人票数选举人票数与该州在国会的参、众议员数相等与该州在国会的参、众议员数相等.参议员每州两位，众议员人数由各州参议员每州两位，众议员人数由各州人口比例人口比例确定确定.各州人口悬殊巨大使各州人口悬殊巨大使各州选举人票数相差很大各州选举人票数相差很大.(如加利福尼亚州选举人票如加利福尼亚州选举人票55张，阿拉斯加州只张，阿拉斯加州只3张张)背景背景典型案例典型案例:美国总统选举实行的选举人制度美国总统选举实行的选举人制度 总统候选人在各州内进行普选，获得总统候选人在各州内进行普选，获得相对多数相对多数选票的候选人得到该州的选票的候选人得到该州的全部选举人票全部选举人票.48个州和华盛顿特区都实行个州和华盛顿特区都实行“胜者全得胜者全得”：在加利福尼亚州以在加利福尼亚州以微弱多数微弱多数普选获胜的普选获胜的总统候选人可得到总统候选人可得到全部全部55张张选举人票选举人票.若有几个人口多的州如此，在选举人投票中就若有几个人口多的州如此，在选举人投票中就可能使各州可能使各州累计得票最多的候选人累计得票最多的候选人反而不能获胜反而不能获胜.选举结果违反选举结果违反全国多数人全国多数人的意愿的意愿.2000年年布什布什与与戈尔戈尔进行的竞选中，戈尔最终败给布什！进行的竞选中，戈尔最终败给布什！问题问题由若干区域由若干区域(如省、县等如省、县等)组成的机构中，每区组成的机构中，每区代表的数量按照人口比例分配，进行投票选举代表的数量按照人口比例分配，进行投票选举和表决时，每区的全体代表投相同的票和表决时，每区的全体代表投相同的票.每区各派一位代表每区各派一位代表(投票人投票人)，按照他们所代表，按照他们所代表的各区人口比例赋予投票的权重的各区人口比例赋予投票的权重.如何度量每位代表的投票对最终结果的影响力如何度量每位代表的投票对最终结果的影响力(权力权力).介绍两种合理的、度量权力的数量指标介绍两种合理的、度量权力的数量指标.通过实例给出它们的应用通过实例给出它们的应用.调整投票人的权重使其权力大致与代表的人口成比例调整投票人的权重使其权力大致与代表的人口成比例.加权投票中权力的度量加权投票中权力的度量背背景景加权投票与获胜联盟加权投票与获胜联盟 例例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 决定投票结果的区域集合决定投票结果的区域集合：A1，A2，A3,A1,A2,B,A1,A3,C,D,A1,B,C,E,A1,A3,B,D，A区代表是区代表是独裁者独裁者(能决定投票结果能决定投票结果),其他代表都是其他代表都是傀儡傀儡.改改革革加权投票与获胜联盟加权投票与获胜联盟 加权投票系统加权投票系统投票人集合投票人集合N=A,B,C,(n人人)权重权重w1,w2,wn 定定额额q 投赞成票的投票人权重之和投赞成票的投票人权重之和 q时决议通过时决议通过.w=w1+w2+wn，一般，一般 w/2wj,则则kikj.Shapley权力指标权力指标 S(4)=3;2,1,1 例例23位投票人的位投票人的全排列全排列: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，1）（4/6,1/6,1/6）CAB:CBA:归一化归一化 Shapley权力指标权力指标 写出投票人的共写出投票人的共n!个全个全排列排列;对每一个排列对每一个排列由左向右由左向右依次检查，若某位投票人加入依次检查，若某位投票人加入时该集合变成获胜联盟，称该投票人为时该集合变成获胜联盟，称该投票人为决定者决定者(Pivot);将每位投票人在所有排列中的成为将每位投票人在所有排列中的成为决定者的次数决定者的次数除除以以n!定义为他们的定义为他们的Shapley权力指标权力指标.=/n!,=(1,2,n)n人加权投票系统人加权投票系统S(4)=3:2,1,1 例例2W=（AB,AC,ABC）=(4/6,1/6,1/6)B和和C对对称称,2=3 Shapley权力指标权力指标 例例3 某股份公司某股份公司4个股东分别持有个股东分别持有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 CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA保留保留B在在C之前的之前的12个排列统计个排列统计A,B(C),D为决定者的次数为决定者的次数.简化简化Banzhaf 权力指标权力指标 S(4)=3;2,1,1 例例2Shapley指指标标=(4/6,1/6,1/6)W=(AB,AC,ABC）获胜联盟获胜联盟AB:由于由于A的加入才成为获胜联盟的加入才成为获胜联盟 由于由于B的加入才成为获胜联盟的加入才成为获胜联盟AC:由于由于A的加入才成为获胜联盟的加入才成为获胜联盟 由于由于C的加入才成为获胜联盟的加入才成为获胜联盟ABC:由于由于A的加入才成为获胜联盟的加入才成为获胜联盟ABACABCA下有下有3条横线，条横线，B,C下各有下各有1条横线条横线 Banzhaf指指标标（3，1，1）（3/5,1/5,1/5）归一化归一化 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,1/12)=(5/12,3/12,3/12,1/12)归一化归一化 Banzhaf 指标指标 Shapley指标指标 投票人的全投票人的全排列排列 对排列对排列由左向右由左向右检查检查决定者决定者 统计每人在所有排列中的统计每人在所有排列中的决定者次数决定者次数 投票人的投票人的获胜联盟集获胜联盟集 对对获胜联盟获胜联盟检查检查决定者决定者 统计每人在所有统计每人在所有获胜获胜联盟联盟中的决定者次数中的决定者次数每个每个排列中有且只有一个排列中有且只有一个决定者决定者每个每个组合中没有或有组合中没有或有(几个几个)决定者决定者(=/n!)已归一化已归一化需需归一化才得到归一化才得到都满足度量权力的数量指标应该具有的性质都满足度量权力的数量指标应该具有的性质.加权投票与权力指标的应用加权投票与权力指标的应用 例例4 拳击比赛设拳击比赛设2个个5人裁判组人裁判组,每每人人一票一票.若第若第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,按简单多数规则执行按简单多数规则执行.a=2,q=8 例例4极小获胜联盟极小获胜联盟Wm=3A2B,(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指标指标 只需考察只需考察Shapley指标指标 例例4 计算计算S=8;2,2,2,2,2,1,1,1,1,1 的的Banzhaf指标指标考察考察A，B可能成为决定者的那些获胜联盟类型和个数可能成为决定者的那些获胜联盟类型和个数 获胜联获胜联盟盟类类型型4A 4A1B 3A2B3A3B 2A4B2A5B联联盟个数盟个数5251001005010A为决定者次数为决定者次数2010030030010020B为决定者次数为决定者次数0020002000A为决定者的次数与为决定者的次数与B为决定者的次数之比为决定者的次数之比 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例例5 “团结就是力量团结就是力量”吗吗？40位议员组成议会位议员组成议会,“民主党民主党”(M)11席席,“共和党共和党”(G)14席席,独立人士独立人士(D)15席席,投票采取简单多数规则投票采取简单多数规则,21票通过票通过.在在独立独立和党派和党派结结盟盟情况下情况下计计算算议员议员的的Shapley指标指标.1.独立独立投票系投票系统统 S(1)=21;1,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 通过通过党派党派结盟能加强权力吗结盟能加强权力吗?2.“民主党民主党”(M)11 位议员结盟系统位议员结盟系统S(2)=21;11,1,1 例例5 “团结就是力量团结就是力量”吗吗？计计算算M 29 个1MM加入加入,成为决定者成为决定者 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30M=11/30=0.367 在余下的在余下的1-11/30=19/30中中G和和D的的Shapley指标按照指标按照14:15分配分配G=(19/30)*(14/29)=0.306,D=0.327 对比对比 S(1)=21;1,1,1:M=0.275,G=0.350,D=0.375 考察考察M在在30人中的位置人中的位置:M+G(14)+D(15)“民主党民主党”结盟使结盟使M增加增加,G,D减少减少.例例5 “团结就是力量团结就是力量”吗吗？3.“共和党共和党”14位议员也结盟位议员也结盟,系统系统S(3)=21;11,14,1,1 15 个1MG1716151413121110 9 8 7 6 5 4 3 2 1 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 M 加加 入位置入位置 i G加加入入位位置置 jD(j7,i8)M(j7,i8)DMGG(j 7)(i,j)对应左下方方对应左下方方格格,共共272个个(除对角除对角线线).对角线对角线以下方格以下方格G在在M之前加入之前加入 数数决定者决定者方格方格:M49,G100,D123 M=49/272=0.180G=100/272=0.368D=0.452 例例5 “团结就是力量团结就是力量”吗吗？“共和党共和党”不不结结盟盟“共和党共和党”结结盟盟“民主党民主党”不不结结盟盟M=0.275 G=0.350M=0.204 G=0.519“民主党民主党”结结盟盟M=0.367 G=0.306M=0.180 G=0.368 不论不论“民主党民主党”是否结盟，是否结盟，“共和党共和党”结盟总比单干好结盟总比单干好.“共和党共和党”一旦结盟，一旦结盟，“民主党民主党”不结盟更好不结盟更好.从从“民主党民主党”角度看角度看,应该尽量保持大家都是单干的局应该尽量保持大家都是单干的局面面,若率先结盟会诱使若率先结盟会诱使“共和党共和党”也结盟也结盟,结果会败得结果会败得很惨很惨.从独立人士角度看从独立人士角度看,若只有若只有“民主党民主党”或或“共和党共和党”结盟自己都有损失结盟自己都有损失,但若两个党均结盟但若两个党均结盟,反而可得渔翁反而可得渔翁之利之利.两种权力指标的公理化两种权力指标的公理化 Shapley指标指标1954年提出年提出,1975年公理化年公理化.Banzhaf指标指标1965年提出年提出,1979年公理化年公理化.投票人集合投票人集合I=1,2,n,投票系投票系统统S=q:w1,w2,wn Banzhaf 指标指标Shapley指标指标I的任一子集的任一子集S对应一个实值、单调函数对应一个实值、单调函数v,若若S为获胜联盟为获胜联盟v(S)=1,否则否则v(S)=0.若若i在在S中是决定者中是决定者,计算计算i为决定者的次数为决定者的次数 按排列计算按排列计算(sS中人数中人数)两种权力指标的公理化两种权力指标的公理化 i=Ai=Bi=CA BA CA B CA BA C1/221/41/41/41/41/4Bz3/41/41/4s22322(s-1)!(3-s)!/3!1/61/62/61/61/6Sh4/61/61/6公理化公理化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)比较比较.两种权力指标的概率解释两种权力指标的概率解释 投票人对结果的影响力投票人对结果的影响力 投票人能左右结果的概率投票人能左右结果的概率.例例2 S(4)=3;2,1,1RA 事件事件“A能左右能左右结结果果”可解释为在各位投票人可解释为在各位投票人独立地、以独立地、以1/2的概率投赞成的概率投赞成或反对票或反对票的条件下的条件下,每位投票人能左右结果的概率每位投票人能左右结果的概率.Banzhaf 指标指标B,C均以均以1/2的概率独立投赞成或反对票的概率独立投赞成或反对票 BB投投赞赞成票成票B投投反反对对票票 两种权力指标的概率解释两种权力指标的概率解释 例例2 S(4)=3;2,1,1p每位投票人独立投赞成票的概率每位投票人独立投赞成票的概率,q=1-p投反对票概率投反对票概率Shapley指标指标p在在0,1均匀分布均匀分布 A,B,C能左右结果的概率能左右结果的概率 可解释为在各位投票人可解释为在各位投票人独立且独立且 0,1均匀概率分布地均匀概率分布地投赞成票投赞成票