博弈论-合作博弈.pdf

合 作 博 弈合 作 博 弈 COOPERATIVE GAMESCOOPERATIVE GAMES 合作博弈的含义合作博弈的含义 前面介绍的各种博弈模型，都是非合作 博弈模型 这些（非合作博弈）模型的一个共同特 点是强调“个体理性 (individual rationality)” 合作博弈则强调群体理性 (group rationality) 群体理性的含义是：从一个群体整体角 度，研究策略的选择，使得整体效用最 大 字典中合作的含义指“为共同目的而一起 行动” 合作博弈的含义合作博弈的含义 与非合作博弈相比，需要一个描述集体 理性的效用函数 纳什认为(1951)，可利用纳什均衡这一 基本概念（非合作博弈的理论基础）， 通过参与人间讨价还价过程，达成合作 的实现在协议集(bargaining sets)理论 中对此进行了描述 详细论述参考文献3、4相应部分 合作博弈的含义合作博弈的含义 可传递效用可传递效用 (transferable utility) 为描述n人合作博弈，通常假设合作博 弈具有可传递效用 简单地说，该效用就像货币一样，可以 在各参与人之间自由转让 合作博弈的特征函数合作博弈的特征函数 合作博弈的特征函数 (characteristic function)是指，对于每一个联盟 (coalition)S (S为N的任意一个子集)，指 定一个函数v (S)，用以描述联盟S无需求 助于S之外的参与人(NS)所能得到的可 传递效用的总量 合作博弈的特征函数合作博弈的特征函数 特征函数满足 v () = 0 对于满足对于ST= 的联盟，若成立 v (ST) v (S) + v (T) 则称v 是超可加的(superadditive) 关于特征函数的一些深入讨论此处从略 合作博弈的各种解概念，就是基于特征函数 进行的。

合作的分配合作的分配 记一个合作博弈为 N, v (S), S N 一个分配(payoff allocation)就是一个向 量 x = (xi), i N 分量 xi可以被解释为合作结果对参与人i 的效用分配水平 可行分配可行分配 说一个分配对于联盟S是可行的(feasible for a coalition S) 当且仅当 ）（Svy Si i 核心的定义核心的定义 说联盟S能改进一个分配 x，当且仅当 v (S) iSxi 当且仅当x是可行的，且不存在联盟能 改进x 时，才说分配x在合作博弈的核心核心 (core)中，即x在核心中的充要条件是 NS,Svx,Nvx Si i Ni i ）（）（ 核心的定义核心的定义 一般来说，核心是一个集合可能结果 是（具体实例从略）：无穷集，唯一 集，空集 核心的理解是，如果合作博弈的一个可 行分配x 不在核心中，那就存在一个联 盟S, 该联盟中的参与人可通过更好地合 作，并在他们之间分配价值v( S)，使得 该分配结果严格优于x 核心求解的一个实例核心求解的一个实例 见电子文档cooperative games Shapley 值值 合作博弈的核心可能结果可能是空的或 非常之大，这限制了核心作为合作博弈 的解的应用 我们希望导出一个具有普遍意义的解概 念 Shapley 值是其中重要的解概念之一 Shapley公理 Shapley 提出了看上去比较 合理的几个公理假设 在这些假设下，Shapley 证明了任何合 作博弈 (N, v)存在唯一的Shapley值。

可 作为合作分配的一个解概念 Shapley 值值 参与人集合N的一个置换 (permutation)，是 任一函数：N N，使得对于N中的每个j, N 中恰好存在一个i, 使得(i) =j（是单射， 又是满射） 给定上述置换和任一联盟博弈v, 令v为满 足 v （(i) | iS）=v (S), S为N的任一子集 的联盟博弈 Shapley 值值 Shapley 公理1（对称性）对于合作博弈 (N, v), 在任一参与人的置换映射(i) 下，分配结果应保持不变，即有 (i)(v) = i(v) 公理1表明：一个参与人在博弈中的角 色才是唯一的，而不是他在集合N中的 特定名字或标号 Shapley 值值 Shapley 值值 说一个联盟R是合作博弈v的一个载体 (carrier)，如果 v (SR)=v (S), S是N的任意子集 若R是v的一个载体，那么所有不在R中 的参与人称为v的“多余人 (dummies)”， 因为他们进入任何联盟都不会改变该联 盟的价值 Shapley 值值 公理2（载体公理），对于合作博弈v和 博弈的任一联盟R, 若R是v的一个载体， 则 )()(Rvv iRi 公理3（线性性）对于任意两个合作博 弈v, w,满足0p1的任意p，以及N中 的任一参与人i, 均有 Shapley 值值 )()1 ()())1 ((wpvpwppv iii 在上述3个公理假设下，Shapely证明 了，存在唯一的一个映射,称为 Shapley 值，为 Shapley 值值 iNS i SviSv N SNS v))()(( ! )!1||(|!| )( 若v是超可加性的，则Shapely值从 i (v) v(i), iN 看，一定是个人理性的。

因为超可加性意 味着 Shapley 值值 iNSivSviSv),()()( Shapley值的应用简例值的应用简例 一些讨论一些讨论 Shapley值的结果 合作博弈解的问题 其他情况 合作博弈与非合作博弈 。