合作对策的公平分配.ppt
7.5 合作对策的公平分配n一.背景与问题n 1.背景：两个实际问题：n A.沿河有三个城镇 A、B、C 依次从上游向下游排列。城镇的污水需经处理后方可排入河内。n三镇可以单独建厂处理污水，也可以联合建厂，用管道送水（从上游向下游）集中处理。nA、B 的距离为20km，B、C 的距离为 38 km。n n如果用Q表示污水的流量，nL表示管道的长度，n按照经验，建污水处理厂的费用为 nCF=73Q0.712(万元),n铺设管道的费用为GF=0.66Q0.51L(万元)。n已知 QA=5，QB=3，QC=5，n LAB=20，LBC=38n10.从节约投资的角度出发，请给出一种最优的污水处理方案。n20.如果联合建厂，各镇所分担的污水处理费用将按下述原则分摊：n联合建厂时的建厂费用按每个镇处理的污水量分担；n管道的费用谁用谁投资，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=620n 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总合分担n CA=CPA+CGA=174+76=250n CB=CPB+CGB=105+27=132n CC=CPC=174-230=20-160=-28-230=-56分摊方案中 A 镇吃亏,C镇占便宜,方案不公平!n B.A、B、C 三人合作经商。单干每人可收入100元，nA、B合作二人可收入700元，nA、C合作二人收入500元，nB、C合作收入400元，三人合作可收入1000元。n问三人合作时如何合理地分配1000元的收入？n n设.三人各得 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.其中若干人的每一种合作(包括单人)都有收益.n 30.合作是非对抗性的(平均收益不会随合作人数的增加而降低).n 2.建模:n 成员:I=1,2,n,n 合作:I 的子集 S I,n 收益:定义在子集类 S 上的函数 v(S),满足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中元素的个数 20.v(S)-v(S i):在合作组 S 中成员 i 的作用.n 30.i(v)是成员i 在各种合作组中所做的贡献的加权平均,权量为 w(|S|).n 令 表示全体成员 I 的一个排序,nSi 为 的一个子集,表示 中以成员 i 为排尾的前面一部分成员的集合.n (n-|Si|)!(|Si|-1)!则表示 中令i排在第|Si|位,Si i 排在前面,然后i,然后其它成员的不同的排列数.nn!表示全体成员 I 全部的排列数.n 因此,w(|S|)表示在的所有排列 中选定Si后成员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(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/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
