博弈论(第4章).ppt

1、,计算机与科学技术学院 Email: ,博弈论及应用（第4章）,西南民族大学,第4章 协调与谈判,主要内容： 4.1 协调博弈 4.2 相关均衡 4.3 纳什谈判解 4.4 初始参考点和其它谈判解 4.5 威胁,第4章 协调与谈判,主要内容： 4.1.1 多重纳什均衡 4.1.2 协调博弈,第4章 协调与谈判,4.1.1 多重纳什均衡 当一个博弈中存在有不止一个纳什均衡时，称为一个多重纳什均衡博弈问题。 两个基本问题： 一 、选择标准 二 、如何保证局中人的策略选择能保证所选策略能实现纳什均衡,第4章 协调与谈判,1. 帕累托占优纳什均衡 2. 风险占优纳什均衡 3. 聚点均衡,第4章 协调与

2、谈判,定义4.1.1 在博弈 中，若 均为G的其纳什均衡，若 满足 则称 为博弈G的帕累托占优纳什均衡。 例4.1.1 战争与 和平博弈 纳什均衡：（战争，战争）、（和平，和平）和一个混合策略纳什 均衡 。 帕累托占优纳什均衡: (和平，和平）,第4章 协调与谈判,例4.1.2 价格竞争博弈： 纳什均衡点：（高价，高价）、（低价，低价）和一个混合策略纳什均衡点 。 经过比较，（高价，高价）是一个帕累托占优纳什均衡。但是纳什均 衡（低价，低价）对商家更有吸引力。,第4章 协调与谈判,若两个商家临近，且出售同一品牌同一种产品 纳什均衡：（高价，高价）和（低价，低价）是两个纯策略 纳什均衡点，（高价

3、，高价）是帕累托占优纳什均衡。但此 时商家一定会出“低价”策略，而避免出“高价”策略的风险。在 这个博弈中，我们称（低价，低价）为该博弈的“风险占优纳 什均衡”。（此均衡无准确定义）,第4章 协调与谈判,聚点均衡：在多重均衡的博弈中，有一致意向选择的均衡，它取决于该博弈之外的特定环境。 夫妻爱好问题 纯策略纳什均衡分别是（足球，足球）和（芭蕾，芭蕾）。不存在上述的帕累托占优纳什均衡，也不存在风险占优纳什均衡，其均衡选择依赖于该博弈之外的特定环境。如果丈夫工作劳累，妻子温柔体贴，他们会选择（足球，足球）；如果该周末正好是妻子的生日，他们会选择（芭蕾，芭蕾）,第4章 协调与谈判,约会博弈： 现有两

4、个人约定第二天就一项重要事宜进行商讨，但未给出 具体时间。一旦约会成功，两人都会有收益，约会不能见面 会误事，收益为负效应。假设第一人在时刻到达，而第二个 人在时刻到达。显然当 时，是纳什均衡点，这种纳什均 衡点有无穷多个。 在多重均衡的博弈中，聚点均衡只能 具体问题具体分析,第4章 协调与谈判,4.1.2 协调博弈 多重均衡的博弈的两个难题 协调博弈的分类 纯粹协调博弈的特征 博弈论专家对实现协调有一些共同的看法,第4章 协调与谈判,4.1.2 协调博弈 第一个难题 当理性的局中人面临着多种策略可以达到均衡时，如何使所有局中人在策略选择上实现纳什均衡的一致性，即使每个局中人的选择结果而组成的

5、策略组合是一个纳什均衡。 第二个难题 在多重均衡中，存在有社会最优的帕累托占优纳什均衡，如何使所有的局中人选择策略，使得组成的策略组合是一个帕累托占优纳什均衡。,第4章 协调与谈判,4.1.2 协调博弈 协调博弈的分类:纯粹协调博弈和非纯粹协调博弈 纯粹协调博弈：局中人对不同的均衡有相同的 偏好。（例4.1.2） 非纯粹协调博弈：局中人对不同的均衡有不同的 偏好。（夫妻爱好博弈）,第4章 协调与谈判,例4.1.4 Cooper的协调博弈 设有两个局中人A和B，两人从事同一种生产。局中人努力的 情况为 。假设人均消费量为 每个人的得益为 得益矩阵： （1，1）是风险占优均衡，（2，2）是帕累托占

6、优纳什均衡。,第4章 协调与谈判,4.1.2 协调博弈 策略的互补性：有一个局中人选择了帕累托占优纳什均衡中的策略，能增加另一方选择帕累托占优纳什均衡中策略的边际收益。这种具有正反馈的特征称之为策略的互补性。 对纯粹协调博弈，（下面简称协调博弈）的研究大多采用实验博弈的方法进行,第4章 协调与谈判,CG（Cooperation Game）的得益矩阵： 纯策略纳什均衡1，1和2，2，其中1，1是风险占优均衡，2，2是帕累托占优纳什均衡 库珀（Cooper）实验 选择了11个人，每人均与其余人进行上述得益矩阵下的两次博弈，其博弈顺序不是公共的知识。若每次博弈完后，则按上面得益矩阵计分。当实验全部结

7、束后，参与人按所得的分数进行奖励。,第4章 协调与谈判,4.1.2 协调博弈 实验结果表明，自然协调成功的情况不存在风险占优在该博弈中的指导作用要好于帕累托占优。 类似的2人协调博弈实验:取所取得局中人的得益函数为 其中:为局中人的策略，取值为自然数序列 这些实验都与库珀对CG-22的博弈实验有类似结论,第4章 协调与谈判,例4.1.6 CG-33协调博弈：CG的意义同例4.5，33是指一个2人3策略的非合作博弈。 得益矩阵： 库珀通过改变参数x和y的取值，实验局中人对这些参数的理解和对均衡的影响。三个最典型的实验：,第4章 协调与谈判,情形1: (x，y)=(1000，0) 情形2: (x，

8、y)=(700, 1000) Cooper 实验的结果： （1）博弈的结果基本上都是纳什均衡； （2）在情形1中，多数结果是1，1风险占优均衡；在情形2中，多数结果是2，2帕累托占优纳什均衡。,第4章 协调与谈判,情形3 : (x，y)=(700, 650) 博弈分析： 3，3仍然是次优的策略组合。对策略3，局中人的最优反应是策略1。 Cooper 实验的结果： 实验结果表现为均衡2，2结果。库珀得到“没有出现完全和 这些结果一致的解释”。这里的“这些结果”是指上面提出的， 寻求次优策略的最优反映导致了均衡结果的选择。,第4章 协调与谈判,博弈论专家对实现协调有一些共同的看法 博弈前的交流 外

9、部建议 外部选择,第4章 协调与谈判,博弈前的交流 假定在博弈前，局中人可以向对方传递信息，但这一信息 并不约束局中人在博弈中对策略的选择。这类博弈通常称为 廉价商议（cheap talk）博弈。,第4章 协调与谈判,2. 外部建议 假设在博弈前，存在一个局中人之外的建议者，他对局中人 的策略选择给出建议。范海克（Van Huyck）等人对下面三 个博弈进行了外部建议的实验。 实验（a） 实验结果（a）：收到外部建议之前40%在纯策略纳什均衡上协调成功；给出外部建议时协调成功的概率是95%,第4章 协调与谈判,实验（b） 实验结果： 1. 未收到外部建议之前98%的博弈实验结果是纳什均衡（1，

10、1） 2. 外部建议选取均衡3，3时 17%的局中人接受了建议 3. 外部建议选取2，2时有75%的局中人接受了建议 结果表明当建议不符合局中人利益时，局中人并不接受建议,第4章 协调与谈判,实验（c） 实验结果： 1. 未收到外部建议之前70%的博弈实验结果是纳什均衡（2，2） 2. 外部建议者给出一个1，1均衡（或3，3均衡）建议时实验博弈的结果与建议相符的只有16% 结果表明若外部建议不是帕累托占优纳什均衡时，建议无效,第4章 协调与谈判,3. 外部选择 假定在协调博弈之前增加一个对博弈之外的选择，再进行协 调博弈，会增加协调成功的可能性。 库珀对CG-22协调博弈（即例4.1.5）实验

11、 77%的博弈结果是2，2帕累托占优纳什均衡，只有2%的博 弈结果是1，1风险占优均衡。 范海克对CG-22协调博弈进行了实验 几乎所有的结果都是2，2帕累托占优纳什均衡。,第4章 协调与谈判,4.2 相关均衡 在例4.1.6，CG-33协调博弈中，无论（x，y）取什么样的数 对， 1，1和2，2都是纯策略纳什均衡点，而博弈中效率 最高的结果（600，600）是策略组合3，3的结果。 纳什均衡没有考虑效率，如何实现效率最高的策略组合？ 相关均衡-利用纳什均衡思想，事前沟通，实现结果转变。,第4章 协调与谈判,1 夫妻爱好博弈 纯策略纳什均衡：（足球，足球）和（芭蕾，芭蕾）。 静态博弈中策略选择

12、结果未必是纳什均衡。 一个约定 抛一硬币，若正面向上，在博弈中，双方都选择足球策 略；若反面向上，在博弈中，双方都选择芭蕾策略。根据 博弈前双方的约定，保证博弈的结果是一个纯策略纳什衡。,第4章 协调与谈判,2 广告博弈 有两个商家出售同一种商品。为了促进商品的销售，可以进 行广告宣传，但做广告需要成本。假设两个商家都做广告， 肯定双方都有收益；都不做广告，则双方都无收益；若有一 个商家做广告，而另一家不做，则做广告的商家独自承担成 本，但另一个商家则坐享广告带来的好处。收益情况如图： 纳什均衡：做广告，不做广告，不做广告，做广告 和 。混合策略纳什均衡的结果是,第4章 协调与谈判,博弈的约定

13、： 约定1 ：抛一枚硬币，若正面向上，采用（做广告，不做广 告）策略组合；若反面向上，采用（不做广告，做广告）策 略组合。由于抛硬币时出现正面和反面的概率都是一样的， 则每个商家得到的期望收益为：,第4章 协调与谈判,约定2：选择一个博弈的局外人，按下面三步确立每个商家的 策略选择： 第一步，局外人在A,B,C中随机地任取一个字母，然后进入下一步； 第二步，若局外人选取是A则通知商家1，不通知商家2；若局外人选取是B，则通知商家2，不通知商家1；若局外人选取是C则两个商家都不通知，然后进入第三步； 第三步，若商家1得到通知，则选择不做广告，否则选择做广告，若商家2得到通知，则选择不做广告，否则

14、选择做广告。,第4章 协调与谈判,约定2：选择一个博弈的局外人，按下面三步确立每个商家的 策略选择： 约定的结果： （1）局外人选取A，则有策略组合不做广告，做广告，导致一个纳什均衡的出现； （2）局外人选取B，则有策略组合做广告，不做广告，导致一个纳什均衡的出现； （3）局外人选取C，则有策略组合做广告，做广告，导致一个次优策略组合出现；,第4章 协调与谈判,由第一步的选取是等可能的，则选取A，B和C的概率分别 是 ，因而商家的期望收益为： 。 广告博弈中的博弈前约定满足下面两个要求： 1. 约定是公平合理的，双方都愿意接受； 2. 在约定的要求下，没有人愿意单独的违背约定，否则可能导致自己

15、得益的损失。 上面两个条件的约定实际上是博弈中局中人策略选择的理性规定，称之为博弈的相关均衡。,第4章 协调与谈判,广告博弈 两种约定的比较 1. 根据博弈的得益结构情况看：第一种约定比第二种约定的结果要差些 2. 将得益结构作如下变化： 约定1要比约定2好。（提示： ）,第4章 协调与谈判,博弈的相关均衡的确立是一种机制设计的思想。 这种机制设计满足纳什均衡的思想，这种机制设计必须 使博弈的局中人对博弈有足够的理解和相互的信任，因为约 定是没有法律效力的。 适用于相关均衡的博弈分析必须是局中人的收益情况是 对称的，这才能保证约定的公平合理。 ）,第4章 协调与谈判,4.3 纳什谈判解 纳什谈

16、判解的实质 二人谈判问题 谈判过程 纳什公理体系 纳什谈判解的定义 纳什谈判解的三个定理 例题4.3.1 例题4.3.2,第4章 协调与谈判,4.3 纳什谈判解 1 纳什谈判解又称为纳什讨价还价解 2 纳什谈判解(1950,纳什)从非合作博弈向合作博弈的演变 这里的合作博弈具有非线性的可转移支付。如何使局中人 能得到的收益达到公平合理，纳什给出了纳什公理体系，并推导出纳什解的结果。,第4章 协调与谈判,设有一个二人有限策略的完全信息静态博弈，即双矩阵博 弈。局中人1取混合策略 ，局中人2取混合策略集 ，局中 人1和2的支付矩阵分别是A和B。即 。当 局中人1取策略 局中人2取策略 时，局中人1

17、和 2的得益 分别为:,第4章 协调与谈判,记两人所得为 ，并考虑到可用抽彩方式决定两人的收 益，且抽彩结果是线性的，则两个局中人的得益 是 中一个有界闭凸子集，记 并称为结果集或可达集。即任何 表示两个局中人可以共同行动，分别获得收益。 一般地讲，在可达集 的帕累托边界上，一个局中人得到的 多一些，另一个局中人得到的就少一些。那么一个局中人能 同意让对方得到多少呢？给对方少一些所得，对方是否会接 受呢？这构成了两个局中人的谈判问题。,第4章 协调与谈判,纳什公理体系 公理1 (个体合理性) ； 公理2 (可行性) ； 公理3 (帕累托最优性) 若 , 且 ，则 公理4 (无关方案的独立性)

18、若 ， 则 公理5 (线性变换的无关性) 若 ，且 则 。 公理6 (对称性) 如果对任意 ，都有 ，若 ， 则,第4章 协调与谈判,定义4.3.1 满足上述纳什公理体系下的称为纳什谈判解 （Nash bargaining solution）,第4章 协调与谈判,定理4.3.1 若 是有界的闭凸集， 为谈判初始点。若有 满足 ，则下面的规划有唯一的最优解： （4.3.4） 定理4.3.2 若 是定理4.3.1条件下的最优解，令函数 （4.3.5） 则 有 。,第4章 协调与谈判,定理4.3.3 设2人谈判问题的结果集 为凸集， 是初始参考点，则存在唯一满足公理1到公理6的函数 。,第4章 协调

19、与谈判,对定理的说明： 定理4.3.3表明，满足纳什公理体系的谈判解 是存在的。 定理4.3.1表明， 是 函数在 中求最大值时的最优解。满足纳什公理体系（公理1公理6）的纳什谈判解也简称为谈判解，有的教材也称为纳什解。,第4章 协调与谈判,对定理的说明： 定理4.3.2表明，根据该定理，对 有 。 若取等号，即有： （4.3.13） 上式右端是一个常数，因此上式 是 上的一条直线，对于任意 中的 点 都在该直线的左下方。,第4章 协调与谈判,当结果集 的边界是光滑的，该直线是 的切线，且切点在 点 。再从（4.3.13）式看，该直线的斜率为： 而连接 和 直线斜率为 ，正好是上式的相 反数。

20、 反映了在谈判过程中，两个局中人可以接受的效用 转换率。,第4章 协调与谈判,当两个局中人在谈判中的效用转换率为1：1时，（ ）问 题变得更简单。例如，两人谈判 问题的结果集在直线 的左下方。 若初始参考点为 ， 则纳什谈判解为,第4章 协调与谈判,帕累托最优边界：讨价还价问题 的解 一定 在的子集 上。（根据公理 3） 因为 是凸的，因此 是这些 的点：不存在一个 ，使得 并且 。我们称 为 帕累托最 优边界。,第4章 协调与谈判,边界光滑：若T是初始参考点，P是纳什谈判解，则TP的斜率 与过P点 的切线的斜率互为相反数。在TP上任意一点U作为 初始谈判点，其纳什谈判解仍是P点。 边界为多边

21、形：若 的斜率等于BC斜率的相反数，则对 上任一点U，作为初始谈判点，那么它们的纳什谈判解都是 。,第4章 协调与谈判,应用举例：例4.3.1 设有一雇员为公司老板打工，若雇员打工后可为公司一 年盈利10万元，而雇员不打工，则无盈利，那么对这10万元 盈利应如何分配？ 假设雇员本人总共有资产价值10万元，若能分到盈利 ， 他所增加的效用为 ，令 ， 为大于0的一个常数。很容易验证： ，表明 雇员是穷人，具有风险规避的特点。公司老板是富有的，如 他能分到盈利 ，他所增加的效用为 。,第4章 协调与谈判,应用举例：例4.3.1 公司老板和雇员对盈利10万元分配进行谈判，谈判的初始 参考点为 ，即公司老板不雇工，对老板和雇员的 增加效用均为0，且 。则有 (4.3.15) 则结果集 为下图所示，其中