第五章 合作博弈

第五章多人合作博弈模型 一 问题引入二 多人结盟博弈的基本概念三 多人结盟博弈的解四 常用解法 一 问题引入 例1 爵士乐队博弈 AJazzBandGounce 一位歌手 S 一位钢琴家 P 和一位鼓手 D 组成一个小乐队在俱乐部同台演出能得到演出费1000元 若歌手和钢琴家一起演出能得800元 而只有钢琴家和鼓手一起演出能得到650元 钢琴独奏表演能得300元 钢琴家没有其它收入 然而 歌手和鼓手在地铁中表演能挣500元 歌手独奏可以从TheTerasses挣200元 而鼓手单独什么也挣不到 问题 如何在这三人爵士乐队中合理分配共同演出费1000元 例2 成本分摊问题 ACostGame 三个城镇A B C欲与附近的一座电站连接起来 其可能的线路及其成本如下网络图表示 这三个镇可相互联合建设 试问如何在这三个小镇合理分摊这笔建设费 A B C 二 多人结盟博弈的基本概念 多人结盟博弈 局中人多于二人时的博弈称为多人博弈 这种博弈中如果局中人可以和其它局中人联合成一体统一行动与其它局中人对抗 这种博弈称为多人结盟博弈 这种博弈有三个基本要素 局中人N 1 2 n 结盟S 特征函数V S 一般可用表示一个多人结盟博弈 1 局中人与结盟 1 N 1 2 n 表示局中人集合 2 结盟S 表示一个联盟 即一局多人对策中 一部份局中人联合成一体像一个 局中人 一样选择策略 这种联合称为结盟 显然结盟S是局中人集合N的子集 S N 3 2n是局中人可能形成结盟的个数 2 特征函数V S 1 V S 表示当若干局中人联合成一个结盟S时 在这局博弈中能获得的最大收益值 即当形成结盟S 只要S内每一个局中人共同策略 选择相应策略结盟S能保证获得 而与联盟外局人采用什么策略无关 若S V 0 2 超可加性若一个多人博弈的特征函数具有下列性质 即对任意结盟S T N S T 满足V S T V S V T 称这个多人博弈具有超可加性 如果特征函数不满足超可加性 博弈中的结盟是不稳定的 例1 爵士乐队博弈 AJazzBandGounce 一位歌手 S 一位钢琴家 P 和一位鼓手 D 组成一个小乐队在俱乐部同台演出能得到演出费1000元 若歌手和钢琴家一起演出能得800元 而只有钢琴家和鼓手一起演出能得到650元 钢琴独奏表演能得300元 钢琴家没有其它收入 然而 歌手和鼓手在地铁中表演能挣500元 歌手独奏可以从TheTerasses挣200元 而鼓手单独什么也挣不到 问题 如何在这三人爵士乐队中合理分配共同演出费1000元 这个问题可归为一个三人合作博弈 它的特征函数V S 为 很容易验证此博弈是具有超可加性的 例2 产品博弈AProductionGame 从M1 M2 M3 M4四种原材料中各取一个单位能生产1个单位的某种产品 这个产品的价格要比它的原材料成本高出1000元 现有三个人 他们拥有这四种材料情况如下表 问 若这三人联合起来生产这种产品 他们之间该如何分配所得利润 将此问题转化为三人博弈 其特征函数如下 局中人2 3 通过合作生产 但由于他们共有四种原材料只能生产1 2个单位产品 所以能挣500元 例3 成本分摊问题 ACostGame 三个城镇A B C欲与附近的一座电站连接起来 其可能的线路及其成本如下网络图表示 这三个镇可相互联合建设 试问如何在这三个小镇合理分摊这笔建设费 A B C 这个问题的合作博弈对 N A B C 成本分摊博弈的特征函数V S 为成本节省 如下表 博弈的特征函数值V S 由下式得出 三 多人结盟博弈的解 多人结盟博弈的解的概念多人结盟博弈中 每个局中人都希望通过结盟的形式去得到更多 而博弈解的问题是如何合理确定这局博弈中每个局中人的分配收益 博弈解一般用X x1 x2 xn 表示n个局中人的得失向量 xi表示第i个局中人之所得 1 合理分配 Imputation 作为一个博弈的解X 即在博弈中对N个局中人得失的合理分配 至少应满足两个条件 1 个人合理性 2 集体合理性 条件 1 称为 个人合理性 IndividualRationality 表示局中人i所分配值xi不小于特征函数中规定他至少能得到的值V i 条件 2 称为 集体合理性 条件 GroupRationality 表示对于一个博弈解 所有局中人分配得失之和应等于所有局中人联合起来形成一个大联盟时得到的收益值 也就是这局博弈中的最大收益值V N 由超可加性 满足上述两种条件的X x1 xn 称为 合理分配 即有显然 作为多人结盟博弈的一个解X 至少必须是一个合理分配 即 例4 一局博弈 N 1 2 3 特征函数如下 V 0 V 1 V 2 V 3 0V 1 2 V 1 3 V 2 3 0V 1 2 3 1合理分配集合而就是其中两合理分配 2 支配 Domination 多人结盟博弈求解问题实际是在合理分配集I V 中 按某种准则选择一个或一组合理分配 作为对策的解 但一个对策中 不可能存在一个合理分配优于另一个合理分配 即满足 这是因为但是对于某一个联盟S 只要满足成立 这是可能的 则对S联盟而言可认为X分配优于Y分配 即得出支配概念 定义 对于两个合理分配X Y 若对于某一联盟S 有 1 2 则称合理分配X通过联盟S支配Y 记为解释 条件 1 表示对于联盟S来讲 X优于Y 条件 2 表示联盟S有足够的能力保证它的局中人I通过合作能获得合理分配定义 在博弈中 只要存在某一联盟S 且X通过S支配Y 则也称X支配Y 记为 四 常用解法 1 稳集法2 核法3 Shaply值法4 多目标规划方法 1 稳集 稳集的基本思想是选择这样一个合理分配的集合作为对策的解 不在这集合内的任何合理分配总能被这个集合中某个合理分配所支配 且这个集合内的合理分配互相不被支配 定义 对于一个对策 存在一组合理分配满足 1 则X Y互相不被支配 2 对任合理分配 则必存在则称这样一组合理分配S V 为此对策的稳集 稳集被看作多人结盟对策的一种形式 例5 有一三人结盟博弈 N 1 2 3 V S 为V V 1 V 2 V 3 0V 1 2 V 1 3 V 2 3 V 1 2 3 2很容易证明 S V 1 1 0 1 0 1 0 1 1 是此博弈的一个稳集 1 先验证这三个合理分配间不相互支配 对任一个不可能成立 例如对在三个分配中任两个之间不可能同时成立 2 设任一的合理分配分别讨论的情况 稳集作为解 从支配角度具有合理性 但存在如下问题 1 多数结盟博弈可能有多个稳集 2 有的博弈都不存在稳集 Lucas 1968 举出一个无稳集的10人博弈例子 Lucas和Rboie 1980 又举出一个无稳集的13人博弈的例子 2 核 TheCore 核的主要思想也是基于支配概念 即从合理分配集I V 中选择一组合理分配 它们对任何联盟来说都不被其他合理分配所支配 把这组合理分配 称为 核 作为博弈的一种解的形式 定义 博弈 若存在一组合理分配 对任何联盟S 满足称这组合理分配为博弈的核 并用C V 表示 记为 2 核 TheCore 定义 设X是联盟博弈的一个合理分配 若存在一联盟S 使得 则称联盟S瓦解分配X 所以 核是不会被任何联盟瓦解的合理分配的集合 例 三人 分别记为1 2 3 有机会分享300元 分配方案由民主表决通过 少数服从多数 如果达不成协议则失去这个机会 特征函数 实际问题中 经济问题的博弈通常是有核的 而在政治科学的一些多人博弈问题常常是没有核存在 为了解决此问题 提出弱核的概 核作为博弈解的合理性 核中的分配肯定不会被任何联盟推翻 因此在联盟博弈中具有稳定性 核作为博弈解的缺点 并非每一个博弈均有非空的核 通过求解下列LP问题 求得一个非空弱核 s t 称根据合理分配 稳集 核的定义有下面关系成立 即核必定在稳集内 稳集必定在合理分配集合内 3 沙波利值 TheShapleyValue 多人结盟博弈的TheShapleyValue解的概念是Shapley在1953年提出的 这个解的概念不同于前面介绍的核和稳集的概念 用核作为博弈解的思想是基于选择不被支配的合理分配去作博弈的解 而稳集是基于选择能支配一切不在这个集合内的合理分配的合理分配作为博弈的解 而Shapley则是基于期望边际收入思想上提出的 他从局中人角度分析在博弈之前 每个局中人应该期望得到多少 在一局博弈中 Shapley值由下式给出 对于一个n人合作博弈 存在唯一的一个向量函数其中 S 表示联盟S中人的个数 则称为Shapley值 Shapely法是一种期望边际收入思想 表示由于局中人参加了联盟而带来的数值 即局中人i对联盟S的边际贡献 而表示局中人参加S的概率 局中人i在 N S 个局中人前 S i 个局中人之后参加S的概率 例7 该博弈的特征函数如下V 1 aV 2 V 3 V 2 3 0V 1 2 bV 1 3 V 1 2 3 c求 i V 先把包括局中人1的联盟抄列如下 S 1 1 2 1 3 1 2 3 4 多人结盟博弈的多目标决策方法 前面所述的多人博弈的各种解的方法 都具有各自的特点和各自的缺点 从理论上讲并不存在一个最优或最合理的解 多人结盟博弈的多目标决策方法 是吸收了核解法等的思想 将求解问题转化为一个多目标规划 从而各种有效的多目标决策方法均能使用于多人结盟博弈问题 对一个多人博弈 N 1 2 N 若把每个局中人的收益值视为一个目标函数 则此问题可看成n个目标的多目标决策问题 它的解是在核C V 中或者仅在合理分配集I V