数学建模博弈模型[共80页]

1、第十一章第十一章 博弈模型博弈模型 11.1 进攻与撤退的抉择进攻与撤退的抉择 11.2 让报童订购更多的报纸让报童订购更多的报纸 11.3 “一口价一口价”的战略的战略 11.4 不患寡而患不均不患寡而患不均 11.5 效益的合理分配效益的合理分配 11.6 加权投票中权力的度量加权投票中权力的度量 单一决策主体单一决策主体 决策变量决策变量 目标函数目标函数 约束条件约束条件 决策主体的决策决策主体的决策 行为发生直接相行为发生直接相 互作用互作用 (相互影响相互影响) 博弈模型博弈模型 非合作博弈非合作博弈合作博弈合作博弈 三要素三要素 博弈模型博弈模型 (Game Theory) 多个

2、决策主体多个决策主体 优化模型优化模型 (Optimization) 决策问题（Decision Problem） 静态、动态静态、动态 信息完全、不完全信息完全、不完全 军事、政治、经济、企业管理和社会科学中应用广泛军事、政治、经济、企业管理和社会科学中应用广泛 1944年年6月初，盟军在诺曼底登陆成功月初，盟军在诺曼底登陆成功. 到到8月初的形势：月初的形势： 背背 景景 11.1 进攻与撤退的抉择进攻与撤退的抉择 双方应该如何决策双方应该如何决策 ？ 强 化强 化 缺口缺口 盟军盟军 (预备队预备队) 撤退撤退 进攻进攻 德军德军 盟军盟军(加加) 盟军盟军(英英) 盟军盟军(美一美一)

3、 盟 军盟 军 (美三美三) 东进东进 原地原地 待命待命 模型假设模型假设 博弈参与者为两方（盟军和德军）博弈参与者为两方（盟军和德军） 盟军有盟军有3种使用其预备队的行动：强化缺口，原地种使用其预备队的行动：强化缺口，原地 待命，东进；德军有待命，东进；德军有2种行动：向西进攻或向东撤退种行动：向西进攻或向东撤退. 博弈双方博弈双方完全理性完全理性，目的都是使战斗中己方获得，目的都是使战斗中己方获得 的净胜场次（胜利场次减去失败场次）尽可能多的净胜场次（胜利场次减去失败场次）尽可能多. 盟军胜盟军胜1场场盟军败盟军败2场场东进东进 无战斗无战斗盟军胜盟军胜2场场原地待命原地待命 无战斗无战

4、斗盟军胜盟军胜1场场强化缺口强化缺口 向东撤退向东撤退向西进攻向西进攻盟军盟军 德军德军 完全信息完全信息 静态博弈静态博弈 共同知识共同知识(以上信息双方共有以上信息双方共有) 双方同时做出决策双方同时做出决策 博弈模型博弈模型 博弈参与者集合博弈参与者集合N=1,2(1为盟军，为盟军，2为德军为德军) 用用u1(a1，a2)表示对盟军产生的结果，即净胜场次，表示对盟军产生的结果，即净胜场次， 称为盟军的称为盟军的效用函数效用函数. 盟军胜盟军胜1场场盟军败盟军败2场场东进东进 无战斗无战斗盟军胜盟军胜2场场原地待命原地待命 无战斗无战斗盟军胜盟军胜1场场强化缺口强化缺口 向东撤退向东撤退向

5、西进攻向西进攻盟军盟军 德军德军 12 02 01 23ij mM 盟军行动盟军行动a1 A1=1,2,3(强化缺口强化缺口/原地待命原地待命/东进东进)； 德军行动德军行动a2 A2=1,2(进攻进攻/撤退撤退). (行动：即纯战略行动：即纯战略) 支付矩阵支付矩阵 （Payoff Matrix） 完全竞争完全竞争: 零和博弈零和博弈 (常数和博弈常数和博弈) u2(a1，a2)对应对应 M 博弈的解的概念：博弈的解的概念：纳什均衡纳什均衡 (NE: Nash Equilibrium) 不存在不存在(纯纯)NE .2 , 1),(),( ,3 , 2 , 1),(),( 22 * 12 *

6、2 * 12 1 * 211 * 2 * 11 aaauaau aaauaau (纯战略纯战略)纳什均衡纳什均衡 Nash: 1994年获诺贝尔经济学奖年获诺贝尔经济学奖 NE: 单向改变战略不能提高自己效用，单向改变战略不能提高自己效用，即每一方的战略即每一方的战略 对于他方的战略而言都是最优的对于他方的战略而言都是最优的,称为称为最优反应最优反应. 12 02 01 23ij mM (纯纯)NE: a*=(a1*, a2*) =(2, 2) 1, 12 , 2 1 , 22, 2 1 , 11, 1 M 非常数和非常数和 博弈博弈(双矩双矩 阵表示阵表示) 混合战略（策略：混合战略（策略：

7、Strategy) 盟军的盟军的混合战略混合战略集集 期望收益期望收益 盟军盟军 德军德军 S1=p=(p1, p2, p3) | 3 1 1, 10 i ii pp 德军的德军的混合战略混合战略集集 S2= q=(q1, q2) | 2 1 1, 10 i ii qq T Sp pMq 1 max T Sq pMq 2 min 完全信息静态博弈完全信息静态博弈 有限博弈矩阵博弈有限博弈矩阵博弈 (2人人) 零和博弈零和博弈常数和博弈常数和博弈 ),(),( ),( 12 3 1 2 1 1 qpUqpU qmppMqqpU ij jiji T 模型求解模型求解 理性推理：理性推理：不管自己怎

8、么做，另一方总是希望使自不管自己怎么做，另一方总是希望使自 己得分尽量低己得分尽量低.（二人零和博弈，完全竞争）（二人零和博弈，完全竞争） 盟军盟军 德军德军 T Sp pMq 1 max T Sq pMq 2 min 线性线性 规划规划 从一个给定的战略中期望得到的赢得，总是从一个给定的战略中期望得到的赢得，总是 采用该策略时他们可能得到的最坏的赢得！采用该策略时他们可能得到的最坏的赢得！ 盟军可以用盟军可以用min pM来衡量策略来衡量策略p的好坏的好坏 max U1(p) = min pM min U2(q) = max MqT 德军可以用德军可以用max MqT来衡量策略来衡量策略q的

9、好坏的好坏 (p*, q*): 混合混合(策略策略)纳什均衡纳什均衡(Mixed NE) p2*=3/5，p3*=2/5 q1*=1/5，q2*=4/5 最优值均为最优值均为2/5 占优占优(dominate)：盟军的行动：盟军的行动2占优于占优于1 （前面的非常数和博弈（前面的非常数和博弈M类似）类似） 混合策略似乎不太可行混合策略似乎不太可行! 但但概率概率可作为可作为参考参考. -现实现实：盟军让预备队原地待命（行动：盟军让预备队原地待命（行动2），而德军），而德军 没有选择撤退（行动没有选择撤退（行动2），结果德军大败），结果德军大败. 模型评述模型评述 博弈规则博弈规则至关重要的，如

10、参与人决策的时间顺序、至关重要的，如参与人决策的时间顺序、 决策时拥有哪些信息等决策时拥有哪些信息等. 11 01 00 M 多人多人(或非常数和或非常数和)博弈问题，一般不能用上面的线性博弈问题，一般不能用上面的线性 规划方法求解，而通过纳什均衡的定义求解规划方法求解，而通过纳什均衡的定义求解. 小结：博弈模型的基本要素小结：博弈模型的基本要素 参与人参与人 理性假设理性假设 行动顺序（静态、动态）行动顺序（静态、动态） 信息结构（完全、不完全）信息结构（完全、不完全） 行动空间（及战略空间）行动空间（及战略空间） 效用函数效用函数 参与者完全理性参与者完全理性(最大化效用最大化效用) 其他

11、因素其他因素 纳什均衡纳什均衡单向改变战略不能提高自己效用单向改变战略不能提高自己效用 11.2 让报童订购更多的报纸让报童订购更多的报纸 报报 童童 模模 型型 回回 顾顾 订购价订购价w，零售价，零售价p，处理价，处理价v（pwv0） 需求量：密度函数需求量：密度函数f(x)、分布函数、分布函数F(x), F(0)=0 订购订购Q份报纸，期望销售量为份报纸，期望销售量为 QQ Q Q Q dxxFQQFQdxxFxxF dxxQfdxxxfQS 00 0 0 )()(1 ()(| )( )()()( 期望存货量期望存货量 Q dxxFQSQQI 0 )()()( 期望利润期望利润 QvwQ

12、SvpwQQvIQpSQG)()()()()()( 最优订购量最优订购量Qr vp wp QF r )( Qr(w) 问题问题 假设报社报纸成本价为假设报社报纸成本价为c，wcv )()( MaxwQcw r cw vp wp Fcw 1 )( w* 完全信息动态博弈：常称完全信息动态博弈：常称Stackelberg Game (两阶段两阶段) 子博弈完美均衡子博弈完美均衡: (w*，Qr(w) vp cp QF )( * 一般一般w*c Qr(w*) wbv) bp wp vp cp )()(bp vp vc bbww b )()()( )()()( )()()()()( * bUbU vp

13、 vb bU bUbU vp bp bU QvcQSvpbUbU srs srr sr 回收协议模型回收协议模型 模型二模型二 回收数量协议回收数量协议 报社回收报社回收 达到协调达到协调 报童回收报童回收 ，报童利润，报童利润, 报社利润报社利润; 利润任意分配都可达到利润任意分配都可达到 按批发价回收，比例为按批发价回收，比例为 (1) 1 0(1)(1) ( )( )d() ( )d( )d QQQ QQ I QQf xxQx f xxF xx (1) 21 0 ( )( )( )( )d Q I QI QI QF xx 报童利润报童利润 12 (1) (1)0 ( , ,)( )( )

14、( ) ()( )d()( )d r QQ Q UwQpS QwI QvI QwQ pwQF xxpvF xx 0 ),( r Q r Q QwU 0)1()1)()(1)( rr QFvwQFwp vp cp QF )( *)1()1)()/()(1)( * QFvwvpcpwp )1()1)()( )( )( * QFvpvc vcvp vww q 回收协议模型回收协议模型 模型评述模型评述 协议参数的确定：协议参数的确定： 不能单方决定不能单方决定 双方谈判（合作博弈）双方谈判（合作博弈） 还有很多其他类型的协议，也可以达到协调还有很多其他类型的协议，也可以达到协调 一种更简单的协议一种

15、更简单的协议 批发价批发价w成本成本c 收取一定加盟费收取一定加盟费 如何评价比较协议的优缺点？如何评价比较协议的优缺点？ 是否能达到协调是否能达到协调是否能任意分配利润是否能任意分配利润 协议执行成本有多高协议执行成本有多高 11.3 “一口价一口价”的战略的战略 背景背景 为了节省为了节省“讨价还价讨价还价”时间，考虑时间，考虑“一口价一口价” 模式模式. 双方同时报价双方同时报价：若买价：若买价卖价，则以均价成交卖价，则以均价成交; 否则不成交否则不成交. 问题问题 双方应如何报价？双方应如何报价？ 双方总能成交吗？（效率估计）双方总能成交吗？（效率估计） “讨价还价讨价还价”很浪费买卖

16、双方的宝贵时间很浪费买卖双方的宝贵时间. 模型假设与建立模型假设与建立 卖方知道物品对自己的价值，但买方不知道卖方知道物品对自己的价值，但买方不知道. 买方知道物品对自己的价值，但卖方不知道买方知道物品对自己的价值，但卖方不知道. 双方都知道（如猜出）对方价值的分布信息双方都知道（如猜出）对方价值的分布信息. 卖方价值卖方价值vs, 买方价值买方价值vb, 均服从均服从 0,1 上的均匀分布上的均匀分布 卖方报价卖方报价ps, 买方报价买方报价pb, pb ps时成交价时成交价p (pb+ps)/2 成交效用：卖方成交效用：卖方U1=p- vs, 买方买方U2= vb p; 不成交不成交: 0

17、 双方完全理性双方完全理性(最大化自己的期望效用最大化自己的期望效用 ). 以上为双方的共同知识以上为双方的共同知识. 卖方报价卖方报价ps ps(vs) 买方报价买方报价pb pb(vb) 双方战略双方战略 战略组合战略组合( ps(vs), pb(vb) 何时构成均衡？何时构成均衡？ 定义在定义在0，1区间上、取值也区间上、取值也 在在0，1区间上的非减函数区间上的非减函数. 不完全信息静态博弈（静态贝叶斯博弈）不完全信息静态博弈（静态贝叶斯博弈） 贝叶斯纳什均衡贝叶斯纳什均衡 单向改变战略不能单向改变战略不能 提高自己效用提高自己效用. 信息非对称（不完全信息）信息非对称（不完全信息）

18、模型假设与建立模型假设与建立 均衡条件均衡条件 具体战略具体战略(函数函数)形式不同，均衡就可能不同形式不同，均衡就可能不同. 单一价格战略单一价格战略 卖方：卖方： 买方：买方： 双方战略互为最优反应，所以构成双方战略互为最优反应，所以构成贝叶斯纳什均衡贝叶斯纳什均衡！ )(Pr* 2 )(| )( max sbbs sbbbbs p pvpv pvpvpEp s )(Pr* 2 )(| )( max ssb ssbssb b p vpp vppvpEp v b xv xvx vp s s ss , 1 , )( xv xvx vp b b bb , 0 , )( 模型假设与建立模型假设与建

19、立 单一价格战略效率为单一价格战略效率为 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 iji xxxxxxxU jiiijiii 3, 2 , 1 0 ,max0 ,max),( 21 0 ii 2/1 i 模型求解模型求解 如果不接受，则如果不接受，则x1=x2=0;

20、U1(s)=U2(s)=0 . 若若s1/2,则则x2 x1 乙的最优反应乙的最优反应 乙的最优反应（给定乙的最优反应（给定s） 如果接受，则如果接受，则x1=1-s, x2=s. 若若s1/2,则则x2x1 U2(s)0 0 ,max0 ,max),( 21jiiijiii xxxxxxxU 1/20 ) 12()( 22 sssU 2222 )21 ()21 ()(ssssU s )21/()( 222 s 当当 s 接受接受; 否则，不接受否则，不接受)( 2 s 2/1)(0 2 s易知易知 (s1/2, 两者一致两者一致) 2/1 2 模型求解模型求解 Case 1: 甲知道乙的甲知

21、道乙的2 若若s1/2,则则x2 x1 甲的决策甲的决策 s=1/2时达到最大值时达到最大值1/2 甲的决策甲的决策(只需考虑乙接受情形只需考虑乙接受情形) ) 12(1)( 11 sssU 若若s1/2,则则x2 x1 但但 s )( 2 s ssssU) 12(1)21 (1)( 1111 )21/()( 222 * ss 2/1 1 均衡均衡: (s*,接受接受) s*严格小于严格小于50%; 是乙的是乙的“愤怒愤怒”系数系数2的增函数的增函数. 模型求解：甲的决策模型求解：甲的决策 Case 2: 甲不知道乙的甲不知道乙的2, 但知道但知道2的分布的分布F(2) 若若s1/2,则则x2

22、 x1 甲的决策甲的决策 若若s1/2,则则x2 x1 U1(s)=1-s-1(2s-1) 同前同前 期望效用期望效用 乙接受概率乙接受概率 s* 1)(min 0)(max F F )(, 1 )()(),21/( )(, 0 ss sssssF ss p )(,) 12(1 )()(),21/() 12(1 )(, 0 )( 11 111 sss sssssFs ss sEU )21/() 12(1 max 11 )()( ssFs sss 模型解释模型解释 甲永远不会提出大于甲永远不会提出大于/的方案的方案s 乙拒绝过小的方案乙拒绝过小的方案s 很好地解释了实际中的最后通牒博弈很好地解释

23、了实际中的最后通牒博弈. 乙接受概率随乙接受概率随s增加不减增加不减 参考文献参考文献 11.5 效益的合理分配效益的合理分配 11 321 xxx 4 5 7 32 31 21 xx xx xx 例例 甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元， 甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，元， 三人合作获利三人合作获利11元元. 又知每人单干获利又知每人单干获利1元元. 问三人合作时如何分配获利？问三人合作时如何分配获利？ 记甲乙丙三人分配为记甲乙丙三人分配为 ),( 321 xxxx 解不唯一解不唯一 (5，3，3) (4，4，3)

24、(5，4，2) 1, 321 xxx )( 1 Ivx n i i niivxi, 2 , 1),( 212121 0 sssvsvssv v ),()()( )( ,2, 1nI集合 (1) Shapley合作对策合作对策 满足实函数，子集)(svIs I,v n人合作对策，人合作对策，v特征函数特征函数 ),( 21n xxxxn人从人从v(I)得到的分配，满足得到的分配，满足 v(s) 子集子集s的获利的获利 ! )!1()!( )( n ssn sw niisvsvswx i Ss i ,),()()(21 公理化方法公理化方法 s 子集子集 s中的元素数目，中的元素数目， Si 包含

25、包含i的所有子集的所有子集 )( sw由由 s 决定的决定的“贡献贡献”的权重的权重 Shapley值值 )()(isvsv i 对合作对合作s 的的“贡献贡献”)(si Shapley合作对策合作对策 三人三人(I=1,2,3)经商中甲的分配经商中甲的分配x1的计算的计算 1/3 1/6 1/6 1/3 )1()()(svsvsw )( sw s )1()(svsv )1(sv )(sv 1 S 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()()( 1 1 svs

26、vswx Ss 1 2 2 3 合作对策的应用合作对策的应用 污水处理费用的合理分担污水处理费用的合理分担 20km38km 河流河流 三城镇地理位置示意图三城镇地理位置示意图 1 2 3 污水处理，排入河流污水处理，排入河流. 三城镇可单独建处理厂，三城镇可单独建处理厂， 或联合建厂或联合建厂(用管道将污水用管道将污水 由上游城镇送往下游城镇由上游城镇送往下游城镇). Q1=5 Q3=5 Q2=3 Q污水量，污水量，L管道长度管道长度 建厂费用建厂费用P1=73Q0.712 管道费用管道费用P2=0.66Q0.51L 230)3(,160)2(,230573) 1 ( 712. 0 CCC

27、35020566. 0)35(73)2 , 1 ( 51. 0712. 0 C 36538366. 0)53(73)3 , 2( 51. 0712. 0 C 46358566. 0)55(73) 3 , 1 ( 51. 0712. 0 C 460)3() 1 (CC 污水处理的污水处理的5 种方案种方案 1）单独建厂）单独建厂 620)3()2() 1 ( 1 CCCD总投资总投资 2）1, 2合作合作 3）2, 3合作合作 4）1, 3合作合作 580)3()2 , 1 ( 2 CCD总投资总投资 595) 3 , 2() 1 ( 3 CCD总投资总投资 合作不会实现合作不会实现 55638

28、) 35(66. 0 20566. 0)535(73) 3 , 2 , 1 ( 51. 0 51. 0712. 0 5 CD 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=73 D5 城城3建议：建议：d1 按按 5:3:5分担分担, d2,d3由城由城1,2担负担负 城城2建议：建议：d3由城由城1,2按按 5:3分担分担, d2由城由城1担负担负 城城1计算：计算：城城3分担

29、分担 d1 5/13=174C(3), 城城2分担分担 d1 3/13+d3 3/8 =132C(1) 不同意不同意! ! D5如何分担？如何分担？ 230) 3( 160) 2( 230) 1 ( C C C 0)3()2()1 (,0)(vvvv 3 ,2, 1I集合 特征函数特征函数v(s)联合联合(集集s)建厂比单独建厂节约的投资建厂比单独建厂节约的投资 ),( 321 xxxx 三三城从城从节约投资节约投资v(I)中得到的分配中得到的分配 40350160230)2 , 1 ()2() 1 ()21 (CCCv 64556230160230) 3 , 2 , 1 () 3 () 2(

30、) 1 ()( 0) 31 ( 25365230160) 3 , 2() 3 () 2() 32( CCCCIv v CCCv Shapley合作对策合作对策 计算计算城城1从从节约投资中得到的分配节约投资中得到的分配x1 )1()()(svsvsw )(sw s ) 1()(svsv ) 1(sv )(sv s1 1 2 1 3 I 0 40 0 64 0 0 0 25 0 40 0 39 1 2 2 3 1/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 三

31、城在总投资三城在总投资556中的分担中的分担 x2 =32.1, x3=12.2x2最大，如何解释？最大，如何解释？ 优点：优点：公正、合理，有公理化基础公正、合理，有公理化基础. 如如n个单位治理污染个单位治理污染, 通常知道第通常知道第i方单独治理的投资方单独治理的投资yi 和和n方共同治理的投资方共同治理的投资Y, 及第及第i方不参加时其余方不参加时其余n-1方的方的 投资投资zi (i=1,2, ,n). 确定共同治理时各方分担的费用确定共同治理时各方分担的费用. i ij j zyiIv )( 其他其他v(s)均不知道均不知道, 无法用无法用Shapley合作对策合作对策求解求解 S

32、hapley合作对策小结合作对策小结 若定义特征函数为合作的获利若定义特征函数为合作的获利(节约的投资节约的投资)，则有，则有 ,)(),()(YyIvniiv n i i 1 210 缺点：缺点：需要知道所有合作的获利需要知道所有合作的获利, 即要定义即要定义I=1,2,n 的的所有子集所有子集(共共2n-1个个)的特征函数，实际上常做不到的特征函数，实际上常做不到. ),( n bbb 1 记 设只知道设只知道)(iIvbi无无 i 参加时参加时n-1方合作的获利方合作的获利 )(IvB及全体合作的获利全体合作的获利 0 21 in xxxxxB),(的分配求各方对获利 ),(),7 ,

33、5 , 4(11 321 xxxxbB求，即已知 求解合作对策的其他方法求解合作对策的其他方法 例例. 甲乙丙三人合作经商，若甲乙合作获利甲乙丙三人合作经商，若甲乙合作获利7元，元， 甲丙合作获利甲丙合作获利5元，乙丙合作获利元，乙丙合作获利4元，三人元，三人 合作获利合作获利11元元. 问三人合作时如何分配获利？问三人合作时如何分配获利？ （1）协商解）协商解 TT 0 , 0 AxbA 1 1 nni i i bxx bxx Bx 11 将剩余获利将剩余获利 平均分配平均分配 i xB n B bb n xB n xx iiiii 1 )( 1 11),7 , 5 , 4(.Bb例 模型模

34、型 以以n-1方合作的获利为下限方合作的获利为下限 T T Axb 求解求解 iii bb n x 1 1 xi 的下限的下限 , 3),1 , 3 , 4( i xBx ) 2 , 4 , 5() 1 , 1 , 1 ( xx （2）Nash解解 ),( 1n ddd记为现状点（谈判时的威慑点）为现状点（谈判时的威慑点） ii i i i i dx Bx dx s.t. )(xma i i xd 在此基础上在此基础上“均匀地均匀地”分配全体合作的获利分配全体合作的获利B 模型模型 0 i d )( 1 iii dB n dx 平均分配获利平均分配获利B 2）Nash解解 1）协商解）协商解

35、（3）最小距离解）最小距离解的上限为记xxxx n ),( 1 ii i i ii xx Bx xx s.t. )(nmi 2 模型模型 第第i 方的边际效益方的边际效益 ii bBx若令若令 n B bb n x iii 1 11),7 , 5 , 4(.Bb例 )( 1 Bx n xx iii 3）最小距离解）最小距离解 1）协商解）协商解 , 6),4 , 6 , 7( Bxx i ) 2 , 4 , 5 () 2 , 2 , 2 (xx （4）满意解）满意解 ii ii i de dx u 满意度 Bx u i i i s.t. )nmi(xma di现状点现状点(最低点最低点) ei

36、理想点理想点(最高点最高点) 模型模型 ii i i xexd,4）基于满意度的解）基于满意度的解 1）协商解）协商解 iii xed , 0 )( * * iiii ii i deudx de dB u 的比例分配中在按 ii i i i xxB x x x （5）Raiffi 解解 jj xbBnjj获利为方合作时的原来无参与当,1)( jini n x xx x x j ii j j , 1, ) 1(2 , 2 :)1的分配基础上进行方合作获利的分配（在Bnx 方再等分方平分，和先由11nnjx j 得到再平均取,nj21 ij j i ii x n x n x n n x ) 1(2

37、 1 2 11 ) 4 , 6 , 7 (),1 , 3 , 4(xx 与协商解与协商解x=(5,4,2)比较比较 11),7 , 5 , 4(.Bb例 ) 12 5 2, 12 11 3, 3 2 4（x 求解合作对策的求解合作对策的6种方法（可分为三类）种方法（可分为三类） Shapley合作对策合作对策 A 类类 B 类类 ! )!1()!( )( n ssn sw niisvsvswx i Ss i , 2 , 1),()()( )(),(IvBiIvbi只需 Issv),(需要所有 协商解协商解 )( 1 iii xB n xx 下限 i x Nash解解 )( 1 iii dB n

38、 dx 现状 i d 最小距离解最小距离解 )( 1 Bx n xx iii 上限 i x 满意解满意解 )( iiiii ii i i deudx de dB u di现状现状, ei理想理想 ii i i xexd, ii bBx, 1b Ax B类类4种方法相同种方法相同 例：有一资方例：有一资方(甲甲)和二劳方和二劳方(乙乙,丙丙), 仅当资方与至少仅当资方与至少 一劳方合作时才获利一劳方合作时才获利10元，应如何分配该获利？元，应如何分配该获利？ Raiffi解解C 类类 )(),(IvBiIvbi只需 方再等分方平分，和先由上限对每个11,nnjxj j 10)(),10,10,

39、0(),(.IvBbiIvbB i )67. 1 ,67. 1 ,67. 6().Shapley(xA )0 , 0 ,10(,xbBx ii )0 , 0 ,10( 1 T T bAx )83. 0 ,83. 0 ,34. 8(x ij j i ii x n x n x n n xC ) 1(2 1 2 11 ).Raiffi( )0 ,0 ,10(x B类：类：计算简单，便于理解，可用于各方实计算简单，便于理解，可用于各方实 力相差不大的情况；一般来说它偏袒强者力相差不大的情况；一般来说它偏袒强者. C类：类： 考虑了分配的上下限，又吸取了考虑了分配的上下限，又吸取了 Shapley的思想

40、，在一定程度上保护弱者的思想，在一定程度上保护弱者. A类：类：公正合理；需要信息多，计算复杂公正合理；需要信息多，计算复杂. 求解合作对策的三类方法小结求解合作对策的三类方法小结 11.6 加权投票中权力的度量加权投票中权力的度量 背景背景 “一人一票一人一票”显示投票和表决的公正显示投票和表决的公正. 股份制公司每位股东投票和表决权的大小由所股份制公司每位股东投票和表决权的大小由所 占有的占有的股份股份多少决定多少决定. 一些国家、地区的议会、政府的产生，由所属的一些国家、地区的议会、政府的产生，由所属的 州、县等各个区域推出的代表投票决定州、县等各个区域推出的代表投票决定. 代表投票的权

41、重取决于所代表区域的代表投票的权重取决于所代表区域的人口人口数量数量. 经济或政治机构权力的分配经济或政治机构权力的分配 背景背景典型案例典型案例: : 美国总统选举实行的选举人制度美国总统选举实行的选举人制度 美全国美全国50个州和华盛顿特区共个州和华盛顿特区共538张张选举人票选举人票. 获选举人票数获选举人票数一半以上一半以上的总统候选人当选总统的总统候选人当选总统. 各州各州选举人票数选举人票数与该州在国会的参、众议员数相等与该州在国会的参、众议员数相等. 参议员每州两位，众议员人数由各州参议员每州两位，众议员人数由各州人口比例人口比例确定确定. 各州人口悬殊巨大使各州人口悬殊巨大使各

42、州选举人票数相差很大各州选举人票数相差很大. (如加利福尼亚州选举人票如加利福尼亚州选举人票55张，阿拉斯加州只张，阿拉斯加州只3张张) 背景背景典型案例典型案例: : 美国总统选举实行的选举人制度美国总统选举实行的选举人制度 总统候选人在各州内进行普选，获得总统候选人在各州内进行普选，获得相对多数相对多数 选票的候选人得到该州的选票的候选人得到该州的全部选举人票全部选举人票. 48个州和华盛顿特区都实行个州和华盛顿特区都实行“胜者全胜者全 得得” ： 在加利福尼亚州以在加利福尼亚州以微弱多数微弱多数普选获胜的普选获胜的 总统候选人可得到总统候选人可得到全部全部55张张选举人票选举人票. 若有

43、几个人口多的州如此，在选举人投票中就若有几个人口多的州如此，在选举人投票中就 可能使各州可能使各州累计得票最多的候选人累计得票最多的候选人反而不能获胜反而不能获胜. 选举结果违反选举结果违反全国多数人全国多数人的意愿的意愿. 2000年年布什布什与与戈尔戈尔进行的竞选中，戈尔最终败给布什！进行的竞选中，戈尔最终败给布什！ 问题问题 由若干区域由若干区域(如省、县等如省、县等)组成的机构中，每区组成的机构中，每区 代表的数量按照人口比例分配，进行投票选举代表的数量按照人口比例分配，进行投票选举 和表决时，每区的全体代表投相同的票和表决时，每区的全体代表投相同的票. 每区各派一位代表每区各派一位代

44、表(投票人投票人)，按照他们所代表，按照他们所代表 的各区人口比例赋予投票的权重的各区人口比例赋予投票的权重. 如何度量每位代表的投票对最终结果的影响力如何度量每位代表的投票对最终结果的影响力(权力权力). 介绍两种合理的、度量权力的数量指标介绍两种合理的、度量权力的数量指标. 通过实例给出它们的应用通过实例给出它们的应用. 调整投票人的权重使其权力大致与代表的人口成比例调整投票人的权重使其权力大致与代表的人口成比例. 加权投票中权力的度量加权投票中权力的度量 背背 景景 加权投票与获胜联盟加权投票与获胜联盟 例例1 一县一县5区区(A, B, C, D, E )人口为人口为 60, 20,

45、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区代表是区代表是独裁者独裁者(能决定投

46、票结果能决定投票结果), 其他代表都是其他代表都是傀儡傀儡. 改改 革革 加权投票与获胜联盟加权投票与获胜联盟 加权投票系统加权投票系统 投票人集合投票人集合N=A, B, C, (n人人) 权重权重w1, w2, ,wn 定额定额q 投赞成票的投票人权重之和投赞成票的投票人权重之和 q时决议通过时决议通过. w=w1+ w2+wn，一般，一般 w/2wj, 则则kikj. Shapley权力指标权力指标 S(4)=3; 2, 1, 1 例例2 3位投票人的位投票人的全排列全排列: ABC, ACB, BAC, BCA, CAB, CBA 主任主任A,教授教授B,学生学生C的加权投票系统的加权

47、投票系统 ABC: 从从A增至增至AB时时AB变为获胜联盟变为获胜联盟 ACB: 从从A增至增至AC时时AC变为获胜联盟变为获胜联盟 BCA:从从BC增至增至BCA时时BCA变为获胜联盟变为获胜联盟 ABC ACB 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!个全个全排列排列; 对每一个排列对每一个排列由左向右由左

48、向右依次检查，若某位投票人加入依次检查，若某位投票人加入 时该集合变成获胜联盟，称该投票人为时该集合变成获胜联盟，称该投票人为决定者决定者(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) B和和C对称对称, 2=3 Shapley权力指标权力指标 例例3 某股份公司某股份公司4个股东分别持有个股东分

49、别持有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

50、 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的加入才成为获胜联盟

51、的加入才成为获胜联盟 AC: 由于由于A的加入才成为获胜联盟的加入才成为获胜联盟 由于由于C的加入才成为获胜联盟的加入才成为获胜联盟 ABC: 由于由于A的加入才成为获胜联盟的加入才成为获胜联盟 AB AC ABC A下有下有3条横线，条横线，B, C下各有下各有1条横线条横线 Banzhaf指标（指标（3，1，1） （3/5, 1/5, 1/5） 归一化归一化 Banzhaf 权力指标权力指标 写出投票人的写出投票人的获胜联盟集获胜联盟集W; 对每一个对每一个获胜联盟获胜联盟检查检查每位投票人是否每位投票人是否决定者决定者; 将每位投票人在所有将每位投票人在所有获胜联盟获胜联盟中的成为中的成

52、为决定者的次数决定者的次数 归一化归一化, 定义为定义为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指标指标 投票人的全投票人的全排列排列 对排列对排列

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

54、比赛设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

55、, a, a, a, 1, 1, 1, 1, 1 (4A , 2A4B) ,4qa ,42qa,23qa 第第1组组5人权重各人权重各2, 第第2组人权重各组人权重各1, 按简单多数规则执行按简单多数规则执行. a=2, q=8 例例4 极小获胜联盟极小获胜联盟Wm = 3A2B , (4A , 2A4B) 一个一个B在所有排列中的决定者次数在所有排列中的决定者次数/ 10！ (3A1B)B(2A3B) (2A3B)B(3A1B) ! 5 ! 4CC 1 4 3 5 ! 5 ! 4CC 3 4 2 5 0635. 0)CCCC( !10 ! 5 ! 4 3 4 2 5 1 4 3 5 一个一个

56、A的的Shapley指标指标 1365. 0)5 63 4 1 ( 5 1 =(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可能成为决定者的那些获胜联盟类型和个数可能成为决定者的那些获胜联盟类型和个数 A为决定者的次数与为决定者的次数与B为决定者的次数之比为决定

57、者的次数之比 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票通过票通过. 在在独立独立和党派和党派结盟结盟情况下计算

58、议员的情况下计算议员的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 个1M M加入

59、加入, 成为决定者成为决定者 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增加增加

60、, G,D减少减少. 例例5 “团结就是力量团结就是力量”吗？吗？ 3. “共和党共和党”14位议员也结盟位议员也结盟, 系统系统S(3) =21;11,14,1,1 15 个1MG 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 M 加加 入位置入位置 i G 加加 入入 位位 置置 j D (j7, i8 ) M(j7, i8 ) D M G G (j 7) (i, j)对应左下方方格对应左下方方格, 共共272个个(除对角线除对角线). 对角线对角线以下方格以下