某项工作,A 单干时获利为 1, B 单干时获利为 2, C 单干时获利为 1, AB 联盟作为个体单干时获利为 10, AC 联盟作为个体单干时获利为 30,BC 联盟作为个体单干时获利为 40,三人合作获利为 100. 问题:怎样将总获利 100 分配给这三人才合理?
v(a)=1,v(b)=2,v(c)=1,v(ab)=10,v(ac)=30,v(bc)=40,v(abc)=100
公平分配收益问题可以用沙普利值来解决。在这个问题中需要计算每一个人的边际贡献,对于n个人的合作博弈问题,利用沙普利值的计算公式$$\phi_i(v)=\frac{1}{n!}\sum_{S\subseteq N\backslash{i}}\binom{n-1-|S|}{|S|}(v(S\cup{i})-v(S))$$ 其中,$v$ 是该问题的特征函数,$v(S)$ 表示联合决策 $S$ 时的获利,$|S|$ 表示联合决策 $S$ 中的人数,$N$ 是所有参与者的集合,$i\in N$ 表示要计算 Shapley value 的人,$\phi_i(v)$ 表示第 $i$ 个人的 Shapley value。 根据这个公式,我们可以得到下面的计算过程:
对于每个人,计算他在所有可能的联合决策中的边际贡献。具体来说,对于每个人 $i$,我们可以列出包含他和其他人的所有可能的联合决策(一共有 $2^n-1$ 种),然后计算出在每种联合决策中,他对于最终获利的贡献。例如,对于 A,可能的联合决策有 {A}、{AB}、{AC}、{ABC},对于 {A} 这种情况,A 的贡献为 1,对于 {AB} 这种情况,A 的贡献为 9(因为 AB 联盟单干时的获利为 10,减去 B 单干时的获利为 2),对于 {ABC} 这种情况,A 的贡献为 60(因为 ABC 三人合作时的获利为 100,减去 BC 联盟单干时的获利为 40,减去 AC 联盟单干时的获利为 30,减去 A 单干时的获利为 1,剩下的就是 A 的贡献)。
对于每个人,将他的边际贡献加权平均,得到他的 Shapley value。具体来说,对于每个人 $i$,我们可以根据上一步计算出的所有边际贡献,按照参与联合决策的人数进行加权平均。例如,对于 A,他参与的联合决策的人数分别为 1、2、3,对应的边际贡献分别为 1、9、60,加权平均后的 Shapley value 为 $(1+9/2+60/6)/3=5$。 根据这个方法,我们可以计算出每个人的 Shapley value:
A 的 Shapley value 为 5。B 的 Shapley value 为 33。C 的 Shapley value 为 22。 这个结果的意义是:如果三个人按照 Shapley value 分配收益,A 应该获得 5/60 的收益,B 应该获得 33/60 的收益,C 应该获得 22/60 的收益。这个分配方案满足 Shapley value 的公平性质,即每个人对于最终收益的贡献与他们参与的贡献成正比。