数学模型第四版姜启源第十博弈模型市公开课一等奖百校联赛特等奖课件.pptx

第十一章第十一章 博弈模型博弈模型11.1 进攻与撤退抉择进攻与撤退抉择11.2 让报童订购更多报纸让报童订购更多报纸11.3 “一口价一口价”战略战略 11.4 不患寡而患不均不患寡而患不均 11.5 效益合理分配效益合理分配 11.6 加权投票中权力度量加权投票中权力度量 第1页单一决议主体单一决议主体决议变量决议变量目标函数目标函数约束条件约束条件决议主体决议行决议主体决议行为发生直接相互为发生直接相互作用作用(相互影响相互影响)博弈模型博弈模型非合作博弈非合作博弈合作博弈合作博弈三要素三要素博弈模型博弈模型(Game Theory)多个决议主体多个决议主体优化模型优化模型(Optimization)决议问题（Decision Problem）静态、动态静态、动态信息完全、不完全信息完全、不完全军事、政治、经济、企业管理和社会科学中应用广泛军事、政治、经济、企业管理和社会科学中应用广泛第2页 1944年年6月初，盟军在诺曼底登陆成功月初，盟军在诺曼底登陆成功.到到8月初形势：月初形势：背背景景11.1 进攻与撤退抉择进攻与撤退抉择双方应该怎样决议双方应该怎样决议？强强 化化缺口缺口盟军盟军(预备队预备队)撤退撤退进攻进攻德军德军盟军盟军(加加)盟军盟军(英英)盟军盟军(美一美一)盟盟军军(美美三三)东进东进原地原地待命待命第3页模型假设模型假设 博弈参加者为两方（盟军和德军）博弈参加者为两方（盟军和德军）盟军有盟军有3种使用其预备队行动：强化缺口，原地待命，种使用其预备队行动：强化缺口，原地待命，东进；德军有东进；德军有2种行动：向西进攻或向东撤退种行动：向西进攻或向东撤退.博弈双方博弈双方完全理性完全理性，目标都是使战斗中己方取得，目标都是使战斗中己方取得净胜场次（胜利场次减去失败场次）尽可能多净胜场次（胜利场次减去失败场次）尽可能多.盟盟军胜军胜1场场盟盟军败军败2场场东进东进无无战战斗斗盟盟军胜军胜2场场原地待命原地待命无无战战斗斗盟盟军胜军胜1场场强强化缺口化缺口向向东东撤退撤退向西向西进进攻攻盟盟军军德德军军完全信息完全信息静态博弈静态博弈 共同知识共同知识(以上信息双方共有以上信息双方共有)双方同时做出决议双方同时做出决议第4页博弈模型博弈模型 博弈参加者集合博弈参加者集合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第5页博弈解博弈解概念：概念：纳什均衡纳什均衡(NE:Nash Equilibrium)不存在不存在(纯纯)NE(纯战略纯战略)纳什均衡纳什均衡Nash:1994年获诺贝尔经济学奖年获诺贝尔经济学奖NE:单向改变战略不能提升自己效用，单向改变战略不能提升自己效用，即每一方战略对即每一方战略对于他方战略而言都是最优于他方战略而言都是最优,称为称为最优反应最优反应.(纯纯)NE:a*=(a1*,a2*)=(2,2)非常数和非常数和博弈博弈(双矩双矩阵表示阵表示)第6页混合战略（策略：混合战略（策略：Strategy)盟军盟军混合战略混合战略集集 期望收益期望收益盟军盟军德军德军 S1=p=(p1,p2,p3)|德军德军混合战略混合战略集集 S2=q=(q1,q2)|完全信息静态博弈完全信息静态博弈有限博弈矩阵博弈有限博弈矩阵博弈(2人人)零和博弈零和博弈常数和博弈常数和博弈 第7页模型求解模型求解理性推理：理性推理：不论自己怎么做，另一方总是希望使自不论自己怎么做，另一方总是希望使自己得分尽可能低己得分尽可能低.（二人零和博弈，完全竞争）（二人零和博弈，完全竞争）盟军盟军德军德军线性线性规划规划 从一个给定战略中期望得到赢得，总是采取从一个给定战略中期望得到赢得，总是采取该策略时他们可能得到最坏赢得！该策略时他们可能得到最坏赢得！盟军能够用盟军能够用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第8页占优占优(dominate)：盟军行动：盟军行动2占优于占优于1 （前面非常数和博弈（前面非常数和博弈M类似）类似）混合策略似乎不太可行混合策略似乎不太可行!但但概率概率可作为可作为参考参考.-现实现实：盟军让预备队原地待命（行动：盟军让预备队原地待命（行动2），而德军），而德军没有选择撤退（行动没有选择撤退（行动2），结果德军大败），结果德军大败.模型评述模型评述 博弈规则博弈规则至关主要，如参加人决议时间次序、决议至关主要，如参加人决议时间次序、决议时拥有哪些信息等时拥有哪些信息等.多人多人(或非常数和或非常数和)博弈问题，普通不能用上面线性规博弈问题，普通不能用上面线性规划方法求解，而经过纳什均衡定义求解划方法求解，而经过纳什均衡定义求解.第9页小结：博弈模型基本要素小结：博弈模型基本要素 参加人参加人 理性假设理性假设 行动次序（静态、动态）行动次序（静态、动态）信息结构（完全、不完全）信息结构（完全、不完全）行动空间（及战略空间）行动空间（及战略空间）效用函数效用函数 参加者完全理性参加者完全理性(最大化效用最大化效用)其它原因其它原因纳什均衡纳什均衡单向改变战略不能提升自己效用单向改变战略不能提升自己效用第10页11.2 让报童订购更多报纸让报童订购更多报纸 报报童童模模型型回回顾顾订购价订购价w，零售价，零售价p，处理价，处理价v（pwv0）需求量：密度函数需求量：密度函数f(x)、分布函数、分布函数F(x),F(0)=0订购订购Q份报纸，期望销售量为份报纸，期望销售量为 期望存货量期望存货量期望利润期望利润 最优订购量最优订购量Qr Qr(w)第11页问题问题假设报社报纸成本价为假设报社报纸成本价为c，wcv w*完全信息动态博弈：常称完全信息动态博弈：常称Stackelberg Game(两阶段两阶段)子博弈完美均衡子博弈完美均衡:(w*，Qr(w)普通普通w*c Qr(w*)wbv)回收协议模型回收协议模型 第14页模型二模型二 回收数量协议回收数量协议 报社回收报社回收 到达协调到达协调报童回收报童回收，报童利润，报童利润,报社利润报社利润;利润任意分配都可到达利润任意分配都可到达 按批发价回收，百分比为按批发价回收，百分比为 报童利润报童利润回收协议模型回收协议模型 第15页模型评述模型评述 协议参数确定：不能单方决定双方谈判（合作博弈）还有很多其它类型协议，也能够到达协调还有很多其它类型协议，也能够到达协调一个更简单协议一个更简单协议批发价批发价w成本成本c收取一定加盟费收取一定加盟费怎样评价比较协议优缺点？怎样评价比较协议优缺点？是否能到达协调是否能到达协调是否能任意分配利润是否能任意分配利润协议执行成本有多高协议执行成本有多高第16页11.3 “一口价一口价”战略战略 背景背景 为了节约为了节约“讨价还价讨价还价”时间，考虑时间，考虑“一口价一口价”模式模式.双方同时报价双方同时报价：若买价：若买价卖价，则以均价成交卖价，则以均价成交;不然不成交不然不成交.问题问题 双方应怎样报价？双方应怎样报价？双方总能成交吗？（效率预计）双方总能成交吗？（效率预计）“讨价还价讨价还价”很浪费买卖双方宝贵时间很浪费买卖双方宝贵时间.第17页模型假设与建立模型假设与建立 卖方知道物品对自己价值，但买方不知道卖方知道物品对自己价值，但买方不知道.买方知道物品对自己价值，但卖方不知道买方知道物品对自己价值，但卖方不知道.双方都知道（如猜出）对方价值分布信息双方都知道（如猜出）对方价值分布信息.卖方价值卖方价值vs,买方价值买方价值vb,均服从均服从 0,1 上均匀分布上均匀分布卖方报价卖方报价ps,买方报价买方报价pb,pb ps时成交价时成交价p(pb+ps)/2成交效用：卖方成交效用：卖方U1=p-vs,买方买方U2=vb p;不成交不成交:0双方完全理性双方完全理性(最大化自己期望效用最大化自己期望效用).以上为双方共同知识以上为双方共同知识.第18页卖方报价卖方报价ps ps(vs)买方报价买方报价pb pb(vb)双方战略双方战略战略组合战略组合(ps(vs),pb(vb)何时组成均衡？何时组成均衡？定义在定义在0，1区间上、取值也区间上、取值也在在0，1区间上非减函数区间上非减函数.不完全信息静态博弈（静态贝叶斯博弈）不完全信息静态博弈（静态贝叶斯博弈）贝叶斯纳什均衡贝叶斯纳什均衡单向改变战略不能单向改变战略不能提升自己效用提升自己效用.信息非对称（不完全信息）信息非对称（不完全信息）模型假设与建立模型假设与建立第19页均衡条件均衡条件详细战略详细战略(函数函数)形式不一样，均衡就可能不形式不一样，均衡就可能不一样一样.单一价格战略单一价格战略卖方：卖方：买方：买方：双方战略互为最优反应，所以组成双方战略互为最优反应，所以组成贝叶斯纳什均衡贝叶斯纳什均衡！模型假设与建立模型假设与建立第20页单一价格战略效率为单一价格战略效率为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 第26页模型求解模型求解假如不接收，则假如不接收，则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,二者一致二者一致)第27页模型求解模型求解Case 1:甲知道乙甲知道乙2 若若s1/2,则则x2 x1甲决议甲决议s=1/2时到达最大值时到达最大值1/2甲决议甲决议(只需考虑乙接收情形只需考虑乙接收情形)若若s1/2,则则x2 x1但但 s 均衡均衡:(s*,接收接收)s*严格小于严格小于50%;是乙是乙“愤恨愤恨”系数系数2增函数增函数.第28页模型求解：甲决议模型求解：甲决议Case 2:甲不知道乙甲不知道乙2,但但知道知道2分布分布F(2)若若s1/2,则则x2 x1甲决议甲决议 若若s1/2,则则x2 x1U1(s)=1-s-1(2s-1)同前同前期望效用期望效用乙接收概率乙接收概率s*第29页模型解释模型解释 甲永远不会提出大于甲永远不会提出大于/方案方案s 乙拒绝过小方案乙拒绝过小方案s很好地解释了实际中最终通牒博弈很好地解释了实际中最终通牒博弈.乙接收概率随乙接收概率随s增加不减增加不减参考文件参考文件第30页11.5 效益合理分配效益合理分配例例甲乙丙三人合作经商，若甲乙合作赢利甲乙丙三人合作经商，若甲乙合作赢利7元，元，甲丙合作赢利甲丙合作赢利5元，乙丙合作赢利元，乙丙合作赢利4元，元，三人合作赢利三人合作赢利11元元.又知每人单干赢利又知每人单干赢利1元元.问三人合作时怎样分配赢利？问三人合作时怎样分配赢利？记甲乙丙三人分配为记甲乙丙三人分配为解不唯一解不唯一(5，3，3)(4，4，3)(5，4，2)第31页(1)Shapley合作对策合作对策 I,v n人合作对策，人合作对策，v特征函数特征函数n人从人从v(I)得到分配，满足得到分配，满足v(s)子集子集s赢利赢利第32页公理化方法公理化方法 s 子集子集 s中元素数目，中元素数目，Si 包含包含i全部子集全部子集由由 s 决定决定“贡献贡献”权重权重 Shapley值值 i 对合作对合作s“贡献贡献”Shapley合作对策合作对策第33页三人三人(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第34页合作对策应用合作对策应用 污水处理费用合理分担污水处理费用合理分担20km38km河流河流三城镇地理位置示意图三城镇地理位置示意图123 污水处理，排入河流污水处理，排入河流.三城镇可单独建处理厂，三城镇可单独建处理厂，或联合建厂或联合建厂(用管道将污水用管道将污水由上游城镇送往下游城镇由上游城镇送往下游城镇).Q1=5Q3=5Q2=3Q污水量，污水量，L管道长度管道长度建厂费用建厂费用P1=73Q0.712管道费用管道费用P2=0.66Q0.51L第35页污水处理污水处理5 种方案种方案1）单独建厂）单独建厂总投资总投资2）1,2合作合作3）2,3合作合作4）1,3合作合作总投资总投资总投资总投资合作不会实现合作不会实现第36页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怎样分担？怎样分担？第37页特征函数特征函数v(s)联合联合(集集s)建厂比单独建厂节约投资建厂比单独建厂节约投资三三城从城从节约投资节约投资v(I)中得到分配中得到分配 Shapley合作对策合作对策第38页计算计算城城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最大，怎样解释？最大，怎样解释？第39页优点：优点：公正、合理，有公理化基础公正、合理，有公理化基础.如如n个单位治理污染个单位治理污染,通常知道第通常知道第i方单独治理投资方单独治理投资yi 和和n方共同治理投资方共同治理投资Y,及第及第i方不参加时其余方不参加时其余n-1方投资方投资zi(i=1,2,n).确定共同治理时各方分担费用确定共同治理时各方分担费用.其它其它v(s)均不知道均不知道,无法用无法用Shapley合作对策合作对策求解求解Shapley合作对策小结合作对策小结若定义特征函数为合作赢利若定义特征函数为合作赢利(节约投资节约投资)，则有，则有缺点：缺点：需要知道全部合作赢利需要知道全部合作赢利,即要定义即要定义I=1,2,n全部子集全部子集(共共2n-1个个)特征函数，实际上常做不到特征函数，实际上常做不到.第40页设只知道设只知道无无 i 参加时参加时n-1方合作赢利方合作赢利全体合作赢利全体合作赢利求解合作对策其它方法求解合作对策其它方法例例.甲乙丙三人合作经商，若甲乙合作赢利甲乙丙三人合作经商，若甲乙合作赢利7元，元，甲丙合作赢利甲丙合作赢利5元，乙丙合作赢利元，乙丙合作赢利4元，三人元，三人合作赢利合作赢利11元元.问三人合作时怎样分配赢利？问三人合作时怎样分配赢利？第41页（1）协商解）协商解11将剩下赢利将剩下赢利 平均分配平均分配 模型模型以以n-1方合作赢利为下限方合作赢利为下限求解求解 xi 下限下限第42页（2）Nash解解 为现实状况点（谈判时威慑点）为现实状况点（谈判时威慑点）在此基础上在此基础上“均匀地均匀地”分配全体合作赢利分配全体合作赢利B模型模型平均分配赢利平均分配赢利B2）Nash解解 1）协商解）协商解第43页（3）最小距离解）最小距离解模型模型 第第i 方边际效益方边际效益若令若令3）最小距离解）最小距离解 1）协商解）协商解第44页（4）满意解）满意解di现实状况点现实状况点(最最低点低点)ei理想点理想点(最高点最高点)模型模型4）基于满意度解）基于满意度解 1）协商解）协商解第45页（5）Raiffi 解解与协商解与协商解x=(5,4,2)比较比较第46页求解合作对策求解合作对策6种方法（可分为三类）种方法（可分为三类）Shapley合作对策合作对策A类类B类类协商解协商解Nash解解 最小距离解最小距离解满意解满意解di现实状况现实状况,ei理想理想B类类4种方法相同种方法相同第47页例：有一资方例：有一资方(甲甲)和二劳方和二劳方(乙乙,丙丙),仅当资方与最少仅当资方与最少一劳方合作时才赢利一劳方合作时才赢利10元，应怎样分配该赢利？元，应怎样分配该赢利？Raiffi解解C类类第48页B类：类：计算简单，便于了解，可用于各方实计算简单，便于了解，可用于各方实力相差不大情况；普通来说它偏袒强者力相差不大情况；普通来说它偏袒强者.C类：类：考虑了分配上下限，又吸收了考虑了分配上下限，又吸收了Shapley思想，在一定程度上保护弱者思想，在一定程度上保护弱者.A类：类：公正合理；需要信息多，计算复杂公正合理；需要信息多，计算复杂.求解合作对策三类方法小结求解合作对策三类方法小结第49页11.6 加权投票中权力度量加权投票中权力度量 背景背景“一人一票一人一票”显示投票和表决公正显示投票和表决公正.股份制企业每位股东投票和表决权大小由所占股份制企业每位股东投票和表决权大小由所占有有股份股份多少决定多少决定.一些国家、地域议会、政府产生，由所属州、县一些国家、地域议会、政府产生，由所属州、县等各个区域推出代表投票决定等各个区域推出代表投票决定.代表投票权重取决于所代表区域代表投票权重取决于所代表区域人口人口数量数量.经济或政治机构权力分配经济或政治机构权力分配 第50页背景背景经典案例经典案例:美国总统选举实施选举人制度美国总统选举实施选举人制度 美全国美全国50个州和华盛顿特区共个州和华盛顿特区共538张张选举人票选举人票.获选举人票数获选举人票数二分之一以上二分之一以上总统候选人当选总总统候选人当选总统统.各州各州选举人票数选举人票数与该州在国会参、众议员数相等与该州在国会参、众议员数相等.参议员每州两位，众议员人数由各州参议员每州两位，众议员人数由各州人口百分比人口百分比确定确定.各州人口悬殊巨大使各州人口悬殊巨大使各州选举人票数相差很大各州选举人票数相差很大.(如加利福尼亚州选举人票如加利福尼亚州选举人票55张，阿拉斯加州只张，阿拉斯加州只3张张)第51页背景背景经典案例经典案例:美国总统选举实施选举人制度美国总统选举实施选举人制度 总统候选人在各州内进行普选，取得总统候选人在各州内进行普选，取得相对多数相对多数选票候选人得到该州选票候选人得到该州全部选举人票全部选举人票.48个州和华盛顿特区都实施个州和华盛顿特区都实施“胜者全得胜者全得”：在加利福尼亚州以在加利福尼亚州以微弱多数微弱多数普选获胜总普选获胜总统候选人可得到统候选人可得到全部全部55张张选举人票选举人票.若有几个人口多州如此，在选举人投票中就可若有几个人口多州如此，在选举人投票中就可能使各州能使各州累计得票最多候选人累计得票最多候选人反而不能获胜反而不能获胜.选举结果违反选举结果违反全国多数人全国多数人意愿意愿.布什与戈尔进行竞选中，戈尔最终败给布什！第52页问题问题由若干区域由若干区域(如省、县等如省、县等)组成机构中，每区代组成机构中，每区代表数量按照人口百分比分配，进行投票选举和表数量按照人口百分比分配，进行投票选举和表决时，每区全体代表投相同票表决时，每区全体代表投相同票.每区各派一位代表每区各派一位代表(投票人投票人)，按照他们所代表，按照他们所代表各区人口百分比赋予投票权重各区人口百分比赋予投票权重.怎样度量每位代表投票对最终止果影响力怎样度量每位代表投票对最终止果影响力(权力权力).介绍两种合理、度量权力数量指标介绍两种合理、度量权力数量指标.经过实例给出它们应用经过实例给出它们应用.调整投票人权重使其权力大致与代表人口成百分比调整投票人权重使其权力大致与代表人口成百分比.加权投票中权力度量加权投票中权力度量背背景景第53页加权投票与获胜联盟加权投票与获胜联盟 例例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区代表是区代表是独裁者独裁者(能决定投票结果能决定投票结果),其它代表都是其它代表都是傀儡傀儡.改改革革第54页加权投票与获胜联盟加权投票与获胜联盟 加权投票系统加权投票系统投票人集合投票人集合N=A,B,C,(n人人)权重权重w1,w2,wn 定定额额q 投赞成票投票人权重之和投赞成票投票人权重之和 q时决议经过时决议经过.w=w1+w2+wn，普通，普通 w/2wj,则则kikj.第58页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:归一化归一化 第59页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 第60页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为决定者次数为决定者次数.简化简化第61页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）归一化归一化 第62页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)归一化归一化 第63页Banzhaf 指标指标 Shapley指标指标 投票人全投票人全排列排列 对排列对排列由左向右由左向右检验检验决定者决定者 统计每人在全部排列中决统计每人在全部排列中决定者次数定者次数 投票人投票人获胜联盟集获胜联盟集 对对获胜联盟获胜联盟检验检验决定者决定者 统计每人在全部统计每人在全部获胜获胜联盟联盟中决定者次数中决定者次数每个每个排列中有且只有一个排列中有且只有一个决定者决定者每个每个组合中没有或有组合中没有或有(几个几个)决定者决定者(=/n!)已归一化已归一化需需归一化才得到归一化才得到都满足度量权力数量指标应该含有性质都满足度量权力数量指标应该含有性质.第64页加权投票与权力指标应用加权投票与权力指标应用 例例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 第65页例例4极小获胜联盟极小获胜联盟Wm=3A2B,(4A,2A4B)一个一个B在全部排列中决定者次数在全部排列中决定者次数/10！(3A1B)B(2A3B)(2A3B)B(3A1B)一个一个AShapley指标指标=(0.1365,0.1365,0.0635,0.0635)计算计算S=8;2,2,2,2,2,1,1,1,1,1 Shapley指标指标一个一个BShapley指标指标 只需考查只需考查Shapley指标指标 第66页例例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第67页例例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 经过经过党派党派结盟能加强权力吗结盟能加强权力吗?第68页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和和DShapley指标按照指标按照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降低降低.第69页例例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 第70页例例5 “团结就是力量团结就是力量”吗吗？“共和党共和党”不不结结盟盟“共和党共和党”结结盟盟“民主党民主党”不不结结盟盟M=0.275 G=0.350M=0.204 G=0.519“民主党民主党”结结盟盟M=0.367 G=0.306M=0.180 G=0.368 不论不论“民主党民主党”是否结盟，是否结盟，“共和党共和党”结盟总比单干好结盟总比单干好.“共和党共和党”一旦结盟，一旦结盟，“民主党民主党”不结盟更加好不结盟更加好.从从“民主党民主党”角度看角度看,应该尽可能保持大家都是单干局应该尽可能保持大家都是单干局面面,若率先结盟会诱使若率先结盟会诱使“共和党共和党”也结盟也结盟,结果会败得结果会败得很惨很惨.从独立人士角度看从独立人士角度看,若只有若只有“民主党民主党”或或“共和党共和党”结盟自己都有损失结盟自己都有损失,但若两个党均结盟但若两个党均结盟,反而可得渔翁反而可得渔翁之利之利.第71页两种权力指标公理化两种权力指标公理化 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中人数中人数)第72页两种权力指标公理化两种权力指标公理化 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)比较比较.第73页两种权力指标概率解释两种权力指标概率解释 投票人对结果影响力投票人对结果影响力 投票人能左右结果概率投票人能左右结果概率.例例2 S(4)=3;2,1,1RA 事件事件“A能左右能左右结结果果”可解释为在各位投票人可解释为在各位投票人独立地、以独立地、以1/2概率投赞成或概率投赞成或反对票反对票条件下条件下,每位投票人能左右结果概率每位投票人能左右结果概率.Banzhaf 指标指标B,C均以均以1/2概率独立投赞成或反对票概率独立投赞成或反对票 BB投投赞赞成票成票B投投反反对对票票 第74页两种权力指标概率解释两种权力指标概率解释 例例2 S(4)=3;2,1,1p每位投票人独立投赞成票概率每位投票人独立投赞成票概率,q=1-p投反对票概率投反对票概率Shapley指标指标p在在0,1均匀分布均匀分布 A,B,C能左右结果概率能左右结果概率 可解释为在各位投票人可解释为在各位投票人独立且独立且 0,1均匀概率分布地均匀概率分布地投赞成票投赞成票条件下，每位投票人能左右结果概率条件下，每位投票人能左右结果概率.第75页调整加权投票系统调整加权投票系统 例例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,