23 · Shapley 值

⏱ 42 分钟 ｜ ⭐⭐ 你可能早就在用它了，只是不知道它是这么来的

🎯 一句话

Shapley 值 = 假设大家随机排队进场，每个人平均带来多少增量。

上一章的 nucleolus 站在稳定那一边（谁也别想掀桌）；Shapley 值站在公平那一边（干多少拿多少）。同一份数据，两个都「对」的答案。

🎲 一、公平怎么量：先想清楚「一个人值多少」

手套博弈里 nucleolus 把 1 全给右手套的人，2、3 号一分不拿。那怎么才算「按贡献分」？

第一个想法：看 $i$ 加进来时多带来多少 —— $v(S\cup\{i\}) - v(S)$，叫 $i$ 对 $S$ 的边际贡献。

⚠️ 但这个数取决于 $S$ 是谁：糖对「已经有面粉的团队」和对「空团队」价值完全不同。单一个边际贡献不能当答案。

⭐ Shapley 的答案：所有加入顺序一视同仁，取平均。 想象 n 个人随机排队依次进场，每人进场时结算他当场带来的增量。 你的报酬 = 你在所有 $n!$ 种排队顺序下增量的平均值。

📐 二、定义

记 $\Pi_N$ 为 $N$ 的全部排列。对排列 $\pi$，令 $S_\pi(i)$ = 排在 $i$ 前面的那些人，则 $i$ 在 $\pi$ 中的边际贡献是 $\Delta_\pi(i) = v(S_\pi(i)\cup\{i\}) - v(S_\pi(i))$。

$$\phi_i \;=\; \frac{1}{n!}\sum_{\pi\in\Pi_N} \Delta_\pi(i)$$

等价的按联盟写法（把贡献相同的排列合并同类项）：

$$\phi_i \;=\; \frac{1}{n!}\sum_{S\subseteq N\setminus\{i\}} |S|!\,(n-|S|-1)!\,\bigl(v(S\cup\{i\})-v(S)\bigr)$$

💡 那两个阶乘就是「有多少种排列会让 $i$ 恰好接在 $S$ 后面」：$S$ 内部随便排（$|S|!$ 种），$i$ 之后的人随便排（$(n-|S|-1)!$ 种）。两种写法是同一件事，手算时用排列版，写程序时用联盟版。

🔨 三、n=3 完整手算（这一节请拿纸跟着做）

Alice 带面粉值 $2，Bob 带糖值 $1，Charles 带草莓值 $3。两两合作：AB 做普通煎饼 $5，AC 做草莓煎饼 $7，BC 卖糖和草莓 $4。三人一起做爆款 $16。

套路：列出 6 个排列，每个排列从左到右依次结算增量。

$$\phi_A=\tfrac{2+2+4+12+4+12}{6}=6,\quad \phi_B=\tfrac{3+9+1+1+9+1}{6}=4,\quad \phi_C=\tfrac{11+5+11+3+3+3}{6}=6$$

⭐ 两个必做的自查： ① 三人加起来 $6+4+6=16=v(N)$ ✓ ② 每一行加起来也是 16（$2+3+11$、$2+9+5$、…）—— 因为一行就是望远镜求和 $v(\{a_1\})+[v(\{a_1,a_2\})-v(\{a_1\})]+\dots=v(N)$。

💡 第 ② 条就是效率的完整证明：每行和都是 $v(N)$，$n!$ 行平均下来当然还是 $v(N)$。算错一个数，行和立刻对不上 —— 这是手算最好用的检错手段。

⚖️ 四、四条公理，唯一确定它

⭐ 定理（Shapley 1953）：同时满足这四条的分配方式有且只有 Shapley 值。 它不是「一种合理的分法」，是唯一一种。这是它能被到处引用的根本原因。

另一个刻画（Young 1985）把可加性换成边际性 —— 「只要 $i$ 在两个博弈里的所有边际贡献都相同，他拿的就该相同」—— 效率 + 对称 + 边际性同样唯一确定 Shapley 值。

⚠️ 可加性看着像技术条件，其实是最有争议的一条：它要求「两个项目并做一个项目」时分配不变，而现实里合并往往产生协同效应。知道公理在哪，就知道结论在哪失效。

🧤 五、公平 ≠ 稳定：回到手套博弈

简单博弈里 Shapley 值有个更快的算法：

$$\phi_i = \frac{i\ \text{的边际贡献为 1 的排列数}}{n!}$$

手套博弈（1 号右手套，2、3 号各一只左手套）的 6 个排列，谁把局面从「输」变成「赢」：

$$\phi_1=\tfrac46,\quad \phi_2=\phi_3=\tfrac16$$

⚠️⚠️ Shapley 值不保证落在核心里。 给 2 号 1/6，1 号和 3 号立刻会甩开他重新配对（他们俩合计只拿到 $\tfrac46+\tfrac16=\tfrac56 < 1$）。

⭐ 这就是这两章最该带走的一句话：「按贡献分」和「没人想掀桌」是两个不同的目标，它们经常给出不同答案。 选哪个取决于你怕的是什么 —— 怕不公平，还是怕散伙。

📈 六、凸博弈：两者和解的那一类

定义：$(N,v)$ 是凸的，如果对所有 $S,T$ 有 $v(S\cup T)+v(S\cap T)\ge v(S)+v(T)$。等价地：

$$B\subseteq A\subseteq N\setminus\{i\}\ \Longrightarrow\ v(A\cup\{i\})-v(A)\ \ge\ v(B\cup\{i\})-v(B)$$

人话：⭐ 联盟越大，同一个人加进来的边际贡献越大（规模报酬递增，滚雪球）。

两条结论：

• 凸博弈的核心非空（Shapley 1971）。构造性证明：按任意排列依次结算边际贡献得到的向量 $x$，本身就在核心里。
• 于是 ⭐ 每个排列的边际贡献向量都在核心里，而 Shapley 值是它们的平均；核心是凸集，所以 Shapley 值也在核心里。

💡 凸博弈是「公平和稳定不打架」的那一类。 手套博弈不凸 —— 2 号在 $\{1\}$ 后面加入贡献 1，在 $\{1,3\}$ 后面加入贡献 0，边际贡献变小了，正好反着。

🗳️ 七、Banzhaf 指数：另一把尺子

简单博弈里还有一个常用的权力度量。

• $i$ 在联盟 $C$ 中是关键的，如果 $v(C)=1$ 但 $v(C\setminus\{i\})=0$
• Banzhaf 值 $\eta_i$ = $i$ 是关键的联盟个数；Banzhaf 指数 $\beta_i = \eta_i / \sum_{j} \eta_j$

手套博弈的获胜联盟只有 $\{1,2\},\{1,3\},\{1,2,3\}$。前两个里两人都关键；$\{1,2,3\}$ 里只有 1 号关键（去掉 2 还剩 $\{1,3\}$ 仍赢）。于是 $\eta=(3,1,1)$，$\beta=(\tfrac35,\tfrac15,\tfrac15)$。

⚠️ Banzhaf 和 Shapley 的关键差别：Shapley 除以 $n!$（按排列平均），满足效率，是一个分配方案；Banzhaf 除以关键计数总和，不满足效率，只是一个相对权力指数。要分钱用 Shapley，要比较投票权大小两个都常见。

🗜️ 八、怎么把 v 写短，怎么算得动

上一章说过 $v$ 有 $2^n$ 个数。两种常见的简洁表示：

① 图博弈：给一张带权无向图，$v(S)$ = $S$ 导出子图的边权之和（比如「合作两两产生价值」）。

$$\phi_i=\tfrac12\sum_{j\ne i} w(\{i,j\})\qquad \text{⭐ 每条边的价值，两个端点一人一半}$$

多项式时间（Deng & Papadimitriou 1994）—— 但 ⚠️ 判断核心是否非空是 NP-完全的，「算 Shapley 容易、判核心难」在这里第一次出现。图博弈不是完全表达的（有些 $v$ 写不出来）。

② MC-nets（边际贡献网络）：把 $v$ 写成一组规则 模式 → 值，模式是成员的合取（允许否定），$v(S)$ = 所有适用规则的值之和（Ieong & Shoham 2005）。

例：$x_1\wedge x_2\to 5$、$x_2\to 2$、$x_3\to 4$、$x_2\wedge\neg x_3\to -2$。那么 $v(\{2\})=2-2=0$，$v(\{2,3\})=2+4=6$，$v(\{1,2\})=5+2-2=5$，$v(N)=5+2+4=11$。

⭐ MC-nets 是完全表达的（每个联盟单独写一条规则即可），而且 —— 由 Shapley 值的可加性，只要逐条规则算 Shapley 再相加就行，线性时间。 第四节那条「看着像技术条件」的公理，在这里换成了算法。

⚠️ 两列没有一行是同时容易的，而且难易顺序还会对调。别默认「概念简单 ⟹ 算得动」。

🤖 九、⭐⭐ 你可能早就在用 Shapley 值了

把「成员」换成「特征」，把「合作赚的钱」换成「模型的预测值」，Shapley 值就变成了 SHAP —— 目前工业界最主流的模型解释工具。

$$\text{预测值} = \underbrace{\phi_0}_{\text{基准}} + \sum_i \phi_i$$

那条「严格加起来等于预测值」的性质，就是第四节的效率公理；「对所有加入顺序取平均」也一字不差地搬了过来，原因还是同一个：特征之间有交互，取平均是为了公平分摊交互那部分。

而「$n!$ 个排列」的指数复杂度在工程上后果很具体：精确算不动，所以要么近似（KernelSHAP，慢到线上用不了），要么利用结构 —— TreeSHAP 靠树的结构在多项式时间内精确算出 Shapley 值。这正是第八节「表示法决定复杂度」的又一个实例，也是 SHAP 在大量用 GBDT 的工业界流行的直接原因。

🔗 这一章连到哪里

✅ 检查点

1. Shapley 值的一句话直觉是什么？为什么不能只取某一个联盟的边际贡献？
2. $\phi_i$ 的排列版和联盟版公式各写一遍。联盟版里那两个阶乘是从哪来的？
3. 煎饼博弈（$v$：A=2, B=1, C=3, AB=5, AC=7, BC=4, ABC=16）的 Shapley 值是多少？手算时有哪两个自查？
4. 唯一确定 Shapley 值的四条公理是什么？哪一条最有争议，为什么？
5. 手套博弈的 Shapley 值是多少？它在核心里吗？这说明了什么？
6. 凸博弈怎么定义（用边际贡献的说法）？为什么它的 Shapley 值一定在核心里？
7. Banzhaf 指数怎么算？手套博弈的 $\beta$ 是多少？它和 Shapley 最关键的差别是哪一条？
8. 图博弈的 Shapley 值公式是什么？MC-nets 为什么能线性时间算 Shapley？
9. SHAP 里的「可加性」对应这一章的哪条公理？为什么 SHAP 必须「对所有顺序取平均」？

🛑 可以停在这里

⚡ 走神救援

⭐⭐Shapley 值 = 假设大家随机排队进场，每人平均带来多少增量：$\phi_i=\frac{1}{n!}\sum_\pi\Delta_\pi(i)$，其中 $\Delta_\pi(i)=v(S_\pi(i)\cup\{i\})-v(S_\pi(i))$。为什么要对所有顺序取平均？因为边际贡献取决于前面已经有谁 —— 糖对「已有面粉的团队」和对「空团队」价值完全不同。等价的联盟版里那两个阶乘 $|S|!(n-|S|-1)!$ 就是「有多少种排列让 i 恰好接在 S 后面」。🥞n=3 手算套路（面粉 A=2、糖 B=1、草莓 C=3，AB=5、AC=7、BC=4、ABC=16）：列 6 个排列，每行从左到右依次结算增量，求和除以 6 → $\phi_A=6,\phi_B=4,\phi_C=6$。⭐ 两个自查：总和 $=16=v(N)$；每一行也加起来 =16（望远镜求和），这既是效率的完整证明，也是手算最好用的检错手段。⭐四条公理（效率 / 对称 / 虚拟成员 / 可加性）唯一确定 Shapley 值（Shapley 1953）；Young 1985 用「效率+对称+边际性」也唯一确定它。⚠️ 最有争议的是可加性（要求项目合并后分配不变，而现实里合并常有协同效应）。🧤手套博弈（1 号右手套，2、3 号各一只左手套）：简单博弈可以只数「谁把局面从输变赢」，6 个排列里 1 号占 4 个 → Shapley $=(\tfrac46,\tfrac16,\tfrac16)$，而 nucleolus $=(1,0,0)$。⚠️⚠️ Shapley 值不在核心里 —— 给 2 号 1/6，1 号和 3 号合计只剩 5/6 < 1，他们会甩开他重新配对。⭐「按贡献分」和「没人想掀桌」是两个不同目标。 和解的那一类叫凸博弈（$B\subseteq A\Rightarrow$ 边际贡献更大，联盟越大加进来越值钱）：核心非空，每个排列的边际贡献向量都在核心里，Shapley 是它们的平均、核心又是凸集，所以 Shapley 也在核心里。Banzhaf 指数数「$i$ 是关键成员的联盟个数」再归一化，手套博弈 $\eta=(3,1,1)\Rightarrow\beta=(\tfrac35,\tfrac15,\tfrac15)$；⚠️ 它不满足效率，是权力指数不是分配方案。表示法：图博弈 $\phi_i=\frac12\sum_j w(\{i,j\})$（多项式时间，但判核心非空是 NP-完全）；MC-nets 用规则 模式→值 写 $v$，完全表达，靠可加性逐规则相加、线性时间。⚠️ 三种表示里「算 Shapley」和「判核心」没有一行同时容易。⭐⭐最后一件事：把「成员」换成「特征」、把「赚的钱」换成「预测值」，Shapley 值就是 SHAP。 那条「各特征贡献严格加起来等于预测值」正是效率公理；而 $n!$ 的指数复杂度，正是 SHAP 必须近似、或靠 TreeSHAP 用树结构做到多项式时间精确的原因。

下一节 👉 24-投票规则.md