Skip to content
返回搜索结果

Shapley值

提出者
Lloyd Shapley
年份
1953
类型
algorithm
类别
Game-theoretic

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

Shapley值是一个合作博弈的解概念,它根据玩家对联盟的边际贡献公平地分配总收益。Shapley值由Lloyd Shapley于1953年提出,是唯一满足四个直观公理的收益分配方式:效率(分配总收益)、对称性(相同的玩家获得相同的收益)、无用玩家(贡献为零的玩家获得零收益)和跨博弈的可加性。

方法背后的直觉

想象一群工人组成一个合资企业。Shapley值的问题是:每个工人应该赚多少?答案基于每个工人在加入不同规模团队时所做的平均边际贡献。对于工人加入的每一种可能顺序(从零到全部),计算他们各自的贡献;然后对所有可能的顺序进行平均。这使得每个工人获得的收益都能反映其不可或缺的作用,而不会偏向于时间顺序或团队规模。这是满足直观公理的唯一“公平”分配。

历史学

Lloyd Shapley于1953年提出了Shapley值,作为合作博弈中公平分配问题的唯一解。他的公理化方法被证明具有变革性,将合作博弈论确立为一个严谨的领域。Shapley值已被应用于从成本分配到功劳分配和环境监管等各种领域。Shapley对博弈论的贡献使他获得了2012年诺贝尔经济学奖,这肯定了该值的基础重要性。

何时使用

当公平分配联盟形成的联合收益时,使用Shapley值,例如在合伙企业中分配利润、在研究团队中分配功劳,或评估对集成模型的个体贡献。当玩家的贡献异质且没有市场价格揭示个体价值时使用。当寻求一种满足基本公平原则且具有公理证明的公平分配时适用。

局限与注意事项

  • 计算成本高昂:需要枚举n个玩家的全部2^n个联盟;对于大型n不可行。
  • 需要完整信息:必须预先知道所有子集的联盟价值。
  • 可能不满足个体理性:某些玩家在整个联盟中可能赚取更多。
  • 多联盟博弈中的非唯一性:当存在多个可行联盟时,确定哪个联盟形成存在歧义。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 公理唯一性:唯一满足效率、对称性、无用玩家和可加性公理的分配。
  • 公平且理论基础扎实:反映了每个玩家在联盟中的平均边际贡献。
  • 灵活性:适用于任何联盟价值明确定义的合作博弈。
  • 可分解性:可与任何估值函数一起使用,包括概率和加权版本。

应用

  • 合伙企业会计:根据合伙人不同的贡献公平分配利润。
  • 研究团队功劳:根据贡献大小在合著者之间分配致谢和功劳。
  • 成本分摊:确定如何根据不同使用模式在用户之间分摊基础设施成本。
  • 流域资源管理:公平地在下游用户之间分配共享河流的水资源。
  • 机器学习:使用SHAP(Shapley Additive exPlanations)将模型预测归因于特征贡献。

使用方式

使用方式

1

识别所有可能形成的玩家子集(联盟)。

2

计算每个联盟S的总收益v(S),即该联盟在没有外部玩家的情况下可以实现的总收益。

3

计算每个玩家i和不包含i的联盟S的边际贡献:v(S ∪ {i}) - v(S)。

4

对玩家i的边际贡献在所有玩家排序中进行平均,并按每个规模联盟的数量加权。

常见陷阱

  • 假设Shapley值导致稳定的联盟;该值定义了公平的收益分配,但不一定定义了稳定的联盟结构。
  • 通过在所有排序中简单平均来计算Shapley值;必须按联盟规模的概率加权。
  • 将Shapley值与Nash Bargaining或其他解概念混淆;每个概念都有不同的解释和属性。
  • 忘记Shapley值假设完整的特征函数;如果联盟价值不确定,则需要扩展。

常见问题

为什么Shapley值是唯一的?

因为它是在满足四个直观公理的唯一收益分配方式:(1) 效率(分配所有收益)、(2) 对称性(相同的玩家获得相同的收益)、(3) 无用玩家(零贡献玩家获得零收益)和 (4) 可加性(收益跨博弈合并)。这些公理唯一地确定了该值。

Shapley值如何处理未形成整个联盟的博弈?

Shapley值假设整个联盟形成并分配其收益v(N)。如果可能形成整个联盟之外的联盟,Shapley值不直接解决联盟结构稳定性问题;需要其他博弈论概念(核心、讨价还价)。

Shapley值可以是负数吗?

是的。如果一个玩家在联盟中的平均边际贡献为负(他们降低了总收益),那么他们的Shapley值就是负数。这种情况可能发生在存在外部性或负协同效应的博弈中。

相关方法

参考文献

  1. Shapley, L. S. (1953). A value for n-person games. In H. W. Kuhn & A. W. Tucker (Eds.), Contributions to the Theory of Games II (pp. 307-317). Princeton University Press.

    打开 DOI 文献
    已复制。
  2. Roth, A. E. (1988). The Shapley value as a von Neumann-Morgenstern utility. Econometrica, 56(4), 745-794.

    打开出版物文献
    已复制。