《纳什均衡四川大学》PPT课件.ppt

1、2010-3-3,博弈论及其应用 （汪贤裕）,#,博弈论及其应用,第2章 纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,2,主要内容： 2.1 基本概念 2.2 纳什均衡 2.3 混合策略纳什均衡 2.4 矩阵博弈,第2章 纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,3,2.1 基本概念,2.1.1 基本概念 2.1.2 占优均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,4,2.1.1 基本概念,例2.1.1 智猪博弈 例2.1.2 夫妻爱好问题 例2.1.3 猜钱币游戏 完全信息静态博弈的三个基本要素,博弈论及其应用 （汪

2、贤裕）,#,博弈论及其应用 （汪贤裕）,5,智猪博弈,猪圈里有两头猪，一头大猪，一头小猪。猪圈的一边有一个食槽，另一边安装一个控制按钮，它能控制食料的供应。按一下按钮有8个单位的食料进入猪食槽，但需要支付2个单位的劳动成本。在吃食的过程中，若大猪先到，大猪能吃7个单位的食料，小猪只能吃1个单位。若小猪先到，小猪能吃到4个单位的食料，大猪只能吃4个单位。若两只猪同时到，大猪吃5个单位，小猪吃3个单位的食料。大猪和小猪都有两个策略，按或等待。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,6,智猪博弈（续）,两只猪在不同策略下的支付矩阵： 大猪和小猪分别采取什么样的策略，且各自的收益

3、分别为多少?,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,7,夫妻爱好问题,OR,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,8,猜钱币游戏,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,9,完全信息静态博弈三要素,局中人集合 局中人集合即博弈参加人的集合。若给定局中人 ，则记 策略集 每个局中人 有一个策略集Si ，策略集Si ， 可以是有限集，也可以是无限集，当策略集是有限集时，我们记： 当每个局中人 选定一个策略si 后，形成一个策略组合 ，并称为一个局势，记为： 我们也引入如下记号： 显然， 也是一个局势，且 。 支付函数 每个局中人有一个

4、支付函数。是局势 s 的函数，是局中人在局势下所能得到的收益。当然，每个局中人都希望自己的尽可能大。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,10,完全信息静态博弈三要素,完全信息静态博弈就是在上述三要素的基础上，分 析各局中人为实现自身利益最大化的策略行为分析。 简记为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,11,2.1.2 占优均衡,定义2.1.1 严格占优策略 定义2.1.2 占优均衡 定义2.1.3 重复剔除占优均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,12,定义2.1.1 严格占优策略,在博弈 中，若 和 是局中人

5、的两个策略，对任意策略组合 都有： （2.1.1）则称，局中人 的策略 严格占优策略 ，或称策略 相对于 是严格劣策略。 囚徒困境中、犯罪嫌疑人A和B策略（承认）就是一个严格占优策略。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,13,定义2.1.2 占优均衡,在博弈 中，若每一个局中人 都存在一个策略 ，使得 占优于 中任何策略，那么策略组合 称为 的占优策略均衡，简称占优均衡。对应的 称为占优均衡结果。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,14,定义2.1.2 占优均衡（续）,囚徒困境中严格占优均衡： （承认，承认）,博弈论及其应用 （汪贤裕）,#,

6、博弈论及其应用 （汪贤裕）,15,定义2.1.3 重复剔除占优均衡,在博弈 中，经过重复剔出严格劣策略后，每个局中人 只剩下一个唯一的策略： 那么，策略组合 称为博弈 的重复剔除占优均衡。 对应 称为 的重复剔除占优均衡结果。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,16,定义2.1.3 重复剔除占优均衡（续）,智猪博弈中重复剔除占优均衡： （按，不按）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,17,2.2 纳什均衡,2.2.1 纯策略纳什均衡 2.2.2 双矩阵博弈的划线法 2.2.3 无限策略的纯策略纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及

7、其应用 （汪贤裕）,18,2.2.1 纯策略纳什均衡,定义2.2.1 纯策略纳什均衡点和均衡结果 定理2.2.1 重复剔除占优均衡与纯策略纳什均衡 纳什均衡点与多目标规划求解比较,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,19,纯策略纳什均衡点和结果,定义2.2.1 在 人非合作博弈 中，若有策略组合 ，使得每一个 ，对任意 都有 （2.2.1） 则称 是 的一个纯策略纳什均衡点，对应的 称为对应的均衡结果。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,20,纯策略纳什均衡点和结果,夫妻爱好博弈中纯策略纳什均衡点： （足球，看足球） 策略集有限，即 ， 此类博

8、弈我们称为双矩阵博弈。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,30,双矩阵博弈称呼的由来（补充1）,在双矩阵博弈中，对任意策略组合 ，记支付函数 ， ，将两个局中人的支付函数分别记为矩阵A和矩阵B如下：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,31,双矩阵博弈称呼的由来（补充2）,（2.2.4） 回到： 划线法 定理2.2.2,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,32,划线法,对局中人1，在（2.2.4）式 的每一行 中，找出对 方支付矩阵B中该行的最大元素 ,即 并在 下划线。当 不唯一时，均在下面划线。 对局中人2，在（2.

9、2.4）式每一列 中，找出对方支付矩阵A中该列的最大元素 即 并在 下划线。当 不唯一时，均在下面划线。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,33,划线法(续),若存在一对 ，使得其两个元素 和 下面都有划线，则 是纯策略纳什均衡点， 和 是对应的纳什均衡结果。 (4)若不存在满足（3）的数对，则该博弈无纯策略纳什均衡。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,34,定理2.2.2,在双矩阵博弈 中划线法的使用： (1)若 和 同时得到划线，则 一定是 的纯策略纳什均衡点。 (2)若不存在能够同时得到划线的数对，则 无纯策略纳什均衡点。,博弈论及其应

10、用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,35,定理2.2.2的证明,设 和 都得到划线，则下面两式同时成立： （2.2.5） （2.2.6） 是博弈的纯策略纳什均衡点。 若不存在同时得到划线的数对，即不存在 同时满足（2.2.5）和（2.2.6）式，则博弈 也就不存在纯策略纳什均衡点。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,36,2.2.3无限策略的纯策略纳什均衡,定理2.2.3 无限纯策略纳什均衡点存在性定理 无限策略纳什均衡点的求解思路 例2.2.2 古诺模型 例2.2.3 伯川德双寡头垄断模型 例2.2.4 公共地的悲剧 例2.2.5 豪泰林价格竞争模型,博

11、弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,37,定理2.2.3,在博弈 中，若局中人 的策略集 是有界闭区域，支付函数 对任意 都是 的拟凹连续函数，则博弈 一定存在有纯策略纳什均衡点。 注：严格拟凹函数定义点击,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,38,严格拟凹函数定义,设 是凸集 上的函数，对任意 及任意 ，若有： （2.2.8)则 为 上的拟凹函数。 若（2.2.8）式中不等号为严格不等号，则称 为 上的严格拟凹函数。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,39,无限策略纳什均衡点的求解思路,当局中人 的收益函数 都是 上的连

12、续可微严格拟凹函数时，每个局中人都有一个最优反映函数（点击 ）组成含 个未知数的 个方程的方程组： （2.2.11） 求解（2.2.11）式得到博弈 的一个纯策略纳什均衡点 注：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,40,反应函数的定义和求解,设 是定义2.2.2规定下的拟凹函数，有： （2.2.9） 称 为局中人 在 上最优的反应函数,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,41,反应函数的定义和求解,当 对任意 是 上的严格的拟凹函数时， ，即只有一个元素。这时，最优反应函数为: （2.2.10） 若 在闭区间 上连续可微且对任意 是严格拟凹函数

13、，则令 可得最优反应函数：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,42,例2.2.2 古诺模型,设市场有1、2两个寡头厂商，生产并销售同一种产品。厂商1、2生产商品的数量分别为 和 ，他们有不同的不变边际成本，分别为 和 ，无固定成本。市场的逆需求函数为 一个正常数，即该产品的市场最高价格且 。市场需求情况和两厂商的成本和收益确定都是共同知识。两个厂商事前没有任何协议和约定，同时分别决定生产的产量，以追求市场的最大利润（设厂商的生产产量没有限制，但 ）。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,43,例2.2.2 古诺模型(续),该博弈中局中人为两个厂

14、商，生产数量是他们的策略， 即 。厂商各自的利润函数： （2.2.12） （2.2.13） 由（2.2.12）和（2.2.13）式可知， 对任何 都是 的严格连续凹函数， 对任何 都是 的严格连续凹函数。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,44,例2.2.2 古诺模型（续）,两个厂商都来确定产量以追求最大利润可以表示成： 求 和 ，并且令 和 有： （2.2.14） （2.2.15）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,45,例2.2.2 古诺模型（续）,求解最优反应函数（2.2.14）和（2.2.15）组成的方程组： （2.2.16） （2.

15、2.17） 组成该博弈的平衡局势，即纯策略纳什均衡点。均衡结果，分别为： 。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,46,例2.2.2 古诺模型（续）,该博弈的纯策略纳什均衡的意义 以厂商1为例，由 ，决定以边际利润等于边际成本来确定生产量，才是最优的。但边际利润不仅与自己的产量 有关，也受到厂商2的产量 的影响。从反应函数可知，要满足边际成本等于边际利润，其产量 与对方生产的产量 的关系必须满足（2.2.14）式。厂商2也是同样的，要满足边际成本等于边际利润，其产量 与对方的生产产量必须满足（2.2.15）式。求解（2.2.14）和（2.2.15）构成了纳什均衡。,博弈

16、论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,47,例2.2.2 古诺模型（续）,纳什均衡点和多目标规划中解概念的差异 1 以例2.2.2古诺模型为例，将有限策略放宽至无限 2 假设厂商1和厂商2有相同的不变边际成本，即,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,48,例2.2.2 古诺模型（续）,将古诺模型中两厂商如何取得自己收益最大作为多目标规划问题：,(2.2.18),其中 和 均由（2.2.12）和（2.2.13）两式确定（ ）。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,49,例2.2.2 古诺模型（续）,该多目标规划的非劣解由下图所示的直线段AB确定：,图2.2.3 古诺模型的纳什均衡与多目标规划的关系,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,50,例2.2.2 古诺模型（续）,上图中D点表示两厂商均生产 时双方的收益。 直线AB的确定 若两厂商由一个垄断集团控制，则最优产量为下式的最优解：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,51,例2.2.2 古诺模型（续）,取 ，求解上式，则当 时