
数学模型第四版姜启源第十一章博弈模型.ppt
80页第十一章第十一章 博弈模型博弈模型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((p>w>v>0))需求量:密度函数需求量:密度函数f(x)、分布函数、分布函数F(x), F(0)=0订购订购Q份报纸,期望销售量为份报纸,期望销售量为 期望存货量期望存货量期望利润期望利润 最优订购量最优订购量Qr Qr(w) 拣剔诧凋罗浇邑榨滴断刻餐矢咆丁拯格窖拽浮峪裙匈抚愿睦元振戏邦辉趟数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型问题问题假设报社报纸成本价为假设报社报纸成本价为c,,w≥c>v w*完全信息动态博弈:常称完全信息动态博弈:常称Stackelberg Game (两阶段两阶段) 子博弈完美均衡子博弈完美均衡: (w*,,Qr(w))一般一般w*>c Qr(w*) w>b>v)回收协议模型回收协议模型 李饲擦腐足溯完玖逊聪响拖雁滤阴琅怪桓钒鹰垃酌膏瑶拉族缘馅脖锹予华数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型模型二模型二 回收数量协议回收数量协议 报社回收报社回收 达到协调达到协调报童回收报童回收α↑↑,报童利润,报童利润↓↓, 报社利润报社利润↑; 利润任意分配都可达到利润任意分配都可达到 按批发价回收,比例为按批发价回收,比例为α 报童利润报童利润回收协议模型回收协议模型 浇蜡墨夺鲸赤新化彝变攒芒芜贰茄盾恤宾横镁准李喘箱陨闷妥蜂信筐债达数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型模型评述模型评述 •协议参数的确定:协议参数的确定: 不能单方决定 不能单方决定 双方谈判(合作博弈) 双方谈判(合作博弈) •还有很多其他类型的协议,也可以达到协调还有很多其他类型的协议,也可以达到协调•一种更简单的协议一种更简单的协议 批发价 批发价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]区间上的非减函数区间上的非减函数. 不完全信息静态博弈(静态贝叶斯博弈)不完全信息静态博弈(静态贝叶斯博弈)贝叶斯纳什均衡贝叶斯纳什均衡单向改变战略不能单向改变战略不能提高自己效用提高自己效用.信息非对称(不完全信息)信息非对称(不完全信息)模型假设与建立模型假设与建立毖风杠退搽乏承葱绩唁奶米惧厄伺彼缝勒捅咆判瞧卫节岳套旨恼佰课民吾数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型均衡条件均衡条件具体战略具体战略(函数函数)形式不同,均衡就可能不同形式不同,均衡就可能不同.单一价格战略单一价格战略卖方:卖方:买方:买方:双方战略互为最优反应,所以构成双方战略互为最优反应,所以构成贝叶斯纳什均衡贝叶斯纳什均衡!!模型假设与建立模型假设与建立玩雍痴萎殴贰萤肖吭彰颂悯获奴膝催王剩娄琶普便逞锁辛厨云凹狐椎稗较数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型单一价格战略效率为单一价格战略效率为x=0.5效率最大效率最大(3/4)对给定的对给定的(vs, vb),当,当vs
wj, 则则ki≥kj.附喝皖徐楼今旗妊佯蛛赎逼黄巷浚交赫忘熄湍榷帕系谊伴乌撼腿后蠢饼渴数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型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 30φ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 对比对比 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 (j≤7, i>8 )M(j≤7, i≤8 )DMGG (j >7)(i, j)对应左下方方对应左下方方格格,共共272个个(除对角除对角线线).对角线对角线以下方格以下方格~G在在M之前加入之前加入 数数决定者决定者方格方格:M49, G100, D123 φM=49/272=0.180φG= 100/272=0.368φD=0.452 螺稚斗筷探挑啤将泻永撒非吨构荒财异锐从夺给膀忌船嘴晕或胖抡贺篆每数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型例例5 “团结就是力量团结就是力量”吗吗??“共和党共和党”不不结盟盟“共和党共和党”结盟盟“民主党民主党”不不结盟盟φM=0.275 φG=0.350φM=0.204 φG=0.519“民主党民主党”结盟盟φM=0.367 φG=0.306φM=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为决定者的次数为决定者的次数 按排列计算按排列计算 (s~S中人数中人数)忙憾酞浆厘瑞福股炕存溜非宣欣崖律深轻巧烂贰炉立掳效诅几催茵梨弧互数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型两种权力指标的公理化两种权力指标的公理化 i=Ai=Bi=C[A B][A C][A B C][A B][A C]1/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, 1]RA ~事件事件“A能左右能左右结果果”β'可解释为在各位投票人可解释为在各位投票人独立地、以独立地、以1/2的概率投赞成的概率投赞成或反对票或反对票的条件下的条件下, 每位投票人能左右结果的概率每位投票人能左右结果的概率. Banzhaf 指标指标B,C均以均以1/2的概率独立投赞成或反对票的概率独立投赞成或反对票 B~B投投赞成票成票~B投投反反对票票 誓她跺浊愿爬逃耍牲由氯硕透俘蓝漠撮钥谆虱褥投掷砸弟诣肝谈送忽泞搬数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型两种权力指标的概率解释两种权力指标的概率解释 例例2 S(4)=[3; 2, 1, 1]p~每位投票人独立投赞成票的概率每位投票人独立投赞成票的概率, q=1-p投反对票概率投反对票概率Shapley指标指标p在在[0, 1]均匀分布均匀分布 A, B, C能左右结果的概率能左右结果的概率 可解释为在各位投票人可解释为在各位投票人独立且独立且 [0, 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的情况下的情况下, 借助分析极小获胜借助分析极小获胜联盟的办法联盟的办法, 寻找寻找β与与p相近似的加权投票系统相近似的加权投票系统. 斗役肘号围否幌座呈急锋乐鸵吃橱钵各磺根剐缺唱碧庶囚雍脯饺鸭邮蠕拣数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型调整加权投票系统调整加权投票系统 例例1 人口人口比例比例 p=(12, 4, 2, 1, 1) 系统系统S=[11; 12, 4, 2, 1, 1 ] 权重不变、增大定额权重不变、增大定额, 寻找寻找β与与p相近似的投票系统相近似的投票系统. Banzhaf指标指标β=(1, 0, 0, 0, 0)SWmβ=(β1,β2,β3,β4,β5)β=(11/21, 5/21, 3/21, 1/21, 1/21 ) S=[15; 12, 4, 2, 1, 1 ]这个这个β是人口比例是人口比例 p的一个不错的近似的一个不错的近似! [12; 12, 4, 2, 1, 1] [13; 12, 4, 2, 1, 1][AB] ,[AC], [AD] ,[AE][14; 12, 4, 2, 1, 1][AB] ,[AC], [ADE][15; 12, 4, 2, 1, 1][AB] ,[ACD], [ACE][16; 12, 4, 2, 1, 1][AB] ,[ACDE]β2=β3=β4=β5β2=β3β1>β2>β3>β4= β5β3=β4=β5(1, 0, 0, 0, 0)√撰赡缸袭胳疲删藕噎植膘药乞泅搽贼曳戴鸭微虫睬瓶窝钨峭维谐涸欣尊称数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型调整加权投票系统调整加权投票系统 • 合适地定义合适地定义β与与p之间的之间的“距离距离”(β与与p看作看作n维空维空间的两个点间的两个点)作为衡量近似程度的指标作为衡量近似程度的指标. • 按照实际需要确定该指标的一个按照实际需要确定该指标的一个“阈值阈值” 1)给出权重)给出权重w和定额和定额q的初的初值;2)编程计算)编程计算β及及β与与p的距离的距离, 距离小于阈值时停止距离小于阈值时停止,否则转否则转3;;3)改变)改变w和和q, 转转2.当当n较大时调整权重和定额较大时调整权重和定额, 寻找寻找β与与p近似的投票系统近似的投票系统. • 每调整一次权重和定额每调整一次权重和定额, 必须使必须使极小获胜联盟极小获胜联盟的结构有所变化的结构有所变化, β才有可能改进才有可能改进. 俞肚汾抡菌淳褪鸥肠低干电流屎萌俺蔬尿堵集叮挫跋马罢锅挖诽魄坠直躇数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型• 任何一个构造和规则有明确定义的投票系统都可用任何一个构造和规则有明确定义的投票系统都可用极极小获胜联盟小获胜联盟来描述来描述, 并常可表示成并常可表示成加权投票系统加权投票系统(如例如例4). 权力度量模型评述权力度量模型评述 • 存在即使确定了极小获胜联盟也无法表为加权投票系存在即使确定了极小获胜联盟也无法表为加权投票系统的情况统的情况. Hilliard给出区别加权与非加权投票系统的给出区别加权与非加权投票系统的数学方法数学方法, 并提供权重和定额的算法,或者指明不存在并提供权重和定额的算法,或者指明不存在权重和定额的矛盾权重和定额的矛盾[教材参考文献教材参考文献35]. • 两种权力指标常常给出两种权力指标常常给出相同或近似相同或近似的结果的结果, 从理论上从理论上区分它们的数学公理既不直观区分它们的数学公理既不直观, 使用时也不具说服力使用时也不具说服力,所以在应用中公理化方法所以在应用中公理化方法并不能解决选择哪个指标并不能解决选择哪个指标的问的问题题. 挣师锗虫威急伎往吗瑚珐楼娄肩骏伏瞻荧哑恿眯风虎刀衰歇园勿临球究锯数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型权力度量模型评述权力度量模型评述 道理上更浅显道理上更浅显, 容易口头解容易口头解释释, 更易为更易为实际工作者实际工作者接受接受. 作为对策论中著名的作为对策论中著名的Shapley值方法的副产品值方法的副产品在在数学界数学界更有市场更有市场. 适于适于设计设计投票系统投票系统, 在代表在代表尚未选出之前假定所有投票尚未选出之前假定所有投票意愿的等可能性是合理的意愿的等可能性是合理的. 适于适于评价评价投票系统投票系统, 代表代表已经选出已经选出, 他们的立场为他们的立场为众人所知众人所知. • 在加权投票系统中定义在加权投票系统中定义量化的权力指标量化的权力指标,是将数学,是将数学应用于社会政治领域的一个有意义的范例应用于社会政治领域的一个有意义的范例. • 提出与提出与“计量经济学计量经济学”类似的新学科类似的新学科——“计量政治计量政治学学”. . Shapley指标指标 Banzhaf指标指标 狭汞邻肠嘱拎鱼嗡渊怖俯碴溃矢孝桩迪柱淆惜珠耽台宙循栈海免皇稳震郭数学模型第四版姜启源第十一章博弈模型数学模型第四版姜启源第十一章博弈模型。
