7.2.1 合作博弈
不同于非合作博弈聚焦局中人（Player）的竞争和均衡策略，博 弈论中的另一个分支主要研究局中人（或智能体）之间的合作，即所 谓的合作博弈理论[1] [3] 。现有合作博弈相关文献分为两个主要模型，一个模型允许比较两个局中人之间的效用并存在效用转移（即可转移 效用博弈（Transferable Utility game）），另一个模型中则不允许比较
（即不可转移效用博弈）。在可转移效用博弈中，一个局中人联盟
（Coalition）生成一个价值，通过合作达到共同得到的价值。联盟的成员必须分享他们联盟的价值，因此他们需要相互比较效用并能转移一些效用到彼此之间。而在不可转移效用博弈中，局中人对不同联盟有偏好，但他们无法提供任何补偿。本节中，我们主要聚焦前者—可转移效用博弈。
7.2.1.1 可转移效用博弈
一般地，可转移效用博弈包括一组局中人𝑁和一个特征函数
𝑣: 2𝑁 → 𝑅，为每个可能的联盟或局中人子集合提供一个价值。该特征函数为整个人群所共知，联盟的价值仅取决于联盟中的参与者。可转移效用博弈主要关注两个问题：应该形成什么联盟（即如何将集合 N划分为联盟），以及如何将联盟的价值分给每个成员。我们首先详细定义可转移效用博弈，然后介绍一些理想的解性质和主流的合作博弈解概念。
考虑一个包含𝑛个局中人的集合𝑁 = {1, 2, ⋯ , 𝑛}。一个联盟是指
集合𝑁的一个非空子集𝐶 ⊆ 𝑁 。特别地，集合𝑁也被称为大联盟
𝑖=1
（Grand Coalition）。所有可能联盟的集合定义为𝒞，其基数为2𝑛。一个联盟结构（Coalition Structure）是指𝑆 = {𝐶1, 𝐶2, ⋯ , 𝐶𝑚}是集合𝑁的一个划分：每个𝐶𝑖是一个联盟并且满足∪𝑚 𝐶𝑖 = 𝑁和对于任意的𝑖 ≠ 𝑗，满足𝐶𝑖 ∩ 𝐶𝑗 = ∅。一个特征函数（Characteristic Function）𝑣: 2𝑁 → 𝑅反映了一个联盟的价值或者效用。
二元组𝐺 = (𝑁, 𝑣)，其中𝑁是局中人的集合，𝑣是一个特征函数。
特征函数描述了一组局中人的价值，而不是单一局中人的收益。我们定义支付分配（Payoff Distribution）𝑥 = (𝑥1, 𝑥2, ⋯ , 𝑥𝑛)，其中𝑥𝑖是局中人𝑖的收益，用于刻画如何将联盟的价值分享给局中人。通常也使用记号𝑥(𝐶) = ∑𝑖∈𝐶𝑥𝑖代表联盟𝐶中所有局中人的收益之和。如果𝑆是一个联盟结构，𝑥是一个支付分配，那么我们称一个二元组(𝑆, 𝑥)为支付配置（Payoff Configuration），并记所有支付配置的集合为𝒫。此时，我们可以回答本节一开始的问题。可转移效用博弈的解就是一个支付配置(𝑆, 𝑥)，反映如何形成联盟和如何分配联盟价值。接下来我们介绍一些关于支付分配的理性概念，即一些连接联盟价值和个人收益的性质。
价值分配给所有局中人。换句话说，整个群体在某种程度上没有失去任何效用。
个体理性（Individual Rationality）：只有当每个局中人𝑖满足𝑥𝑖 ≥
𝑣({𝑖})时，它才会成为该联盟的成员（即加入一个联盟后要比单独行动更有利）。
𝑣(𝐶)。一个联盟的收益之和应该至少等于该联盟的价值（即在联盟层面上不应有任何损失）。
因为联盟形成问题的解是一个支付配置，所以寻找联盟结构（即寻找形成了哪些联盟）和找到支付分配（即在成员之间分享联盟的价值）的问题通常不能分开处理。现有文献中提出的不同解概念：如核心（Core）[4] 、核仁（Nucleolus）[5] 、核（Kernel）[6] 、Shapely 值
[7] 等[8] -[10] 。每种解都有各自的优缺点，不存在一个解比其他所有解方案更好。此处，我们主要介绍核心和 Shapely 值的概念及相关结
果，如果读者对其他解概念感兴趣，可以参考相关文献。
7.2.1.2 核心（Core）
核心是由Gillies 在 1953 年提出，侧重于联盟的稳定性。简言之，当没有一组局中人有任何动机组建另一个联盟时，支付分配就在核心中。详细地说，
定义 2（核心）：一个支付分配𝑥 ∈ ℝ𝑛是博弈（𝑁, 𝑣）的核心，当
且仅当𝑥满足有效性、个体理性和群体理性，即𝑐𝑜𝑟𝑒(𝑁, 𝑣) = {𝑥 ∈ ℝ𝑛|∑𝑖∈𝑁𝑥𝑖 = 𝑣(𝑁) ∩ 𝑥(𝐶) ≥ 𝑣(𝐶), ∀𝐶 ⊆ 𝑁}。
直觉上，核心反映了没有任何一组局中人有拒绝当前支付分配的
动机，也就是说，没有任何一组局中人可以通过组建其他联盟来获得更多支付，那么这个支付分配就在核心中。注意，这个条件必须对𝑁的所有子集都成立，特别是对于所有单元素子集，这可以确保个人合理性。不难发现核心是一种满足线性不等式的支付结构，因此核心是封闭的和凸的。
然而，核心的概念存在多个问题。首先，核心可能是空的：某些特征函数会产生冲突使得无法同时满足所有玩家。当核心为空时，至少有一名玩家对支付分配不满意，因此会阻止联盟形成。其次，采用核心作为稳定概念的另一个问题与计算复杂性有关。判定一种支付分配是否在核心中是 NP 难问题[11] 。此外，确定核心的非空性，即使对于具有超加性（Superadditive）的博弈，也是 NP 难问题[11] ，尽管存在一种转移方案可以收敛到核心[12] 。此外， Dieckmann 和 Schwalb[13] 介绍了一种技术，可以在非超加性博弈中达到核心分配。此外，一些合作博弈类可以保证核心非空，例如凸博弈。Bondareva 和 Shapley 独立地对核心非空的博弈类进行了刻画，提出了著名的 Bondareva–Shapley 定理[2] 。
此外，关于核心的概念也存在一些扩展。如上所述，核心的一个主要问题是它可能为空。特别地，联盟中的一名成员可能阻止形成联
盟以获得微小的回报。如果考虑建立联盟有成本时，可以认为为了获得微小的利益增益而阻止联盟不值得。强𝜖-核心（Strong 𝜖-core）和弱𝜖-核心（Weak 𝜖-core）概念描述了这种可能性。相比于核心的约束，强𝜖 -核心（弱𝜖 -核心）[14] 的约束有适当的放松：∀𝐶 ⊆ 𝑁, 𝑥(𝐶) ≥
𝑣(𝐶) − 𝜖, （对应地，∀𝐶 ⊆ 𝑁, 𝑥(𝐶) ≥ 𝑣(𝐶) − |𝐶| ⋅ 𝜖）。不难发现，如果𝜖足够大，强𝜖-核心或弱𝜖-核心将不为空。当不断降低𝜖的值时，将存在一个阈值，使得对于𝜖′ < 𝜖，𝜖′-核心将变为空集。这个特殊的𝜖-核心被称为最小核心（Least Core）[14] 。
放宽核心要求的另一种方式是稍微修改博弈。观察核心的约束可以知道，如果能够充分增加大联盟的价值，相应博弈的核心将变得不为空。这便是稳定性成本（Cost of Stability）[15] 的思想。给定一个可转移效用博弈(𝑁, 𝑣)和一个值Δ ∈ ℝ，我们考虑构建另一个合作博弈
（𝑁, 𝑣𝛥），其中对于所有的𝐶 ⊂ 𝑁, 𝑣𝛥(𝐶) = 𝑣(𝐶)，但对于大联盟𝑁，满足𝑣𝛥(𝑁) = 𝑣(𝑁) + 𝛥。稳定性成本定义为最小的𝛥，使得（𝑁, 𝑣𝛥）的核心不为空。
7.2.1.3 Shapley 值
到目前为止，许多解概念（如核心、核仁、核）都着眼于收益分配的稳定性，Shapley 值则是关注公平性。Shapley 值于 1953 由Shapley提出，从两个不同的方面描述了公平性的概念。第一种是公理化方法： Shapley 值可以用一组公理来定义，其中每个公理都是公平性的一个属性。第二种方法考虑一个联盟形成过程，在这个过程中，局中人逐个进入联盟并获得边际贡献作为收益。这种联盟形成过程可能是不公平的，因为一个局中人的收益取决于加入顺序。Shapley 值通过使用所有可能的加入顺序的平均值来反映公平性。我们将从这两种方面给出 Shapley 值的定义：
我们首先呈现几条公理，帮助我们对 Shapley 值进行刻画：
（1）有效性（Efficiency）：∑𝑖∈𝑁 𝑥𝑖 = 𝑣(𝑁)。
（2）无贡献者（Dummy Player）：我们称一个局中人𝑖是无贡献者，即对于任意联盟𝐶，𝑣(𝐶 ∪ {𝑖}) = 𝑣(𝐶)，则𝑥𝑖 = 0。
（3）对称性（Symmetry）：当两个局中人贡献相同的边际价值时，
他们的收益也相同，即如果局中人𝑖 ≠ 𝑗，对于任意的联盟𝐶，如果满足𝑖, 𝑗 ∉ 𝐶且𝑣(𝐶 ∪ 𝑖) = 𝑣(𝐶 ∪ 𝑗)，那么𝑥𝑖 = 𝑥𝑗。
（4）可加性（Additivity）：对于两个可转移效用博弈(𝑁, 𝑣)和
(𝑁, 𝑤)和对应的支付分配 x 和 y，有𝑥 + 𝑦也为博弈(𝑁, 𝑣 + 𝑤)的支付分配。
每条公理在一定程度上对支付分配函数进行了约束。实际上，
Shapley 值是唯一一个满足上述四条公理的支付分配函数。
Shapley 值的另一种定义基于有序边际贡献。首先，我们定义一个局中人𝑖对一个联盟𝐶的边际贡献，记为𝑚𝑐𝑖(𝐶)：
𝑚𝑐𝑖(𝐶) = 𝑣(𝐶 ∪ 𝑖) − 𝑣(𝐶)。
令π代表一个大联盟𝑁的加入顺序，亦可视为集合{1,2, ⋯ , 𝑛}的一个置换（Permutation）。此时，局中人𝑖遵循这个顺序加入大联盟时的边际贡献为𝑚𝑐𝑖({𝑗|𝜋(𝑗) < 𝜋(𝑖)})。记所有置换的集合为Π(𝑁)，易知其基数为|Π(𝑁)| = 𝑛!。接下来我们给出 Shapley 值的定义：
任意局中人𝑖，对应的 Shapley 值定义为
∑𝜋∈𝛱(𝑁) 𝑚𝑐𝑖({𝑗|𝜋(𝑗) < 𝜋(𝑖)})
𝜑𝑖(𝐺) =
。
𝑛!
不难发现，上述定义是基于大联盟𝑁的所有置换。如果我们从联盟的角度去观察每个局中人的Shapley 值，我们可以节省很多计算量，因为我们只需对所有可能的联盟情况进行求和。详细地，如果排在局中人𝑖前面的为联盟𝐶，那么我们可以知道前面的局中人有|𝐶|!中排列，后面的局中人有(𝑛 − |𝐶| − 1)!排列，因此，我们给出等价的 Shapley值定义：
𝜑 (𝐺) = ∑ |𝐶|!(𝑛−|𝐶|−1)! (𝑣(𝐶 ∪ {𝑖}) − 𝑣(𝐶))。
𝑖 𝐶⊆𝑁\{𝑖}
𝑛!
虽然 Shapley 值总是存在且唯一，但 Shapley 值的本质是基于组 合数，因此需要考虑形成联盟的所有可能顺序，这使得对于一般情况 下直接计算Shapley 值并不高效。当某些合作博弈自身具有特殊的结 构性质时，存在一些算法可以高效地计算 Shapley 值。另一方面，这 种计算复杂性有时可以成为一个优势，使得局中人无法从操纵中受益。例如，在某些博弈中，单个局中人可以通过伪造多个身份来受益。然 而，确定局中人是否可以从这些虚假身份中受益的复杂性已被证明是 NP 完全的[16] 。