合作对策的公平分配

1、合作对策的公平分配第1页，共15页，2022年，5月20日，7点39分，星期二一. 背景与问题 1. 背景：两个实际问题： A. 沿河有三个城镇 A、B、C 依次从上游向下游排列。城镇的污水需经处理后方可排入河内。三镇可以单独建厂处理污水，也可以联合建厂，用管道送水（从上游向下游）集中处理。A、B 的距离为20km，B、C 的距离为 38 km。 第2页，共15页，2022年，5月20日，7点39分，星期二如果用Q表示污水的流量，L表示管道的长度，按照经验，建污水处理厂的费用为 CF = 73Q0.712 (万元), 铺设管道的费用为GF= 0.66Q0.51L (万元)。已知 QA=5，QB

2、=3，QC=5， LAB=20，LBC=38第3页，共15页，2022年，5月20日，7点39分，星期二10. 从节约投资的角度出发，请给出一种最优的污水处理方案。20. 如果联合建厂，各镇所分担的污水处理费用将按下述原则分摊：联合建厂时的建厂费用按每个镇处理的污水量分担；管道的费用谁用谁投资，联合使用时按污水量之比分担。计算分析上面的分摊原则是否合理？30. 试给出一个合理分担污水处理费用的方案。第4页，共15页，2022年，5月20日，7点39分，星期二 解：10. 污水处理费用与投资 一镇单建：PA=7350.712=230，PB=160，PC=230 二镇合建：PAB= 7380.71

3、2+0.6650.5120=350 PAC = 463，PBC = 365 三镇合建：PABC=556 投资： I. 单独建厂： PI=PA+PB+PC=620 II A、B合建：PII=PAB+PC=580 III A、C合建：PIII=PAC+PB=623 IV B、C合建：PIV=PBC+PA=595 V 三镇合建： PV=PABC=556 三镇合建总投资最少，较单独建厂节省64（万元）第5页，共15页，2022年，5月20日，7点39分，星期二20. 费用分担建厂费 PABC=556，分摊 CPA=5565/13=174, CPB=105, CPC=174.管道费GFAB=0.6650

4、.5120=30, GFBC=73.分摊 CGA=30+735/8=76, CGB=733/8=27总合分担 CA=CPA+CGA=174+76=250 CB=CPB+CGB=105+27=132 CC=CPC=174-230= 20-160= -28-230= -56分摊方案中 A 镇吃亏, C镇占便宜, 方案不公平! 第6页，共15页，2022年，5月20日，7点39分，星期二 B. A、B、C 三人合作经商。单干每人可收入100元，A、B合作二人可收入700元，A、C合作二人收入500元，B、C合作收入400元，三人合作可收入1000元。问三人合作时如何合理地分配1000元的收入？ 第7

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

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

7、v(S)-v( S i ): 在合作组 S 中成员 i 的作用 .第11页，共15页，2022年，5月20日，7点39分，星期二 30. i(v) 是成员i 在各种合作组中所做的贡献的加权平均, 权量为 w(|S|) . 令 表示全体成员 I 的一个排序, Si 为 的一个子集, 表示 中以成员 i 为排尾的前面一部分成员的集合. (n-|Si|)!(|Si|-1)! 则表示 中令i排在第 |Si| 位, Si i 排在前面, 然后i, 然后其它成员的不同的排列数. n! 表示全体成员 I 全部的排列数 . 因此, w(|S|) 表示在的所有排列 中选定Si后成员i排与第 |Si| 位的概率

8、.第12页，共15页，2022年，5月20日，7点39分，星期二合作对策4. 例 . 三人经商 v( i )=100, i=1,2,3; v(1,2)=700, v(1,3)=500, v(2,3)=400; v(1,2,3)=1000 . 求 1(v), 2(v), 3(v) . S1 (1) (1,2) (1,3) (1,2,3) v(S) 100 700 500 1000 v(S1) 0 100 100 400v(S)-v(S1) 100 600 400 600 |S| 1 2 2 3 w(S) 1/3 1/6 1/6 1/3wv(S)-v(S1) 100/3 100 200/3 200

9、 1(v)=400, 2(v)=350, 3(v)=250第13页，共15页，2022年，5月20日，7点39分，星期二4. 例 . 三镇排污 v( i )=0, i=1,2,3; v(1,2)=40, v(1,3)=0, v(2,3)=25; v(1,2,3)=64 . 求 1(v), 2(v), 3(v) . S1 (1) (1,2) (1,3) (1,2,3) v(S) 0 40 0 64 v(S1) 0 0 0 25v(S)-v(S1 0 40 0 39 |S| 1 2 2 3 w(S) 1/3 1/6 1/6 1/3wv(S)-v(S1) 0 40/6 0 39/3 1(v)=19.7, 2(v)=32.2, 3(v)=12.1CA=230-19.7=210.3, CB=160-32.2=127.8, CC=230-12.2=217.8第14页，共15页，2022年，5月20日，7点39分，星期二三. 公平的收益分配 I. 对称性. 一个分配方案应与成员的编号无关. II. 有效性. 对于每次合作中均无贡献者,不应从合作的效益中得到好处. III. 合理性. 合作收益全部分光 .IV. 可加性. n 人同时进行两项合作时, 每人分配的所得应是两项分配