第1章 合作博弈基本理论
1.1 概述
博弈论 (game theory) 是描述智能且理性的局中人之间冲突与合作情境的数学理论[1]。为了更清晰地反映“冲突与合作”内涵，Myerson[1] 建议将博弈论更名为“冲突分析论”(conflict analysis) 或“互动决策论”(interactive decision theory)。局中人间是否有互动，是区分决策问题与博弈问题的标志。
现代合作博弈起源于 von Neumann 和 Morgenstern[2] 的《博弈论与经济行为》一书，其中将博弈分为非合作博弈 (non-cooperative game) 与合作博弈 (cooperative game) 两个分支，二者的区别在于局中人之间是否能达成一个有约束力的协议 (binding agreement)[3]。
从现代观点来看，von Neumann 和 Morgenstern[2] 研究的合作博弈为效用可转移合作博弈 (transferable utility cooperative game)，Nash[4] 随后研究的合作博弈为谈判合作博弈 (bargaining game)。一般化的合作博弈，即效用不可转移合作博弈 (non-transferable utility cooperative game)，由 Aumann 和 Peleg[5] *先 提出。由于这种合作博弈比较复杂，学术界一般先研究效用可转移合作博弈及谈 判合作博弈，再将相应结果扩展到效用不可转移合作博弈。本书主要关注效用可转移合作博弈。为了行文简洁，后面将用合作博弈来指代效用可转移合作博弈。合作博弈通过给定所有潜在联盟的价值 (worth) 来描述收益分配或成本分摊情境。联盟的价值即联盟中的局中人通过合作所能取得的*保守收益或成本。合作博弈的解是一种在全体局中人间分配全局联盟价值的方法。一个解可对应一个或多个分配方案，相应的解分别称为单值解 (single-value solution) 和集合解 (set solution)。
本书主要关注合作博弈的单值解，简称值 (value)，本章先对合作博弈单值解相关理论进行简要介绍，具体安排如下：1.2 节给出合作博弈及其单值解；1.3节讨论合作博弈空间；1.4 节介绍合作博弈中的几种特殊局中人。
1.2 合作博弈及其单值解
合作博弈是描述收益分配和成本分摊情境的数学模型，其解则是一种在全体局中人间分配全局联盟价值的方法。
定义 1.1 有限集 N 上的合作博弈是一有序二元组 (N， v)，其中：
(1) N 代表局中人集；
(2) v 是从 N 的幂集到实数集的映射，即，满足。称：
(1) N 中的元素为局中人 (player)；
(2) N 的子集为联盟 (coalition)；
(3) v(S) 为联盟 S 的价值。
记 N 上合作博弈的全体为 GN(固定 N)。记合作博弈的全体为 G(可变 N)。
例 1.1 假设北京大学、广州大学和福州大学都要邀请一位美国学者来校讲学à。为节约成本，这三所学校决定合作，即邀请该学者依次到访这三所学校并分摊相关费用。不失一般性，依次记北京大学、广州大学和福州大学为 1、2、3。于是，这一合作情境可用合作博弈 (N， v) 来描述，其中：
(1)；
(2)，对任意的，代表 S 中的局中人合作时所需的*低费用。
在合作博弈的定义中，联盟价值一般应代表联盟中局中人合作时所能获得的*保守收益或成本，代表一种“*坏”情形。
例 1.2 为求解破产问题 (bankruptcy problem)，O’Neill[6] 定义了破产合作博弈 (bankruptcy game)。破产问题是描述“资不抵债”情境的数学模型。当一企业宣告破产，且其现有资产无法支付所负债务时，主管部门就必须在企业的债权人间分配企业的现有资产。记：
(1) 企业现有资产为E；
(2) 企业的有限个债权人集合为 N；
(3) 企业应付给债权人i的债务为；
(4) 企业的债务分布为。
则破产情境可用如下破产模型描述：
为求解问题 P，即将企业的现有资产分配给各债权人，O’Neill[6] 定义了破产合作博弈 (N， vE，d)：对任意的，有
显然，vE，d(S) 代表联盟 S 所能获得的*保守收益à。合作博弈的解是一种在全体局中人间分配全局联盟价值的方法。一个解可对应一个或多个分配方案，相应的解分别称为单值解 (简称值) 或集合解。本书主要关注合作博弈的单值解 (值)。
定义 1.2 任取 G0 . G(GN)。G0 上的值是一映射
其中，对任意的局中人 i ∈ N，φi(N， v) 代表用值 φ 在 N 间分配全局联盟价值v(N) 时 i 的收益。
例 1.3 (1) 均分值 (equal division value，ED) 在局中人间均分全局联盟价值á，即对任意的 (N， v) ∈ G 及 i ∈ N，有
(2) 均分剩余值 (equal surplus division value，ESD)[10] 先赋予局中人其自身价值，再将全局联盟价值剩余的部分在局中人间均分，即对任意的 (N， v) ∈ G 及i ∈ N，有
(3) 均分剩余贡献值 (egalitarian non-separable contribution value，ENSC)[10]是均分剩余值的对偶。它先赋予各局中人对全局联盟的边际贡献 (marginal contribution)，再将全局联盟价值剩余的部分在全体局中人间均分，即对任意的 (N， v) ∈G 及 i ∈ N，有
(4) 个体理性值 (dictatorial index，DI)[11] 赋予局中人其自身价值，即对任意的 (N， v) ∈ G 及 i ∈ N，有
(5) 比例值 (stand-alone-coalition proportional value)[12] 依各局中人自身价值按比例分配全局联盟价值，即对任意满足 的合作博弈 (N， v) ∈ G及i∈N，有
(6) 幼稚值 (naive solution)[13] 赋予局中人对全局联盟的边际贡献，即对任意的(N， v) ∈ G 及 i ∈ N，有
1.3 合作博弈空间
任意合作博弈 (N， v) ∈ GN 都可看成一个 2n . 1 维的实向量。于是，在 GN上可定义如下加法和数乘运算。
(1) 加法：对任意的，有
其中，对任意的，有
(2) 数乘：对任意的 α ∈ R，有 (N， αv) ∈ GN，其中 (N， αv) = α(N， v)，即对任意的 S . N，有合作博弈 αv 定义为
显然，GN 构成了一个线性空间。下面给出这一线性空间的两组常见基底。
定义 1.3 对任意的非空有限局中人集 N 及联盟 T ∈ 2N \ .，若对任意的，有
则称 N 上的使用博弈 (N， uT ) ∈ GN 是 T 一致合作博弈。
定理 1.1 对任意的 (N， v) ∈ GN [14]，有
其中
代表 Harsanyi 红利 (dividend)[15， 16]。
定义 1.4 对任意的非空有限局中人集 N 及联盟，若对任意的，有
则称 N 上的合作博弈 (N， eT ) ∈ GN 是 T 标准合作博弈。
显然，对任意的 (N， v) ∈ GN，都有
除了一致合作博弈和标准合作博弈，Yokote 等[17] 给出了合作博弈空间 GN的一组基底，即指挥官合作博弈 (command game) 类。有兴趣的读者也可按需构造 GN 的基底，或对 GN 进行拆分 (decomposition)。例如，为了求解 Shapley值[14]、加权 Shapley 值[18， 19]、Banzhaf 值[20] 及*小二乘值 (least square values)[21]的反问题 (inverse problem)，Dragan[22-25] 分别构造了与这些值对应的合作博弈空间的势基底 (potential basis)。为了刻画均分值与均分剩余值的凸组合[26]，Hu 和 Li[27] 给出了合作博弈空间的一组基底。为了刻画 Shapley 值、均分值与均分剩余值的凸组合，Yokote 和 Funaki[28] 给出了合作博弈空间的另一组基底。*近，Hernández-Lamoneda 等[29] 还给出了 GN 的一种拆分。
1.4 合作博弈中的几种特殊局中人
有几种特殊的局中人在合作博弈中比较重要，他们分别是对称局中人 (symmetric player)、无效局中人 (null player)、哑局中人 (dummy)、注销局中人 (nullifying player) 和瓦解局中人 (dummifying player)。
定义 1.5 对任意的，若任取，都有
则称 i 和 j 是 (N， v) 的对称局中人[14]。
两个局中人对称代表他们在特征函数中可以替换。Albizuri 等[30] 给出了另外两种与此相关的局中人概念。它们一方面要求两个局中人关于特征函数可以替换，另一方面分别要求两个局中人只需出现一个、必须同时出现才可创造价值。另外，若在定义 1.5 中要求 S .= .，则其转变为拟对称 (quasi-substitutes) 局中人[31]。
定义 1.6 对任意的及，若任取，都有
则称 i 是的哑局中人[14]。
哑局中人不能给任意联盟创造附加值，因而它对于收益分配过程没有发言权。
自身价值为 0 的哑局中人称为无效局中人。
定义1.7 对任意的及，若任取，都有
则称 i 是 (N， v) 的无效局中人[14]。
无效局中人不仅自身不能创造价值，还不能给任何联盟创造附加值。然而，他的出现也不会给其他联盟造成损失。一种比无效局中人更具恶意的局中人称作注销局中人。
定义1.8 对任意的 及，若任取，都有
则称i是 (N， v) 的注销局中人[32]。
注销局中人会使任何联盟的价值归零。与之对应，瓦解局中人也会给包含他的联盟带来损失，但他仅会破坏包含他的联盟中局中人间的结盟关系，而不会让该联盟的价值归零。
定义 1.9 对任意的，若任取，都有
则称 i 是 (N， v) 的瓦解局中人[33]。
展开
