专题二合作博弈PPT课件.ppt

专题二 合作博弈 在非合作的n人博弈中 局中人之间不允许事先协商和选择策略 不允许他们把策略结合起来 不允许局中人对得到的支付重新分配 一个局中人不能分享另一个局中人得到的支付 讨论的n人合作博弈 对上述问题都不加限制 局中人在选择策略时可以协商 并且局中人的支付可以相互转让 在n人合作博弈中 如何选择自己的策略已不是主要讨论的问题 n人合作博弈模型主要讨论下述问题 1 1 n个局中人之间是如何构成联盟的 2 各个联盟的支付或收益有多大 3 局中人最终在联盟中分配到多少 1 稳定集1 联盟设局中人集合N 1 2 n N的任意子集称为联盟 注1 空子集也称为一个联盟 记所有的联盟构成的集类为B 对于SB 用v S 表示联盟S中的局中人通过合作所得到的支付 因而v S 可认为定义在R上 取值于实数的一个函数 2 2 联盟博弈称为一个联盟博弈3 特征函数称v为该联盟博弈的特征函数 它满足v 0例1 局中人1 卖主 要把物品卖掉 局中人2和3 买主 分别出价9元和10元 如果局中人1将物品卖给局中人2的要价是x元 则局中人2赢利9 x元 V 1 2 9 v 1 3 10 v i v 2 3 0 i 1 2 3 v 1 2 3 10于是建立了联盟博弈 3 特征函数是研究联盟博弈的基础 确定特征函数的过程实际就是一个建立合作博弈的过程 定义1 称向量x x1 x2 xm 是联盟S 1 2 m 的一个分配 如果它满足 1 整体合理性 2 v i i 1 2 m 个体合理性 注2 的全部分配所构成的集合记为I v 注3 满足 1 2 的分配不唯一 4 定义2 设有分配x yI v 及联盟SB 如果 1 对iS 说明分配x比y好 2 说明分配中给联盟成员的支付可由联盟付出 则称对联盟S 分配x优于y 记作 如果对于 能找到一个联盟T 使 则称优于 记作 定义3 对于联盟博弈 集合s V I v 称为联盟博弈的稳定集 如果以下条件成立 5 1 S V 中任意分配x都不优于S V 中的其余分配 说明稳定集内部任何两个分配无优超关系即内稳定性 2 不属于S V 中的任何分配y 总可以在S V 中找到优于y的分配x 外稳定性 注4 稳定集的概念由冯 诺依曼 V Neumann 和摩根斯坦 Morgenstern 提出 也成为合作博弈的V N M解 6 例2设有三个局中人 拟合伙开商店 每月可赢利200元 要使商店正常营业 起码需要两人 试问 应采用怎样的方式经营 以及怎样分配利润才是合理的 解 特征函数为v i 0 i 1 2 3 v 1 2 v 2 3 v 1 3 v 1 2 3 2三人利润分配是向量x x1 x2 x3 满足x1 x2 x3 v 1 2 3 2 x1 x2 x3 0如果联盟 1 2 形成 即局中人1 2合伙 则分配x 1 1 0 是合理的 7 否则 局中人1要求采取分配 1 1 0 其中 0 1 那么局中人2与局中人3合伙 如果局中人3也采取类似的要求 则局中人2不与任何人结盟 余下1与3各持己见 1 1 不构成分配 同样 如果 2 3 结盟 y 0 1 1 是合理的分配 1 3 结盟 z 1 0 1 是合理的分配 易知w x y z 是稳定集 1 x y z之间没有优超关系 8 2020 1 7 9 2 对于w之外的任何一个分配a a1 a2 a3 满足a1 a2 a3 2且ai 0 必被w中某个分配优超 2 核心定义1 n人联盟博弈的所有不被优超的分配构成的集合称为核心 记为c v 定理1 分配方案x x1 x2 xn 在核心c v 中的充要条件 1 2 对 10 例3 设有三人联盟对策 其特征函数v 1 v 2 v 3 0 v 1 2 4 v 2 3 1 v 1 3 3 v 1 2 3 5由定理1知 这个博弈的核心由下面不等式组确定 x1 x2 4x1 x3 3x2 x3 1x1 x2 x3 5xi 0 11 其解为A x x1 x2 x3 x1 x2 x3 5 xi 0 内以 4 0 1 4 1 0 3 2 0 2 2 1 为顶点的四边形 如图 0 0 5 0 5 0 3 2 0 4 1 0 5 0 0 4 1 0 2 2 1 核 12 有些联盟博弈的核可能是空的 满足非空的条件 定理 对于n人的联盟博弈 核心非空的充要条件是线性规划有解 13 4联盟博弈的Shapley值 n人合作博弈的另一个解设为一联盟博弈 对于给定的特征函数v可以确定出特定的分配这里 14 称为联盟博弈的Shapley值 可以证明Shapley值是满足下述公理的唯一向量 A1 对称性公理每个局中