合作博弈
合作博弈是博弈论的一个分支，它研究的是在一组参与者（玩家）能够形成有约束力的联盟（coalition）并进行合作时，如何分配合作所产生的总收益的问题。 与非合作博弈强调个体理性不同，合作博弈更侧重于集体理性，即如何实现效率、公正和公平的分配。
合作博弈的基本构成
一个合作博弈可以由一个二元组 $G=(N, v)$ 来定义：
-
Set of Players $N=\{1, 2, \dots, n\}$： 博弈中所有参与者的集合。
-
Coalition $S$： 联盟 $S$ 是参与者集合 $N$ 的一个子集（$S \subseteq N$）。 参与者可以组成不同的联盟进行合作。称 $N$ 为 grand coalition。
-
Characteristic Function $v(S): 2^N \to \mathrm{R}$： 特征函数 $v(S)$ 定义了每一个联盟 $S$ 通过合作所能创造或确保获得的总收益。通常假设空联盟的收益为零，即 $v(\emptyset)=0$。
Games with transferable utility (TU)
指收益可以在联盟中自由分配的博弈，反过来，比如一辆车、一部手机，这些是不可拆分的，因此是 games with non-transferable utility (NTU)
收益分配方案
一个合作博弈的结果是 $(\mathcal{C}, x)$，其中 coalition structure $\mathcal{C}=\{C_1, C_2, \dots, C_k\}$ 是 $N$ 的一个划分，满足 $\displaystyle\cup_{i=1}^k C_i=N$, $C_{i} \cap C_j = \emptyset \text{ for } i \neq j$ 。
$x=(x_1, x_2, \dots, x_n)$ 是 payoff vector，满足
- Individual Rationality: $x_i \geq v(\{i\})$
- Group Rationality: $\sum_{i\in C} x_i = v(C) \text{ for } C \in \mathcal{C}$
对形成 grand coalition 满足这两个条件的分配被称为 imputation。
通常我们会假设特征函数满足一些条件
- Superadditivity: $v(C \cup D) \geq v(C) + v(D) \text{ for all } C, D \subseteq N, C\cap D=\emptyset$ 意味着组成更大的联盟总不会变差，在这种情况下，收益分配结果总是形成 grand coalition。
- Normalized: $v(\emptyset)=0$，任何博弈均可通过平移进行标准化。
- Monotonicity: $v(C) \geq v(D) \text{ for } C \supseteq D$ ，意思是人多力量大
Stability
合作博弈的一个核心问题是解的稳定性，即是否存在促使个体偏离当前联盟与分配方案的动机。
The Core
定义 $$ \text{core} (G) = \left\{x \mid \sum_{i\in N} x_i = v(N) \text{ and } \sum_{i\in C} x_i \geq v(C), \text{ for all } C \subseteq N\right\} $$ 例:
- Voting Games: $N=\{1,2,3\}, v(C)=1 \text{ if } |C|\geq 2, \text{ otherwise }v(C)=0$ 。 此时，核心的条件要求 $x_1+x_2 \geq 1$, $x_1 + x_3 \geq 1$, $x_2 + x_3 \geq 1$ 以及 $x_1+x_2+x_3 =1$。这些不等式无法同时满足，因此该博弈的核心是空集。
因为 core 可能不存在，考虑更广泛的定义 $$ \epsilon-\text{core}(G) = \left\{x \mid \sum_{i\in N} x_i = v(N) \text{ and } \sum_{i\in C} x_i \geq v(C) -\epsilon, \text{ for all } C \subseteq N\right\} $$ 例:
- Voting Games: $N=\{1,2,3\}, v(C)=1 \text{ if } |C|\geq 2, \text{ otherwise }v(C)=0$ 。$x=(1/3,1/3,1/3)$ 是一个 1/3-core。
定义 $\epsilon^\ast(G) = \inf \{\epsilon > 0 \mid \epsilon-\text{core} (G) \text{ is not empty}\}$
Convex Games
A TU game G = (N, v) is convex if its characteristic function is supermodular。
Convex 是一个比 superadditive 更强的条件。
$f$ 是一个 supermodular 的集函数，如果： $$ f(T \cup \{i\}) - f(T) \leq f(S\cup \{i\}) - f(S), \text{ for } T \subset S, i \notin S $$ 这意味着个体 $i$ 加入到一个更大的联盟时，其作用更大。
任何一个 Convex game 都有一个非空的 core
考虑一个按特定参与者顺序 $(1, 2, \dots, n)$ 定义的收益向量 $x$：令 $x_1=v(\{1\}), x_2=v(\{1, 2\})-v(\{1\}), \dots, x_n=v(N)-v(N\backslash \{n\})$，我们有 $x_1+\dots +x_n=v(N)$。
另一方面，对任意的联盟 $C=\{i, j, \dots, s\}, i <j <\cdots < s$，有 $$ \begin{aligned} v(C) & = v(\{i\}) + v(\{i, j\}) - v(\{i\}) + \cdots + v(C) - v(C \backslash \{s\}) \\ & \leq v(\{1, \dots, i\})-v(\{1, \dots, i-1\}) + v(\{1, \dots, j\}) - v(\{1, \dots, j-1\}) + \cdots + v(\{1, \dots, s\}) - v(\{1, \dots, s-1\})\\ & \leq x_i + x_j + \cdots + x_s \end{aligned} $$ 第一个不等式是因为 $v$ 的 supermodularity，第二个不等式是因为 $x$ 的定义。
这样就通过构造的方式证明 core 的存在性。
Shapley Value
它的核心思想是：每个参与者获得的收益应该等于他对所有可能形成的联盟的平均边际贡献 (average marginal contribution)。
$n$ 个人可以形成 $n!$ 个全排列，每个全排列中可以计算个体 $i$ 的边际贡献，这些边际贡献的平均值就是
参与者 $i$ 的夏普利值 $\phi_i(v)$ 的计算公式为：
$$ \phi_i(G) = \sum_{S \subseteq N, i \notin S} \frac{|S|!(|N|-|S|-1)!}{|N|!} [v(S \cup \{i\}) - v(S)] $$
前面的分式代表了权重，即参与者 $i$ 在所有可能的加入顺序中，恰好在联盟 $S$ 形成后加入的概率。
Shapley Value 有以下几个性质：
- Efficiency: $\phi_1+\cdots+\phi_n=v(N)$
- Symmetry: 如果 $i$ 和 $j$ 是对称的，那么 $\phi_i=\phi_j$
定义 $i$ 和 $j$ 是对称的，如果 $v(C \cup \{i\}) = v(C\cup \{j\}) \text{ for } C\subseteq N\backslash \{i, j\}$
- Null player: 如果 $i$ 是 null player，那么 $\phi_i=0$
如果一个参与者 $i$ 对于任何不包含它的联盟 $S$ 均无贡献，即对所有 $S \subseteq N \setminus \{i\}$ 都有 $v(S \cup \{i\}) = v(S)$，则称 $i$ 为 null player
- Additivity: 令 $G_1=(N, u), G_2=(N, v)$ 是两个合作博弈，可以定义 $G_3=(N, u+v)$，这时有 $\phi_i(G_1+G_2)=\phi_i(G_1) + \phi(G_2)$
可以证明，满足以上 4 个性质的特征函数就是 Shapley value。
在每一个 convex game 中，Shapley value 都在 core 中。
Alternative Solution Concept
Banzhaf Index
$$ B_i(N, v) = \frac{1}{2^{n-1}} \sum_{S \subseteq N\backslash \{i\}} \left[ v(S\cup \{i\})-v(S) \right] $$
班扎夫指数衡量的是一个参与者的权力。它计算了参与者 $i$ 的平均边际贡献，但与夏普利值不同，它假设所有规模的联盟 $S$ 出现的概率是均等的。在投票博弈中，它衡量一个投票者成为“关键投票者”（即其投票能改变结果）的频率，从而量化其投票权。
Nucleolus
核仁是另一种寻求“公平”分配的解概念。它通过最小化联盟的最大“不满”程度来确定唯一的收益分配方案。具体而言，对于一个收益向量 $x$，联盟 $C$ 的“超额”或“不满”定义为 $e(C, x) = v(C) - \sum_{i \in C} x_i$。核仁选择的收益向量 $x$ 能在词典序上最小化所有联盟按降序排列的超额向量。核仁总是存在且唯一的，并且如果核心非空，核仁一定位于核心内。
Hedonic Games
当效用（如幸福感、职位满意度）无法像金钱一样自由转移时，我们就进入了 NTU 博弈的领域。
Hedonic games 指每个玩家的效用仅仅取决于他所在的那个联盟。玩家对所有他可能加入的联盟有一个偏好排序。其稳定性概念（核心）定义为：不存在一个联盟 $ S $，使得 $S$ 中的所有成员都严格偏好组成 $S$ 而不是留在自己当前的联盟中。
Stable Matching Problem
有 $n$ 个男人和 $n$ 个女人，每个人都对异性有一个从最喜欢到最不喜欢的偏好排序。目标是找到一个稳定匹配，即不存在不稳定对的匹配。
在一个匹配中，如果存在一个男人 $ m $ 和一个女人 $ w $他们没有被匹配在一起，但 $ m $ 偏好 $ w $ 超过他现在的伴侣，同时 $ w $ 也偏好 $ m $ 超过她现在的伴侣，那么$ (m, w) $ 就构成一个不稳定对。
稳定婚姻一定存在，
Gale-Shapley 算法 (Deferred Acceptance Algorithm)
该算法是一个能够保证找到稳定匹配的经典算法，并因此获得了诺贝尔经济学奖。
-
流程:
- 所有男人和女人初始都是自由的。
- 只要还存在未匹配的男人，就任选一个男人 $$ m $$。
- 男人 $$ m $$ 向他偏好列表里下一个他还没求过婚的女人 $$ w $$ 求婚。
- 女人 $$ w $$ 的回应：
- 如果 $$ w $$ 是自由的，她暂时接受 $$ m $$。
- 如果 $$ w $$ 已与 $$ m' $$ 订婚，她会比较 $$ m $$ 和 $$ m' $$。如果她更偏好 $$ m $$，她就与 $$ m' $$ 分手（$$ m' $$ 变回自由身）并暂时接受 $$ m $$。否则，她拒绝 $$ m $$。
- 重复此过程，直到所有男人都被匹配。
-
算法性质:
- 终止性: 算法一定会在有限步内（最多 $$ O(n^2) $$ 次求婚）终止。
- 稳定性: 算法的输出一定是一个稳定匹配。
- 男性最优 (Man-optimal): 算法找到的稳定匹配对所有男性来说是“最优”的，即每个男人都得到了他在所有可能的稳定匹配中能得到的最好的伴侣。
- 女性最劣 (Woman-pessimal): 与之对应，这个匹配对所有女性来说是“最差”的，即每个女人都得到了她在所有可能的稳定匹配中能得到的最差的伴侣。