合作对策的应用 例2 派别在团体中的权重
90人的团体由 个派别组成，人数分别为 人的团体由3个派别组成 人数分别为40, 30, 20人。 人的团体由 个派别组成， 人 团体表决时需过半数的赞成票方可通过。 团体表决时需过半数的赞成票方可通过。 若每个派别的成员同时投赞成票或反对票， 若每个派别的成员同时投赞成票或反对票，用Shapley 合作对策计算各派别在团体中的权重。 计算各派别在团体中的权重 合作对策计算各派别在团体中的权重。
3
Q3=5
• 污水处理，排入河流 污水处理， •三城镇可单独建处理厂， 三城镇可单独建处理厂， 三城镇可单独建处理厂 或联合建厂(用管道将污水 或联合建厂 用管道将污水 由上游城镇送往下游城镇) 由上游城镇送往下游城镇
Q~污水量，L~管道长度 污水量， 管道长度 污水量 建厂费用P 建厂费用 1=73Q0.712 管道费用P 管道费用 2=0.66Q0.51L
v(i) = 0 (i = 1,2,Ln), v( I ) = ∑ yi − Y , v ( I \ i ) = ∑ y j − z i
i =1
n
j ≠i
其它v(s)均不知道 无法用 均不知道, 无法用Shapley合作对策求解 合作对策求解 其它 均不知道 合作对策
求解合作对策的其他方法
参加时n-1方合作的获利 设只知道 bi = v ( I \ i ) ~ 无 i 参加时 方合作的获利
特征函数v(s)~联合 集s)建厂比单独建厂节约的投资 联合(集 建厂比单独建厂节约的投资 特征函数 联合
v (1) = v ( 2 ) = v ( 3 ) = 0
v(1 U 2) = C (1) + C(2) − C(1,2) = 230 + 160 − 350 = 40
v(2 U 3) = C(2) + C(3) − C(2,3) = 160+ 230− 365 = 25 v(1U 3) = 0 v(I ) = C(1) + C(2) + C(3) − C(1,2,3) = 230+160+ 230− 556 = 64
v(s)
v ( s \ 1)
v ( s ) − v ( s \ 1) s
w( s )
w ( s )[ v ( s ) − v ( s \ 1)]
x1=13/3
类似可得 x2=23/6, x3=17/6
合作对策的应用 例1 污水处理费用的合理分担
三城镇地理位置示意图
20km 38km
1
Q1=5 2
Q2=3 河流
x = ( x 1 , x 2 , x 3 ) ~三城从节约投资 中得到的分配 节约投资v(I)中得到的分配 三城从节约投资
计算城 从节约投资中得到的分配x 计算城1从节约投资中得到的分配 1
s
v (s )
v (s \ 1) v ( s ) − v ( s \ 1)
1 0 0 0 1 1/3 0
1
1 xi = ∑ bi − bi ~ xi 的下限 求解 A x = b n −1 例. b = ( 4,5,7 ), B = 11 将剩余获利 B − ∑ x i 平均分配
1 1 B xi = xi + (B − ∑xi ) = ∑bi − bi + n n n
x = (4,3,1), B − ∑xi = 3,
三人(I={1,2,3})经商中甲的分配 1的计算 经商中甲的分配x 三人 经商中甲的分配 x1 = ∑ w ( s )[ v ( s ) − v ( s \ 1)]
s∈ S 1
S1
1 1 0 1 1 1/3 1/3
1 U 2 7 1 6 2 1/6 1
1U3 5 1 4 2 1/6 2/3
I 11 4 7 3 1/3 7/3
x = x + (1,1,1) = (5,4,2)
（3）Nash解 ） 解
记 d = (d1 ,L, dn ) 为现状点（谈判时的威慑点） 为现状点（谈判时的威慑点）
在此基础上“均匀地”分配全体合作的获利 在此基础上“均匀地”分配全体合作的获利B 模 型
max∏ ( xi − d i )
i
s.t. ∑ xi = B xi ≥ d i
团体 I={1,2,3}，依次代表 个派别 ，依次代表3个派别 1, s的成员超过 45 定义特征函数 定义特征函数 v ( s ) = 0， 否则 v (φ ) = 0, v (1) = v ( 2) = v (3) = 0,
v (1 U 2) = v (1 U 3) = v ( 2 U 3) = v ( I ) = 1
权重 x1 = x 2 = x3 = 1 / 3
虽然3派人数相差很大 虽然 派人数相差很大
Shapley合作对策小结 合作对策小结
优点：公正、合理，有公理化基础。 优点：公正、合理，有公理化基础。 缺点：需要知道所有合作的获利，即要定义 缺点：需要知道所有合作的获利，即要定义I={1,2,…n}的所有 的所有 子集(共 的特征函数， 子集 共2n-1个)的特征函数，实际上常做不到。 个 的特征函数 实际上常做不到。 个单位治理污染, 方单独治理的投资y 如n个单位治理污染 通常知道第 方单独治理的投资 i 和n方共 个单位治理污染 通常知道第i方单独治理的投资 方共 同治理的投资Y, 及第i方不参加时其余 方的投资z 方不参加时其余n-1方的投资 同治理的投资 及第 方不参加时其余 方的投资 i (i=1,2, …n). 确定共同治理时各方分担的费用。 确定共同治理时各方分担的费用。 若定义特征函数为合作的获利(节约的投资 ， 若定义特征函数为合作的获利 节约的投资)，则有 节约的投资
0.712 0.51
D5
{
1→2管道费：d2=0.66 ×50.51 ×20=30 → 管道费 管道费： 2→3管道费：d3=0.66 ×(5+3)0.51 ×38=73 → 管道费 管道费：
C(3) = 230
建议： 分担, 由城1,2担负 城3建议：d1 按 5:3:5分担 d2,d3由城 担负 建议 分担 建议： 由城1,2按 分担, 城2建议：d3由城 按 5:3分担 d2由城 担负 建议 分担 由城1担负
( n − s )! ( s − 1)! w( s ) = n!
中的元素数目， 包含i的所有子集 s~子集 s中的元素数目， Si ~包含 的所有子集 子集 中的元素数目 包含
[v ( s ) − v ( s \ i )] ~ i 对合作 的“贡献” ( i ∈ s ) 对合作s 贡献”
由 决定的“贡献” w ( s ) ~由s决定的“贡献”的权重
平均分配获利B 平均分配获利
1 xi = d i + ( B − ∑ d i ) n
di = 0
di = xi
3）Nash解 ⇒ 2）协商解 ） 解 ）
（4）最小距离解 ）
模 型
记 x = ( x1 ,L, xn )为x的上限
min ∑ ( xi − xi ) 2
i
s.t.
若令
∑x = B
i
1 xi = xi − (∑ xi − B ) n
U
40 0 40 2 1/6 6.7
2
1
U
0 0 0 2 1/6 0
3
I 64 25 39 3 1/3 13
s
w( s )
w( s )[ v ( s ) − v ( s \ 1)]
x1 =19.7, x2 =32.1, x3=12.2 最大，如何解释？ x2最大，如何解释？ 三城在总投资556中的分担 三城在总投资 中的分担 城1 C(1)-x1=210.4, 城2 C(2)-x2=127.8, 城3 C(3)-x3=217.8
污水处理的5 污水处理的 种方案 1）单独建厂 C (1) = 73 ⋅ 5 0.712 = 230, C ( 2) = 160, C (3) = 230 ） 总投资 D1 = C (1) + C ( 2) + C (3) = 620 2）1, 2合作 ） 合作
总投资
C (1, 2 ) = 73 ⋅ (5 + 3) 0.712 + 0 .66 ⋅ 5 0.51 ⋅ 20 = 350
即已知 B = 11，b = ( 4,5,7 ), 求 x = ( x1 , x2 , x3 )
（2）协商解 ）
模 型
i
以n-1方合作的获利为下限 方合作的获利为下限
∑x = B ∑ x − x ≥ b
i 1
M ∑ x − x ≥ b i n n
T T
1
0 1 ⇒ AxT ≥ bT , A = O 1 0
记甲乙丙三人分配为 x = ( x1 , x2 , x3 )
x1 + x2 + x3 = 11
x1 + x 2 ≥ 7 x1 + x 3 ≥ 5 x 2 + x3 ≥ 4
解不唯一 (5，3，3) ， ， (4，4，3) ， ， (5，4，2) ， ， ……
x1 , x 2 , x 3 ≥ 1
(1) Shapley合作对策 合作对策
x = ( x1 , x 2 , L , x n ) ~n人从 得到的分配，满足 人从v(I)得到的分配 得到的分配， 人从
∑ x = v( I )
i =1 i
n
x i ≥ v ( i ),
i = 1, 2 , L , n
Shapley合作对策 合作对策
公理化方法
s∈S i
Shapley值 值
xi = ∑ w( s )[v( s ) − v( s \ i )], i = 1,2,L n
xi ≤ xi
x i = B − bi