Math——博弈论-Shapley-Value

整体说明

  • Shapley Value（沙普利值） 是合作博弈论中的一个核心概念，由诺贝尔经济学奖得主 Lloyd Shapley 于 1953 年提出
  • Shapley Value 用于解决一个基本问题：在一个多人合作博弈中，如何公平地分配所有合作者共同创造的总收益？
  • Shapley Value 给出了一种按照每个参与者的“边际贡献”来分配总收益的数学方法

Shapley Value 核心思想

  • Shapley Value 分配的唯一标准是：每个参与者获得的收益，应该等于他在所有可能的加入顺序下，对联盟平均边际贡献的期望值

Shapley Value 数学定义

  • 场景设定：
    • 参与者集合为 \(N = \{1, 2, \dots, n\}\)
    • 特征函数 \(v(S)\)：表示任意子集 \(S \subseteq N\) 合作所能创造的总价值（满足 \(v(\emptyset) = 0\)）
  • 参与者 \(i\) 的 Shapley Value \(\phi_i(v)\) 定义为：
    $$
    \phi_i(v) = \frac{1}{n!} \sum_{\pi \in \Pi_n} \left[ v(S_{\pi,i} \cup \{i\}) - v(S_{\pi,i}) \right]
    $$
  • 其中：
    • \(\Pi_n\) 是所有 \(n!\) 种排列（加入顺序）的集合
    • \(S_{\pi,i}\) 是在排列 \(\pi\) 中出现在参与者 \(i\) 之前的所有参与者集合
    • 方括号内就是参与者 \(i\) 加入当前联盟 \(S_{\pi,i}\) 时带来的边际贡献

Shapley Value 直观理解

  • 假设有三个朋友 A、B、C 一起做项目，总共赚了 100 元，他们想知道：每个人应该分多少才公平 ？
  • Shapley Value 的思路是：
    • 1）考虑所有可能的加入顺序（3! = 6 种）
    • 2）在每种顺序下，计算每个人“刚好加入时”带来的价值增量
    • 3）把每个人在所有顺序下的边际贡献求平均
  • 例如：
    加入顺序 A 的边际贡献 B 的边际贡献 C 的边际贡献
    A → B → C v(A) v(AB) - v(A) v(ABC) - v(AB)
    A → C → B v(A) v(ABC) - v(AC) v(AC) - v(A)
    … … … …
  • 最终：
    $$
    \phi_A = \frac{\text{A 在 6 种顺序下的边际贡献之和} }{6}
    $$

更细节的示例

  • 假设一个简单的投票博弈：
    • 参与者：A、B、C
    • 总收益：1 元
    • 获胜规则：多数票（至少 2 票）
  • 特征函数：
    • \(v(\{A,B\}) = 1\)
    • \(v(\{A,C\}) = 1\)
    • \(v(\{B,C\}) = 1\)
    • \(v(\{A,B,C\}) = 1\)
    • 其余子集为 0
  • 计算 A 的 Shapley Value：
    • 考虑 6 种顺序：
      • A 先来：边际贡献 = 0（A 一个人无法获胜）
      • A 在 B 之后加入（B → A）：此时已有 B（0 票），A 加入后达到 2 票 → 边际贡献 = 1
      • A 在 C 之后加入 → 边际贡献 = 1
      • A 在 B、C 之后加入 → 边际贡献 = 0（已经赢了）
  • 平均后：\(\phi_A = \frac{1}{3}\)
  • 同理：
    • \(\phi_B = \frac{1}{3}\)
    • \(\phi_C = \frac{1}{3}\)
  • 结果：三个人平分收益，符合多数投票博弈的对称性直觉

Shapley Vlaue 满足四大公理（唯一性保证）

  • Shapley Value 是唯一同时满足以下四条公理的分配方式：
    • 效率性（Efficiency / 帕累托最优） ：所有参与者的 Shapley Value 之和等于总收益：
      $$ \sum_{i=1}^n \phi_i(v) = v(N) $$
      • 合作产生的总收益必须被全部分配完，既没有剩余，也没有透支，即所有人的沙普利值之和等于团队总收益
    • 对称性（Symmetry） ： 如果两个参与者对任何联盟的贡献相同，则他们获得相同的收益
    • 线性性（Additivity） ： 若游戏可分解为两个独立子游戏的求和，则 Shapley Value 也相应求和
    • 哑元性（Dummy Player / 零贡献者） ： 如果一个参与者对所有联盟的边际贡献均为 0，则其收益为 0
  • 这些公理使得 Shapley Value 成为一种公平、无偏、可解释 的信用分配方式

Shapley Value 的其他定义形式

  • Shapley Value 是一种公平分配合作总收益的方法：每个人得到的等于他在所有可能加入顺序下的平均边际贡献
  • 假设有一群人要组成一个团队，每个人是一个接一个加入的
    • 当一个人加入团队时，团队的总收益会因为他的加入而增加，这个增加的量就是他的“边际贡献”
    • 参与者加入团队的先后顺序会影响他的边际贡献
    • 沙普利值的做法是：考虑所有可能的加入顺序，计算该参与者在每种顺序下的边际贡献，然后求平均值

Shapley Value 数学公式

  • 沙普利值的计算公式如下：
    $$ \phi_i(v) = \sum_{S \subseteq N \setminus \{i\} } \frac{|S|! (n - |S| - 1)!}{n!} (v(S \cup \{i\}) - v(S)) $$
    • \(N\)：所有参与者的集合
    • \(n\)：参与者的总人数
    • \(S\)：不包含参与者 \(i\) 的某个子联盟
    • \(|S|\)：子联盟 \(S\) 中的人数
    • \(v(S)\)：子联盟 \(S\) 能创造的收益
    • \(v(S \cup \{i\}) - v(S)\)：参与者 \(i\) 加入联盟 \(S\) 后带来的边际贡献
    • \(\frac{|S|! (n - |S| - 1)!}{n!}\)：这是一个权重，代表在所有可能的排列顺序中，刚好形成联盟 \(S\) 并且 \(i\) 紧接着加入的概率