合作对策.ppt

《合作对策.ppt》由会员分享，可在线阅读，更多相关《合作对策.ppt（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、7.5 7.5 合作的分配对策合作的分配对策n 一一.背景与问题背景与问题n 1.背景：两个实际问题：背景：两个实际问题：n A.沿河有三个城镇沿河有三个城镇 A、B、C 依次从上游向下游依次从上游向下游排列。城镇的污水需经处理后方可排入河内。排列。城镇的污水需经处理后方可排入河内。n三镇可以单独建厂处理污水，也可以联合建厂，用三镇可以单独建厂处理污水，也可以联合建厂，用管道送水（从上游向下游）集中处理。管道送水（从上游向下游）集中处理。nA、B 的距离为的距离为20km，B、C 的距离为的距离为 38 km。n n如果用如果用Q表示处理污水的量，表示处理污水的量，nL表示管道的长度，表示管道

2、的长度，n按照经验，建污水处理厂的费用为按照经验，建污水处理厂的费用为 nPF=73Q0.712(万元万元),n铺设管道的费用为铺设管道的费用为GF=0.66Q0.51L(万元万元)。n已知已知 QA=5，QB=3，QC=5，n LAB=20，LBC=38n10.从节约投资的角度出发，请给出一种最优的从节约投资的角度出发，请给出一种最优的污水处理方案。污水处理方案。n20.如果联合建厂，各镇所分担的污水处理费用如果联合建厂，各镇所分担的污水处理费用将按下述原则分摊：将按下述原则分摊：n联合建厂时的建厂费用按每个镇处理的污水量联合建厂时的建厂费用按每个镇处理的污水量分担；分担；n管道的费用谁用谁

3、投资，管道的费用谁用谁投资，n联合使用时按污水量之比分担。联合使用时按污水量之比分担。n计算分析上面的分摊原则是否合理？计算分析上面的分摊原则是否合理？n30.试给出一个合理分担污水处理费用的方案。试给出一个合理分担污水处理费用的方案。n 解：解：10.污水处理费用与投资污水处理费用与投资n 一镇单建：一镇单建：PA=7350.712=230，PB=160，PC=230n 二镇合建：二镇合建：PAB=7380.712+0.6650.5120=350n PAC=463，PBC=365n 三镇合建：三镇合建：PABC=556n 投资：投资：n I.单独建厂：单独建厂：PI=PA+PB+PC=620

4、n II A、B合建：合建：PII=PAB+PC=580n III A、C合建：合建：PIII=PAC+PB=623n IV B、C合建：合建：PIV=PBC+PA=595n V 三镇合建：三镇合建：PV=PABC=556n 三镇合建总投资最少，较单独建厂节省三镇合建总投资最少，较单独建厂节省64（万元）（万元）n20.费用分担费用分担n建厂费建厂费 PABC=556，n分摊分摊 CPA=5565/13=174,CPB=105,CPC=174.n管道费管道费GFAB=0.6650.5120=30,GFBC=73.n分摊分摊 CGA=30+735/8=76,CGB=733/8=27n总合分担总合

5、分担n CA=CPA+CGA=174+76=250n CB=CPB+CGB=105+27=132n CC=CPC=174-230=20-160=-28-230=-56分摊方案中分摊方案中 A 镇吃亏镇吃亏,C镇占便宜镇占便宜,方案不公平方案不公平!nB.A、B、C 三人合作经商。三人合作经商。n单干每人可收入单干每人可收入100元元nA、B合作二人可收入合作二人可收入700元，元，nA、C合作二人收入合作二人收入500元，元，nB、C合作收入合作收入400元，三人合作可收入元，三人合作可收入1000元。元。n问三人合作时如何合理地分配问三人合作时如何合理地分配1000元的收入？元的收入？n设设

6、.三人各得三人各得 x1,x2,x3(百元百元).n则应有则应有x1+x2+x3=10,n且满足且满足 xi 1,x1+x2 7,n x1+x3 5,x2+x3 4.n可以有解可以有解 n(5,3,2),(4,3.5,2.5),n(4.5,3.5,2),(5.5,3,1.5)n哪一个更合理哪一个更合理?n 2.问题：在问题：在 n 人合作对策中如何合理地分配效益人合作对策中如何合理地分配效益值？值？n二二.模型和收益分配的模型和收益分配的 Shapley 值值n 1.假设假设:n 10.N 人从事某项活动人从事某项活动.n 20.其中若干人的每一种合作其中若干人的每一种合作(包括单人包括单人)

7、都有都有收益收益.n 30.合作是非对抗性的合作是非对抗性的(平均收益不会随合作人平均收益不会随合作人数的增加而降低数的增加而降低).n 2.建模建模:n 成员成员:I=1,2,n,n 合作合作:I 的子集的子集 S I,n 收益收益:定义在子集类定义在子集类 S 上的函数上的函数 v(S),n 满足满足v()=0,对于对于S1S2=,n 有有v(S1S2)v(S1)+v(S2)n我们称我们称 v(S)为为 I 上的特征函数上的特征函数.n 分配分配:X=x1,xn,满足满足 n 3.收益分配的收益分配的 Shapley 值值10.Shapley 公式公式其中其中|S|:S中元素的个数中元素的

8、个数 20.v(S)-v(S i):在合作组在合作组 S 中成员中成员 i 的作用的作用.n 30.i(v)是成员是成员i 在各种合作组中所做的贡献的在各种合作组中所做的贡献的加权平均加权平均,权量为权量为 w(|S|).n 令令 表示全体成员表示全体成员 I 的一个排序的一个排序,nSi 为为 的一个子集的一个子集,表示表示 中中以成员以成员 i 为排尾的为排尾的前面一部分成员的集合前面一部分成员的集合.(n-|Si|)!(|Si|-1)!则表示则表示 中令中令i排在第排在第|Si|位位,Si i 排在前面排在前面,然后然后i,然后其它成员然后其它成员 的不同的排列数的不同的排列数.nn!表

9、示全体成员表示全体成员 I 全部的排列数全部的排列数.n因此因此,w(|S|)表示在的所有排列表示在的所有排列 中中选定选定Si后后n成员成员i排于第排于第|Si|位的概率位的概率.n4.例例.三人经商三人经商n v(i)=100,i=1,2,3;v(1,2)=700,n v(1,3)=500,v(2,3)=400;v(1,2,3)=1000.n求求 1(v),2(v),3(v).n S1 (1)(1,2)(1,3)(1,2,3)n v(S)100 700 500 1000n v(S1)0 100 100 400nv(S)-v(S1)100 600 400 600n|S|1 2 2 3 n w

10、(S)1/3 1/6 1/6 1/3nwv(S)-v(S1)100/3 100 200/3 200n 1(v)=400,2(v)=350,3(v)=250n4.例例.三镇排污三镇排污n v(i)=0,i=1,2,3;n v(1,2)=40,v(1,3)=0,v(2,3)=25;v(1,2,3)=64.n求求 1(v),2(v),3(v).n S1 (1)(1,2)(1,3)(1,2,3)n v(S)0 40 0 64n v(S1)0 0 0 25nv(S)-v(S1 0 40 0 39n|S|1 2 2 3n w(S)1/3 1/6 1/6 1/3nwv(S)-v(S1)0 40/6 0 39

11、/3 n 1(v)=19.7,2(v)=32.2,3(v)=12.1nCA=230-19.7=210.3,CB=160-32.2=127.8,CC=230-12.2=217.8n三三.公平的收益分配公平的收益分配n I.对称性对称性.一个分配方案应与成员的编号无关一个分配方案应与成员的编号无关.n II.有效性有效性.对于每次合作中均无贡献者对于每次合作中均无贡献者,不应从不应从合作的效益中得到好处合作的效益中得到好处.nIII.合理性合理性.合作收益全部分光合作收益全部分光.nIV.可加性可加性.n 人同时进行两项合作时人同时进行两项合作时,每人分配每人分配的所得应是两项分配所得之和的所得应是两项分配所得之和.n四四.合作对策收益分配的合作对策收益分配的 Shapley 定理定理:n对一切特征函数对一切特征函数 v,Shapley 值是唯一满足条件值是唯一满足条件 IIV 的函数的函数.n F.S.Reberts,Discrete Mathematical Models(1976),Ch.6