📑 本页目录（点开跳转）
22 · 联盟博弈与核心
⏱ 36 分钟 ｜ ⭐ 问题从「会怎么打」变成「怎么分」
🎯 一句话
当参与者可以签有约束力的合同时，博弈论问的不再是「谁会出什么招」，而是「合作赚到的钱怎么分，才没有任何一伙人想退出去单干」。
「没有任何一伙人想退出」形式化之后，就叫 核心（Core）。
🔀 一、这里发生了一次转折
前面几章的博弈是非合作的：谁也不能强迫谁，说好的话不算数，纳什均衡回答的是「会怎么打」。从这一章起，设定变了两条：
| 非合作博弈（前几章） | 合作博弈（这一章起） | |
|---|---|---|
| 能不能签约 | 不能，承诺没有约束力 | ⭐ 能，合同可执行 |
| 分析对象 | 每个人的策略 | 每一伙人（联盟）能创造多少价值 |
| 要回答的 | 均衡落在哪 | ⭐ 总价值怎么分配 |
拼车怎么摊运费、合资项目怎么分利润、给什么分成一支队伍才不散伙、一个网络里哪个节点最关键 —— 都是这个形状。
⭐ 非合作博弈算的是「均衡」，合作博弈算的是「分配」。前者的敌人是背叛，后者的敌人是退群。
🧩 二、TU 博弈：把「一伙人值多少钱」写下来
定义（可转移效用的联盟博弈）：一对 $(N, v)$，其中 $N=\{1,\dots,n\}$ 是参与者，$v: 2^N \to \mathbb{R}$ 给每个联盟 $S$ 一个值 $v(S)$，且 $v(\emptyset)=0$。
$v(S)$ 的意思是：S 里这伙人抱团、不靠外人，能挣到多少。「可转移效用」指这笔钱在联盟内部可以任意再分（能转账）。通常还假设非负和单调（$S\subseteq T \Rightarrow v(S)\le v(T)$）。
| S | ∅ | {1} | {2} | {3} | {1,2} | {1,3} | {2,3} | {1,2,3} |
|---|---|---|---|---|---|---|---|---|
| v(S) | 0 | 4 | 2 | 1 | 7 | 10 | 11 | 15 |
⚠️ $v$ 定义在 $2^n$ 个联盟上：n=3 是 8 个数，n=20 就是一百多万个。「怎么把 $v$ 简短地写下来」本身就是研究问题，下一章讲两种写法。
简单博弈：取值只有 0/1 的单调博弈且 $v(N)=1$。$v(S)=1$ 叫获胜联盟，否则叫失败联盟。它也叫简单投票博弈 —— 描述的就是「哪些人凑一起能通过议案」。
加权投票博弈（WVG） 是它最常见的写法：给每人权重 $w_i$、定门槛 $q$，$v(S)=1 \iff \sum_{i\in S} w_i \ge q$，记作 $[q; w_1,\dots,w_n]$。例如 $[3;2,1,1]$：1 号单干不够，和谁组队都够，而 2、3 号加起来只有 2。
⚠️ 不是每个简单博弈都能写成 WVG。 取极小获胜联盟为 $\{1,2\},\{1,4\},\{2,3\}$，可同时推出 $w_1 > w_2$ 和 $w_2 > w_1$ —— 权重直观，但表达能力有缺口。
💰 三、分配的两条最低要求
支付向量 $x=(x_1,\dots,x_n)$，记 $x(S)=\sum_{i\in S}x_i$。
| 要求 | 式子 | 人话 |
|---|---|---|
| 效率 | $\sum_{i\in N} x_i = v(N)$ | 挣到的钱不多不少全分完 |
| 个体理性 | $x_i \ge v(\{i\})$ | ⭐ 没人分到的比自己单干还少 |
但一个人不想退出，不等于一伙人不想退出。核心就是把这句话补全。
⭐ 四、核心（Core）
定义（Gillies 1959）：$x$ 在核心里，当且仅当 $x(N)=v(N)$ 且
$$\forall S \subseteq N,\quad x(S) \ge v(S)$$
顺手定义后面反复要用的超额（excess）：$e(x,S) = x(S) - v(S)$ —— 「S 这伙人对现在这个分法有多满意」。正数 = 留在大联盟划算，负数 = 有理由掀桌。核心就是「所有超额 ≥ 0」。
💡 核心自动蕴含个体理性：单点集 $\{i\}$ 也是一个 $S$。核心 = 把个体理性从个人推广到每一伙人。
🔨 n=3 的手算套路
7 个非空联盟里，空集恒成立、大联盟由效率取等号、3 个单点给下限。剩下 3 个两人联盟用一个技巧翻转：因为 $x(N)=v(N)$，
$$x(S)\ge v(S) \iff x(N\setminus S) \le v(N)-v(S)$$
⭐ 于是核心变成「三个下限 + 三个上限」，一眼看得出有没有解。
完整走一遍
$N=\{1,2,3\}$，单点全 0，$v(\{1,2\})=50$，$v(\{1,3\})=70$，$v(\{2,3\})=X$，$v(N)=100$。
| 联盟约束 | 翻成上限 |
|---|---|
| $x_1+x_2 \ge 50$ | $x_3 \le 50$ |
| $x_1+x_3 \ge 70$ | $x_2 \le 30$ |
| $x_2+x_3 \ge X$ | $x_1 \le 100-X$ |
$X=60$ 时上限之和 $50+30+40=120 \ge 100$，放得下 → 核心非空。挑一个：$x=(30,20,50)$，逐条验 $50\ge50$、$80\ge70$、$70\ge60$ ✓。
$X$ 多大时核心开始空？ 要求 $50+30+(100-X)\ge 100$，即 ⭐ $X \le 80$。$X>80$ 时 2、3 抱团挣得太多，大联盟凑不出钱同时喂饱三对人。
💡 等价算法：三条不等式直接相加得 $2\cdot 100 \ge 50+70+X$，同样是 $X\le 80$。前者适合「随手找一个核心里的点」，后者适合「证明核心是空的」。
⚠️ 五、核心很容易空
最短的例子：三个人，任意两人就能完成任务 —— $v(S)=1$ 当 $|S|\ge2$，否则 0。上限技巧立刻给出 $x_1,x_2,x_3$ 全 $\le 1-1=0$，加起来最多 0，可效率要求是 1。矛盾，核心为空。 直觉：不管怎么分，总有两个人合计拿不到 1，那两人踢掉第三个自己干就赚了。
定义（否决者 vetoer）：任何不含 $i$ 的联盟都是失败的。
⭐ 定理：简单博弈核心非空 ⟺ 存在否决者；且核心里非否决者一律拿 0。
两半都很短。有否决者 $i$ 就把 1 全给他：任何获胜联盟都含 $i$，故 $x(S)=1=v(S)$。没有否决者时任取一个分配，总有 $x_i>0$，而 $v(N\setminus\{i\})=1$ 却只拿到 $1-x_i<1$ —— 那伙人当场掀桌。回看「任意两人完成任务」：去掉谁剩下两人都还能赢，没有否决者 → 必空 ✓。
🩹 六、Least Core 与 Nucleolus
核心空不代表没法分钱，只代表没法让所有人都满意。那就退一步：让最不满意的那伙人尽量不那么不满意。
ε-核心：允许 $e(x,S)\ge-\varepsilon$。Least Core 是所有非空 ε-核心的交，即把 $\varepsilon$ 压到刚好还有解（Shapley & Shubik 1966）：
$$\min \varepsilon \quad \text{s.t.}\ \ x(S)\ge v(S)-\varepsilon\ \ \forall S\subset N,\ \ x_i\ge0,\ \ \textstyle\sum_i x_i=v(N)$$
⭐ Least Core 永远非空（$\varepsilon$ 可以一直放大）。手算上面那个空核心博弈：三个两人约束相加得 $2\ge3(1-\varepsilon)$，故 $\varepsilon\ge1/3$；而 $x=(1/3,1/3,1/3)$ 恰好取到 —— least core $=\{(1/3,1/3,1/3)\}$，$\varepsilon^\ast=1/3$。
Least core 也可能有很多点，再细分一层。超额向量 $\theta(x)$：把所有 $e(x,S)$ 从小到大排成一列，首项就是「最委屈的那伙人有多委屈」。
⭐ Nucleolus：在所有效率分配里使 $\theta(x)$ 字典序最大的那一个。 人话：先把最委屈的联盟的委屈降到最小，再压第二委屈的，以此类推。 （另一种常见写法是「超额降序排、取字典序最小」，同一件事 —— 判据永远是「最坏的联盟尽量好」。）
| 性质 | 说明 |
|---|---|
| 存在且唯一 | Schmeidler 1969 ⭐ 最大的卖点 |
| 必在 least core 里 | 它是 least core 的精细化 |
| 核心非空时必在核心里 | ⭐ 不会给出「有人想退出」的分法 |
🧤 手套博弈：完整手算
1 号有一只右手套，2、3 号各一只左手套；凑成一双值 1。于是 $v(\{1,2\})=v(\{1,3\})=v(N)=1$，其余全 0。
| S | {1,2} | {1,3} | {1,2,3} | ∅ | {2} | {3} | {1} | {2,3} |
|---|---|---|---|---|---|---|---|---|
| v(S) | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| $e$ 在 $(\tfrac12,\tfrac14,\tfrac14)$ | −1/4 | −1/4 | 0 | 0 | 1/4 | 1/4 | 1/2 | 1/2 |
| $e$ 在 $(1,0,0)$ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
两个超额向量升序排好：$(-1/4,-1/4,0,0,\tfrac14,\tfrac14,\tfrac12,\tfrac12)$ 对 $(0,0,0,0,0,0,0,1)$。首项 $0 > -1/4$，后者字典序更大 —— nucleolus $=(1,0,0)$，右手套通吃。
用否决者定理复核：1 号是否决者 → 核心非空且非否决者拿 0 → 核心恰好 $=\{(1,0,0)\}$ ✓ 两条路对上了。
⚠️ 看着不公平：2、3 号各带了一只手套却一分钱拿不到。但稳定性就是这么算的 —— 只要给 2 号一分钱，1 号和 3 号就会甩开他重新配对。 ⭐ 「稳定」和「公平」在这里第一次分了家。下一章的 Shapley 值站在公平那边，给出 (4/6, 1/6, 1/6)。
📊 七、四个解概念
| 解概念 | 一定存在？ | 唯一？ | 一句话 |
|---|---|---|---|
| 核心 Core | ❌ 可能空 | ❌ 可能一大片 | 没有任何一伙人想退出 |
| Least Core | ✅ | ❌ | 最委屈的联盟，委屈降到最小 |
| Nucleolus | ✅ | ✅ | 字典序地把委屈一层层压下去 |
| Shapley 值 | ✅ | ✅ | 平均边际贡献（下一章）⚠️ 不保证在核心里 |
⚠️ 都不便宜：核心是有 $2^n$ 条约束的线性规划，Shapley 值涉及 $n!$ 个排列。「概念好定义」和「算得出来」是两件事。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 23-Shapley值.html | 手套博弈里 nucleolus 给 (1,0,0)、Shapley 给 (4/6,1/6,1/6)。同一份数据、两个都「对」的答案 —— 去看「稳定」和「公平」的分歧出在哪 |
| 24-投票规则.html | 简单博弈问「哪些人凑一起能通过议案」，那一章换个角度问同一件事：票怎么变成决定 |
| ../模型上线之后/09-特征重要性的三种谎言.html | 「哪个成员贡献大」在机器学习里叫特征重要性。先去看它在工程上会怎么被算错，下一章会把这条线接死 |
✅ 检查点
- 合作博弈和非合作博弈最本质的设定差别是哪一条？各自的「敌人」是什么？
- 为什么说「怎么写下 $v$」本身是个问题？简单博弈和加权投票博弈各是什么？
- 核心的定义是什么？为什么它自动蕴含个体理性？
- n=3 手算核心时，把两人联盟翻成「第三人上限」的那一步是怎么来的？
- 单点全 0、$v(\{1,2\})=50,\ v(\{1,3\})=70,\ v(\{2,3\})=X,\ v(N)=100$：$X$ 取什么范围核心非空？$X=60$ 时给一个核心里的点。
- 「三人、任意两人完成任务」的核心为什么空？用否决者定理再解释一遍。
- Least core 在解决什么问题？上面那个空核心博弈的 $\varepsilon^\ast$ 和解是多少？
- Nucleolus 怎么定义？三条性质是什么？手套博弈的 nucleolus 是多少，怎么验？
👀 答案
- 能不能签有约束力的合同。非合作博弈承诺不算数，分析策略、问均衡，敌人是背叛；合作博弈合同可执行，分析每一伙人能创造多少价值、问分配，敌人是退群。
- $v$ 定义在 $2^n$ 个联盟上，n=3 是 8 个数、n=20 是一百多万个，所以要简洁表示法。简单博弈取值只有 0/1 且 $v(N)=1$；WVG 是它的权重写法 $[q;w_1,\dots,w_n]$，⚠️ 但表达能力有缺口（$\{1,2\},\{1,4\},\{2,3\}$ 那个反例同时逼出 $w_1>w_2$ 和 $w_2>w_1$）。
- 效率 $x(N)=v(N)$ 且对所有 $S$ 有 $x(S)\ge v(S)$。蕴含个体理性是因为单点集也是一个 S。
- 因为效率给了 $x(N)=v(N)$，所以 $x(S)\ge v(S)$ 与 $x(N\setminus S)\le v(N)-v(S)$ 等价。核心因此变成 3 个下限 + 3 个上限。
- $X\le 80$（上限之和 $50+30+(100-X)\ge100$）。$X=60$ 时例如 (30, 20, 50)：$50\ge50$、$80\ge70$、$70\ge60$ ✓。
- 三个上限全是 $1-1=0$，加起来最多 0，效率却要 1 → 矛盾。否决者版本：去掉任何一人剩下两人还能赢，所以没有否决者，而简单博弈核心非空 ⟺ 有否决者。
- 解决「核心空了怎么办」：允许超额到 $-\varepsilon$，取刚好还有解的最小 $\varepsilon$，永远非空。那个博弈里 $2\ge3(1-\varepsilon)$ 给出 $\varepsilon^\ast=1/3$，解是 $(1/3,1/3,1/3)$。
- 把所有超额升序排成向量，取字典序最大的那个效率分配。性质：存在且唯一（Schmeidler 1969）、必在 least core 里、核心非空时必在核心里。手套博弈是 (1,0,0)：它的超额向量首项 0，大于 $(\tfrac12,\tfrac14,\tfrac14)$ 的 $-1/4$；再用否决者定理复核 —— 1 号是否决者，核心 $=\{(1,0,0)\}$ ✓。
🛑 可以停在这里
⚡ 走神救援
⭐这一章转了个弯：前面的博弈不能签约、算「会怎么打」；从这里起合同可执行、算「合作赚的钱怎么分」。前者的敌人是背叛，后者的敌人是退群。 TU 博弈是一对 $(N,v)$，$v(S)$ = S 这伙人抱团能挣多少，$v(\emptyset)=0$。⚠️ $v$ 定义在 $2^n$ 个联盟上（n=20 就是一百多万个数）。简单博弈只取 0/1，加权投票博弈 $[q;w_1..w_n]$ 是它的常见写法（如 $[3;2,1,1]$），⚠️ 但表达能力有缺口。⭐⭐核心 Core：对所有 S 都有 $x(S)\ge v(S)$ —— 没有任何一伙人想退出去单干，它自动蕴含个体理性。超额 $e(x,S)=x(S)-v(S)$ 就是「这伙人有多满意」。⭐n=3 手算套路：空集恒成立、大联盟由效率取等、3 个单点给下限、3 个两人联盟翻成第三人的上限（因为 $x(S)\ge v(S)\iff x(N\setminus S)\le v(N)-v(S)$）。例子：单点全 0、$v(12)=50,v(13)=70,v(23)=X,v(N)=100$ → 上限 $x_3\le50,x_2\le30,x_1\le100-X$，和 ≥ 100 需 $X\le80$；$X=60$ 时 (30,20,50) 在核心里。⚠️核心很容易空：「三人、任意两人就能完成任务」→ 三个上限全 0 却要凑出 1。⭐简单博弈判据：核心非空 ⟺ 有否决者，且核心里非否决者一律拿 0。 空了就退一步：ε-核心允许超额到 $-\varepsilon$，Least Core 取刚好还有解的最小 $\varepsilon$（永远非空），上例解出 $\varepsilon^\ast=1/3$、$(1/3,1/3,1/3)$。再细分是 Nucleolus：超额升序排、取字典序最大 —— 先把最委屈的联盟压到最小，再压第二委屈的。它存在且唯一（Schmeidler 1969）、必在 least core 里、核心非空时必在核心里。🧤手套博弈（1 号右手套，2、3 号各一只左手套）：$(\tfrac12,\tfrac14,\tfrac14)$ 的超额首项是 −1/4，$(1,0,0)$ 的首项是 0 → nucleolus =(1,0,0)，与否决者定理算出的核心完全一致。⚠️ 2、3 号各带一只手套却一分不拿，看着不公平，但只要给 2 号一分钱，1 号和 3 号就会甩开他重新配对 —— ⭐「稳定」和「公平」在这里第一次分了家，下一章的 Shapley 值站在公平那边，给出 (4/6,1/6,1/6)。
下一节 👉 23-Shapley值.md