合作对策的公平分配

  • 格式:pdf
  • 大小:196.83 KB
  • 文档页数:15

二. 模型和收益分配的 Shapley 值 1. 假设: 10. N 人从事某项活动. 20. 其中若干人的每一种合作(包括单 人)都有收益. 30. 合作是非对抗性的(平均收益不会 随合作人数的增加而降低).
2. 建模: 成员: I = {1, 2, …, n}, 合作: I 的子集 S ⊂ I, 收益: 定义在子集类 {S} 上的函数 v(S), 满足v(Ø) = 0, 对于S1∩S2 = Ø, 有v(S1∪S2 ) ≥ v(S1)+v(S2) 我们称 v(S) 为 I 上的特征函数. 分配: X={x1, …, xn}, 满足
B. A、B、C 三人合作经商。单干每人可 收入100元, A、B合作二人可收入700元, A、C合作二人收入500元, B、C合作收入400元,三人合作可收入1000 元。 问三人合作时如何合理地分配1000元的收 入?
设. 三人各得 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 人合作对策中如何合理地 分配效益值?
§7.5 合作对策的公平分配
一. 背景与问题 1. 背景:两个实际问题: A. 沿河有三个城镇 A、B、C 依次从上游 向下游排列。城镇的污水需经处理后方可排 入河内。 三镇可以单独建厂处理污水,也可以联合建 厂,用管道送水(从上游向下游)集中处 理。 A、B 的距离为20km,B、C 的距离为 38 km。
三. 公平的收益分配 I. 对称性. 一个分配方案应与成员的编号无关. II. 有效性. 对于每次合作中均无贡献者,不应从 合作的效益中得到好处. III. 合理性. 合作收益全部分光 . IV. 可加性. n 人同时进行两项合作时, 每人分配 的所得应是两项分配所得之和 . 四. 合作对策收益分配的 Shapley 定理 : 对一切特征函数 v, Shapley 值是唯一满足条件 I~IV 的函数. F.S.Reberts, Discrete Mathematical Models (1976), Ch. 6
S中包含 {i}的子集类
(n− | S |)!(| S | −1)! w(| S |) = n!
|S|: S中元素的个数
20. [v(S)-v( S \ i )]: 在合作组 S 中成员 { i }的作用 .
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| 位的概率 .
如果用Q表示污水的流量, L表示管道的长度, 按照经验,建污水处理厂的费用为 CF = 73Q0.712 (万元), 铺设管道的费用为GF= 0.66Q0.51L (万元)。 已知 QA=5,QB=3,QC=5, LAB=20,LBC=38
10. 从节约投资的角度出发,请给出一种 最优的污水处理方案。 20. 如果联合建厂,各镇所分担的污水处 理费用将按下述原则分摊: 联合建厂时的建厂费用按每个镇处理的 污水量分担; 管道的费用谁用谁投资, 联合使用时按污水量之比分担。 计算分析上面的分摊原则是否合理? 30. 试给出一个合理分担污水处理费用的 方案。
20. 费用分担 建厂费 PABC=556, 分摊 CPA=556×5/13=174, CPB=105, CPC=174. 管道费GFAB=0.66×50.51×20=30, GFBC=73. 分摊 CGA=30+73×5/8=76, CGB=73×3/8=27 总合分担 CA=CPA+CGA=174+76=250 -230= 20 CB=CPB+CGB=105+27=132 -160= -28 CC=CPC=174 -230= -56 分摊方案中 A 镇吃亏, C镇占便宜, 方案不公平!
解:10. 污水处理费用与投资 一镇单建:PA=73×50.712=230,PB=160,PC=230 二镇合建:PAB= 73×80.712+0.66×50.51×20=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(万 元)
合作对策
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(S\{1}) 0 100 100 400 v(S)-v(S\{1}) 100 600 400 600 |S| 1 2 2 3 w(S) 1/3 1/6 1/6 1/3 w[v(S)-v(S\{1})] 100/3 100 200/3 200 φ1(v)=400, φ2(v)=350, φ3(v)=250
Байду номын сангаас
∑ x = v(I ) ,
i =1 i
n
xi ≥ v(i) ,
∑ x ≥ v(S )
i∈S i
3. 收益分配的 Shapley 值 10. Shapley 公式
S∈Si

w (| S |)[ v ( S ) − v ( S \ i )] ,
i = 1,
,n
其中
S i = {S | i ∈ S } ,
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(S\{1}) 0 0 0 25 v(S)-v(S\{1} 0 40 0 39 |S| 1 2 2 3 w(S) 1/3 1/6 1/6 1/3 w[v(S)-v(S\{1})] 0 40/6 0 39/3 φ1(v)=19.7, φ2(v)=32.2, φ3(v)=12.1 CA=230-19.7=210.3, CB=160-32.2=127.8, CC=230-12.2=217.8