《合作对策的公平分配》由会员分享，可在线阅读，更多相关《合作对策的公平分配（15页珍藏版）》请在金锄头文库上搜索。
1、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. 从节约投资的角度出发，请给出一种
2、最优的污水处理方案。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合
3、建：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
4、=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、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 上的特征函
6、数.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 全
7、部的排列数 . 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
8、 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 4
9、0/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
