纳什均衡(四川大学).ppt

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 猜钱币游戏 完全信息静态博弈的三个基本要素,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,5,智猪博弈,猪圈里有两头猪，一头大猪，一头小猪。猪圈的一边有一个食槽，另一边安装一个控制按钮，它能控制食料的供应。按一下按钮有8个单位的食料进入猪食槽，但需要支付2个单位的劳动成本。在吃食的过程中，若大猪先到，大猪能吃7个单位的食料，小猪只能吃1个单位。若小猪先到，小猪能吃到4个单位的食料，大猪只能吃4个单位。若两只猪同时到，大猪吃5个单位，小猪吃3个单位的食料。大猪和小猪都有两个策略，按或等待。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,6,智猪博弈（续）,两只猪在不同策略下的支付矩阵： 大猪和小猪分别采取什么样的策略，且各自的收益分别为多少?,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,7,夫妻爱好问题,OR,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,8,猜钱币游戏,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,9,完全信息静态博弈三要素,局中人集合 局中人集合即博弈参加人的集合。若给定局中人 ，则记 策略集 每个局中人 有一个策略集Si ，策略集Si ， 可以是有限集，也可以是无限集，当策略集是有限集时，我们记： 当每个局中人 选定一个策略si 后，形成一个策略组合 ，并称为一个局势，记为： 我们也引入如下记号： 显然， 也是一个局势，且 。 支付函数 每个局中人有一个支付函数。是局势 s 的函数，是局中人在局势下所能得到的收益。当然，每个局中人都希望自己的尽可能大。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,10,完全信息静态博弈三要素,完全信息静态博弈就是在上述三要素的基础上，分 析各局中人为实现自身利益最大化的策略行为分析。 简记为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,11,2.1.2 占优均衡,定义2.1.1 严格占优策略 定义2.1.2 占优均衡 定义2.1.3 重复剔除占优均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,12,定义2.1.1 严格占优策略,在博弈 中，若 和 是局中人 的两个策略，对任意策略组合 都有： （2.1.1）则称，局中人 的策略 严格占优策略 ，或称策略 相对于 是严格劣策略。 囚徒困境中、犯罪嫌疑人A和B策略（承认）就是一个严格占优策略。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,13,定义2.1.2 占优均衡,在博弈 中，若每一个局中人 都存在一个策略 ，使得 占优于 中任何策略，那么策略组合 称为 的占优策略均衡，简称占优均衡。对应的 称为占优均衡结果。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,14,定义2.1.2 占优均衡（续）,囚徒困境中严格占优均衡： （承认，承认）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,15,定义2.1.3 重复剔除占优均衡,在博弈 中，经过重复剔出严格劣策略后，每个局中人 只剩下一个唯一的策略： 那么，策略组合 称为博弈 的重复剔除占优均衡。 对应 称为 的重复剔除占优均衡结果。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,16,定义2.1.3 重复剔除占优均衡（续）,智猪博弈中重复剔除占优均衡： （按，不按）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,17,2.2 纳什均衡,2.2.1 纯策略纳什均衡 2.2.2 双矩阵博弈的划线法 2.2.3 无限策略的纯策略纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,18,2.2.1 纯策略纳什均衡,定义2.2.1 纯策略纳什均衡点和均衡结果 定理2.2.1 重复剔除占优均衡与纯策略纳什均衡 纳什均衡点与多目标规划求解比较,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,19,纯策略纳什均衡点和结果,定义2.2.1 在 人非合作博弈 中，若有策略组合 ，使得每一个 ，对任意 都有 （2.2.1） 则称 是 的一个纯策略纳什均衡点，对应的 称为对应的均衡结果。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,20,纯策略纳什均衡点和结果,夫妻爱好博弈中纯策略纳什均衡点： （足球，看足球）&（看芭蕾，看芭蕾）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,21,纯策略纳什均衡点和结果（续）,猜钱币游戏中不存在纯策略纳什均衡点。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,22,定理2.2.1,在 人非合作博弈 中： 若， 是重复剔除占优均衡， 则 一定是纯策略纳什均衡点。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,23,定理2.2.1的证明,证明：用反证法。 若 是重复剔除占优均衡，但不是纯策略纳什均衡点。则有 和 , , 使得 （2.2.2） 那么在局中人 在对 的剔除过程中应有对任意的策略组合 满足 （2.2.1）式。这里策略组合当然也包括 ，即 因此（2.2.2）式是不可能出现的，即（2.2.2）式与剔除严格劣策略过程矛盾。 从而定理2.2.1成立。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,24,纳什均衡点与多目标规划求解比较,在n人非合作博弈 中，对每一个局中人 ，都在寻找自己的策略 使得自己的收益 最大，但是局中人 单方面不能找到自己的最佳策略，其结果是相互影响的，是由策略组合 决定的。这就是一个有相互影响的多人决策问题。有人可能这样设想：是否有一个局外人，将 个局中人的收益最大作为 个目标的多目标规划问题，即求： （2.2.3） 纳什均衡点和上面的（2.2.3）的多目标规划的求解是两个不同的概念。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,25,纳什均衡点与多目标规划求解比较（续）,囚犯困境是一个2人非合作博弈 两个局中人策略集 和支付 函数 都表示在表1.2.1中 图2.2.1 囚犯困境中的局中人 收益图,以囚徒困境为例,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,26,纳什均衡点与多目标规划求解比较（续）,各点代表不同策略组合下双方的收益： A点对应策略组合（承认，承认） B点对应策略组合（承认，不承认） C点对应策略组合（不承认，不承认） D点对应策略组合（不承认，承认） B点、C点和D点所代表的策略组合 都是单人决策的多目标规划（2.2.3） 中的非劣解。 但策略组合（承认，承认）是唯一的纳什均衡点。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,27,纳什均衡点与多目标规划求解比较（续）,结论： （一）非合作博弈中的纳什均衡点，不可能用（2.2.3）表示的多目标规划作为替代，双方有不同的思想基础。 （二）博弈论与多目标规划这类多人决策问题的差异，进一步显示出纳什均衡思想在博弈论中的重要地位。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,28,2.2.2 双矩阵博弈的划线法, 双矩阵博弈的定义 纯策略纳什均衡的简单求解方法划线法 定理2.2.2 划线法与纯策略纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,29,双矩阵博弈的定义,在博弈中，若三要素的前两个要素满足： 只有两个局中人，即 ; 策略集有限，即 ， 此类博弈我们称为双矩阵博弈。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,30,双矩阵博弈称呼的由来（补充1）,在双矩阵博弈中，对任意策略组合 ，记支付函数 ， ，将两个局中人的支付函数分别记为矩阵A和矩阵B如下：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,31,双矩阵博弈称呼的由来（补充2）,（2.2.4） 回到： 划线法 定理2.2.2,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,32,划线法,对局中人1，在（2.2.4）式 的每一行 中，找出对 方支付矩阵B中该行的最大元素 ,即 并在 下划线。当 不唯一时，均在下面划线。 对局中人2，在（2.2.4）式每一列 中，找出对方支付矩阵A中该列的最大元素 即 并在 下划线。当 不唯一时，均在下面划线。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,33,划线法(续),若存在一对 ，使得其两个元素 和 下面都有划线，则 是纯策略纳什均衡点， 和 是对应的纳什均衡结果。 (4)若不存在满足（3）的数对，则该博弈无纯策略纳什均衡。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,34,定理2.2.2,在双矩阵博弈 中划线法的使用： (1)若 和 同时得到划线，则 一定是 的纯策略纳什均衡点。 (2)若不存在能够同时得到划线的数对，则 无纯策略纳什均衡点。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,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 豪泰林价格竞争模型,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,37,定理2.2.3,在博弈 中，若局中人 的策略集 是有界闭区域，支付函数 对任意 都是 的拟凹连续函数，则博弈 一定存在有纯策略纳什均衡点。 注：严格拟凹函数定义点击,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,38,严格拟凹函数定义,设 是凸集 上的函数，对任意 及任意 ，若有： （2.2.8)则 为 上的拟凹函数。 若（2.2.8）式中不等号为严格不等号，则称 为 上的严格拟凹函数。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,39,无限策略纳什均衡点的求解思路,当局中人 的收益函数 都是 上的连续可微严格拟凹函数时，每个局中人都有一个最优反映函数（点击 ）组成含 个未知数的 个方程的方程组： （2.2.11） 求解（2.2.11）式得到博弈 的一个纯策略纳什均衡点 注：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,40,反应函数的定义和求解,设 是定义2.2.2规定下的拟凹函数，有： （2.2.9） 称 为局中人 在 上最优的反应函数,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,41,反应函数的定义和求解,当 对任意 是 上的严格的拟凹函数时， ，即只有一个元素。这时，最优反应函数为: （2.2.10） 若 在闭区间 上连续可微且对任意 是严格拟凹函数，则令 可得最优反应函数：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,42,例2.2.2 古诺模型,设市场有1、2两个寡头厂商，生产并销售同一种产品。厂商1、2生产商品的数量分别为 和 ，他们有不同的不变边际成本，分别为 和 ，无固定成本。市场的逆需求函数为 一个正常数，即该产品的市场最高价格且 。市场需求情况和两厂商的成本和收益确定都是共同知识。两个厂商事前没有任何协议和约定，同时分别决定生产的产量，以追求市场的最大利润（设厂商的生产产量没有限制，但 ）。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,43,例2.2.2 古诺模型(续),该博弈中局中人为两个厂商，生产数量是他们的策略， 即 。厂商各自的利润函数： （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.2.17） 组成该博弈的平衡局势，即纯策略纳什均衡点。均衡结果，分别为： 。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,46,例2.2.2 古诺模型（续）,该博弈的纯策略纳什均衡的意义 以厂商1为例，由 ，决定以边际利润等于边际成本来确定生产量，才是最优的。但边际利润不仅与自己的产量 有关，也受到厂商2的产量 的影响。从反应函数可知，要满足边际成本等于边际利润，其产量 与对方生产的产量 的关系必须满足（2.2.14）式。厂商2也是同样的，要满足边际成本等于边际利润，其产量 与对方的生产产量必须满足（2.2.15）式。求解（2.2.14）和（2.2.15）构成了纳什均衡。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,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 古诺模型（续）,取 ，求解上式，则当 时， 有最值 。也就是说，当厂商1采取策略 ，厂商2采取 ，而 时，厂商1的收益 和厂商2的收益 满足 。这样，厂商1和厂商2的收益的帕累托边界为直线段AB。对应多目标规划（2.2.18）的非劣解为： ， ，,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,52,例2.2.2 古诺模型（续）,多目标规划（2.2.18）的任何满意解都是依一定的法则在非劣解中寻求满意解。而此时古诺模型的纳什均衡为：,对应的收益为图2.2.3的C点，即两厂商的收益分别是 。纳什均衡点 是多目标规划（2.2.18）中的劣解。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,53,例2.2.2 古诺模型（续）,结论 在策略集为无限时，纳什均衡点仍然不是多目标规划中的非劣解。 纳什均衡与多目标规划存在不同，是不可混淆的。造成这种差别的原因在于，纳什均衡是多人决策，而多目标规划是单人决策。 博弈论的一个最显著特征：竞争环境下的多人决策。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,54,伯川德双寡头垄断模型,考虑市场上有两个寡头厂商生产同一类型产品。厂商1和厂商2分别选择价格 和 。消费者对企业的产品的需求为： 其中0b1，即只限于企业 的产品和企业 产品具有相互替代的情况。企业生产没有固定成本，并且边际成本为常数 ， 。 两个企业同时进行价格选择行动。另外企业 的策略 是所选价格 ，也即每个企业的策略集 。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,55,伯川德双寡头垄断模型（续）,企业 选择价格 ，对手 选择价格 ，企业的利润为： （2.2.20） 对于企业1来说，若企业2选定的价格为 ，它确定自己的价格 以追求最大利润 对企业1求 并且令 解得： （2.2.21）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,56,伯川德双寡头垄断模型（续）,同理，可得企业2的最优价格 （2.2.22） 联立（2.2.21）（2.2.22）解方程组得： （2.2.23） 均衡结果为： （2.2.24）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,57,例2.2.4 公共地的悲剧,考虑有相同情况的 个牧民组成的某个牧民村，他们共同拥有一片草地。每年所有的牧民都会在共同的草地上放牧养羊。用 表示牧民 养羊的头数，则牧民村的养羊总头数为 。购买羊崽和照看一只羊的成本为c，c不随某一牧民拥有羊的树目的多少而变化。当草地上的羊的总头数为 时，牧民养的一只羊的价值为 ，设 。当草地上羊的总头数 较少时，每只羊有相对较多的空间，每只羊能吃到的草也丰盛些。而羊的总数 增加时，则正好相反，每只羊相对能吃到的草相对较少。并有当羊群总数 达到一个极限 时，再增加一只羊将对已经牧养的羊带来损害。对一只羊的价值 的上述特征用公式表示，则为: ， 。,(2.2.25),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,58,例2.2.4 公共地的悲剧(续),每年春天， 个牧民同时分别选择牧养羊的数量。假设其是连续的可分割的。牧民 的策略是选择在公共草地上牧养羊的数量 ，并有策略集 。当其他村民养羊数为 时，牧民 牧养 只羊获得的收益为： 现在要讨论的问题是：牧民 如何决定自己的牧养羊数 ， ，以获得自己的最大收益。,(2.2.26),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,59,例2.2.4 公共地的悲剧(续),这构成了一个 人非合作博弈的问题，需要求平衡局势，即纳什均衡。很明显， 在任何 时，都是 的凹函数。计算 并且令 ，得到： 当 是一个已知函数时，求解由上式给出的 个方程和 个未知数，可以求得该体系的纯策略纳什均衡点，即平衡局势 再代回到（2.2.26）式，则有纳什均衡结果。,(2.2.27),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,60,例2.2.4 公共地的悲剧(续),公共地的悲剧的意义 将上面的 人非合作博弈的牧养羊纳什均衡结果与草地在非公共地的情况下，即由社会计划管理者进行管理作对比研究。 在 个牧民分散独立决策牧养羊情况下，设 是第 个牧民的养羊数 最优决策， 。由于 个牧民是相同情况,则: ， ， 。 令 ，则由（2.2.27）式得： 再将（2.2.28）的 个方程加总，有：,(2.2.29),(2.2.28),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,61,例2.2.4 公共地的悲剧(续),若草地是由社会计划者管理，社会计划者选择草地的最优牧 养量是 ，则 应该是下式的解： 若上式的最优解为 ，则 应满足 （边际收益等于边际成本），即： 比较（2.2.29）式和（2.2.31）式，下面我们证明 。 由式（2.2.29）和（2.2.31）式有：,(2.2.30),(2.2.31),(2.2.32),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,62,例2.2.4 公共地的悲剧(续),令 由（2.2.32）式和（2.2.25）式有： 由（2.2.33）式和（2.2.25）式得： 由（2.2.34）和（2.2.35）有：,(2.2.33),(2.2.34),(2.2.35),(2.2.36),由于 个牧民是对称的，则他们分散养羊的总收益为： ，而社会计划管理者的养羊带来的总收益为: 。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,63,例2.2.4 公共地的悲剧(续),由于 是（2.2.30）式的最优解，则必有: （2.2.36）式表明，在均衡点时， 个牧民牧养羊的总数超过社会最优条件下的牧养总数。并由（2.2.37）式， 个牧民养羊的总收益低于社会计划管理者的总收益。由于每个牧民都只考虑自己的利益，并不管其行为对其他牧民带来的影响，致使公共草地被过度使用，并且得不偿失。这就是经济学中的“公共地的悲剧”。,(2.2.37),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,64,例2.2.5 豪泰林价格竞争模型,在古诺特模型中，产品是同质的。但在更多的实际问题中，不同的企业生产的产品是有差异的，替代弹性不会是无限的，此时消费者对不同的产品有不同的偏好。 考虑产品差异的一种特殊的情况，即空间上的差异,豪泰林模型,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,65,豪泰林价格竞争模型（续）,假定有一个长度为1的线性城市，消费者均匀地分布在0，1区间里，其分布函数的密度为1。假设有两个商店分别位于城市的两端，商店1位于处 ，商店2位于处 ，他们出售物质性能相同的产品。每个商店具有相同的单位产品成本为 。消费者购买商品的旅行成本与离商店的距离成正比例，单位距离的成本为 。所以住在的消费者如果去商店1去购买，要花费的旅行成本 ；如果去商店2去购买，要花费的旅行成本 。为方便讨论，再假定消费者都有单位的物质需求，即消费1个单位消费品。另外所有消费者都可能到两家商店购买，即他们都能获得消费剩余。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,66,豪泰林价格竞争模型（续）,模型的建立令 为商店的商品 的价格 ，商店 的出价，即是它的策略，因而商店 的策略集为 ， 。 商店的收益函数令 为需求函数， 。那么存在一点 ，住在 左边的消费者都将到商店1去购买，住在 右边的消费者都将到商店2去购买，我们说住在 处的消费者在两个商店之间是无差异的。这里 应该满足： （2.2.38）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,67,豪泰林价格竞争模型（续）,解（2.2.38）式得需求函数分别为： （2.2.39） （2.2.40） 两商店利润函数分别为： （2.2.41） （2.2.42）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,68,豪泰林价格竞争模型（续）,商店选择自己的价格 以最大化自己的利润。 求 并且令 ，有最优反应函数如下： （2.2.43） （2.2.44） （2.2.43）（2.2.44）式联立解方程组得： （2.2.45）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,69,豪泰林价格竞争模型（续）,即为纳什均衡点，对应的均衡结果，即每个商店的均衡利润为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,70,2.3 混合策略纳什均衡,2.3.1 混合策略纳什均衡 2.3.2 混合策略纳什均衡点的存在性定理 2.3.3 双矩阵博弈的纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,71,2.3.1 混合策略纳什均衡, 定义2.3.1 混合策略 混合策略下 人非合作博弈三要素 定义2.3.2混合策略纳什均衡点和均衡结果,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,72,混合策略的定义,对于每个 ，局中人 的纯策略集 。若局中人 对每一个纯策略 以 概率 进行选择，则 被称为局中人 的一个混合策略。其中 ， ， 。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,73,混合策略的定义,局中人 混合策略就是定义在其纯策略集 上的一个概率分布。 局中人 的混合策略集记为 ： （2.3.1） 记 为博弈 的一个混合策略组合。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,74,混合策略下 n 人非合作博弈三要素,(1)局中人的集 ； (2)每个局中人 有一个混合策略的集 其中 满足（2.3.1）； (3)每个局中人有一个支付函数 并设 是局中人 的支付函数 在混合策略局势 下得到的期望支付。 在混合策略的情形下，一个 人非合作博弈可以用下面的记号来表示：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,75,混合策略纳什均衡点和均衡结果,设 是 人非合作博弈 的一个混合策略局势。如果对于每一个 和每个 ，有 : ， ， （2.3.2） 则称 是 （在混合策略下）的一个混合策略纳什均衡点， 为对应的均衡结果。 为混合策略 下局中人 的期望收益。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,76,2.3.2 混合策略纳什均衡点的存在性定理,定理2.3.1 混合策略纳什均衡点的充分必要条件 定理2.3.2 混合策略纳什均衡点的存在性,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,77,定理2.3.1,设 是 人非合作博弈。 是 的一个混合策略纳什均衡点的充分必要条件是：对于每个局中人 和每个纯策略 ，有 。 （2.3.3） 这里 是将局中人 的混合策略 换成一个纯策略 后的期望支付。 定理2.3.1证明,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,78,定理2.3.1证明,必要性。显然成立。 充分性。设（2.3.3）式成立，即对于每个 有 ， （2.3.4） 设 是局中人 的任意一个混合策略。（2.3.4）中 个不等式两端依次乘以 ，得到 ， （2.3.5） 对 从1到 求和： （2.3.6） （2.3.6）式中的左端就是 ，右端的和式等于 1。 由此可知， 是 的混合策略纳什均衡。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,79,定理2.3.2,每个 人非合作博弈 必有混合策略纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,80,定理2.3.2证明,证明：设 是 的任意混合策略局势。对于每个 的每个纯策 ， ，定义 对于每个 ，定义,(2.3.7),(2.3.8),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,81,定理2.3.2证明(续),Brouwer 不动点定理：定义在有限维欧式空间紧凸集S上从S映入其本身的连续映射必有不动点。,易知， , 所以 是局 中人 的一个混合策略。 是 的连续函数，所以 是 的连续函数。根据 Brouwer 不动点定理，存在不动点 ， 其中 ，使得,(2.3.9),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,82,定理2.3.2证明(续),该不动点就是博弈 的混合策略纳什均衡的证明 首先，对于任意的混合策略局势 ，每个局中人 必有一个纯策略 ，使得 ，且 因此，对于 ，局中人 的策略 中必定包含一个 ，使得 ， 从而 。 由（2.3.7）有： 。,(2.3.10),博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,83,定理2.3.2证明(续),其中 。由此可得: 。 而由 的定义，所有的 都是非负的，所以从上式可知，对于每个 ， 。因此根据（2.3.7）式，有 ,即 。 上式对于每个 成立。由定理2.3.1可知， 是 的混合策略纳什均衡。,对于上述局中人 的策略 ，由（2.3.9）式有：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,84,2.3.3 双矩阵博弈的纳什均衡, 双矩阵博弈纳什均衡的求解 例2.3.1 含一个参数 的 双矩阵博弈 例2.3.2 小偷与守卫的博弈,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,85,双矩阵博弈纳什均衡的求解, 存在策略占优时纳什均衡的求解 不存在策略占优时纳什均衡的求解,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,86,存在策略占优时纳什均衡的求解,设双矩阵博弈局中人1，2的支付矩阵分别为 若 ， ，或 ， ，则局中人1有严格占优策略； 若 ， ，或 ， ，则局中人2有严格占优策略。 之后，采用重复剔除法，可得重复剔除占优均衡，同时求得纳什均衡。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,87,存在策略占优时纳什均衡的求解,若 ， ，则局中人1的两个策略无差异，即采用任何纯策略或任何混合策略都有相同的收益。 若 ， ，则局中人2的两个策略无差异，即采用任何纯策略或任何混合策略都有相同的收益。 这种情况没有讨论的意义。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,88,不存在策略占优时纳什均衡的求解,局中人1的支付矩阵A中，有： ，且至少有一个等式不成立；或 ，且至少有一个等式不成立。这时，若令 （2.3.11） 必有 ，且Q和q同号。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,89,不存在策略占优时纳什均衡的求解(续),局中人2的支付矩阵B中，有： ，且至少有一个等式不成立；或 ，且至少有一个等式不成立。这时，若令 （2.3.12） 必有 ，且R和r同号。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,90,不存在策略占优时纳什均衡的求解(续),此时令 分别表示局中人1和2的混合策略，其中 博弈的混合策略局势由一对数 确定。 分别表示局中人1，2在上述混合策略 下得到的期望支付。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,91,不存在策略占优时纳什均衡的求解(续),由定理2.3.1可知， 是博弈的平衡点的充要条件是 （2.3.13） （2.3.14） （2.3.15） （2.3.16）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,92,设双矩阵博弈局中人1，2的支付矩阵分别为： 设局中人1的混合策略为： 设局中人1的混合策略为： 简记混合策略组合为（ x, y ）。则局中人1的期望收益为：,不存在策略优超时纳什均衡的求解（续）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,93,（2.3.13）式为：,(2.3.14）式为：,不存在策略优超时纳什均衡的求解（续）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,94,不存在策略优超时纳什均衡的求解（续）,由于 ，因此（2.3.13），（2.3.14）式展开并化简后变为 （2.3.17） （2.3.18） 其中:,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,95,不存在策略优超时纳什均衡的求解（续）,由于 ，满足（2.3.17）和（2.3.18）式的应满足： （2.3.19）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,96,简记混合策略组合为（ x, y ）。则局中人2的期望收益为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,97,(2.3.15)式为： (2.3.16)式为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,98,不存在策略占优时纳什均衡的求解（续）,类似地，令 则（2.3.15），（2.3.16）简化为 （2.3.20） （2.3.21）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,99,不存在策略占优时纳什均衡的求解（续）,同样由于 ，满足（2.3.20）和（2.3.21）式的应满足 （2.3.22） 将（2.3.18）和（2.3.22）结合起来，就得到 双矩阵博弈在不存在占优策略情形下纳什均衡点，相应的计算 和 ，则可得到对应的纳什均衡结果。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,100,例2.3.1 一般双矩阵博弈,设双矩阵博弈中局中人1，2的支付矩阵分别为： 下面求该博弈的混合策略下的纳什均衡结果。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,101,例2.3.1 一般双矩阵博弈（续）,由：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,102,例2.3.1 一般双矩阵博弈（续）,两个不等式作图：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,103,例2.3.1 一般双矩阵博弈（续）,结论 有唯一点 满足两个不等式组。则该博弈的纳什均衡为 对应的均衡结果为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,104,例2.3.2 含一个参数a的 22双矩阵博弈,设双矩阵博弈局中人1，2的支付矩阵分别为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,105,例2.3.2含一个参数a的 22双矩阵博弈（续）,当 时，局中人1的第一个策略相对于第二策略是严格劣策略，局中人1会选择第二个策略。由于理智的局中人2同样可以分析出局中人1的这一选择，因此，他会选择第二个策略。此时博弈的纳什均衡点为（0，1），（0，1），均衡结果为（1，2）。 当 时，博弈中不存在占优策略，因此我们使用一般方法。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,106,例2.3.2（续）, 由 ， 得,图2.3.1 时的纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,107,例2.3.2（续）,该博弈有三个纳什均衡点： O：（(0，1)，(0，1)），W：（(1，0)，(1，0)）， M：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,108,例2.3.2（续）,其均衡结果分别是： 对第一个纳什均衡点O：（0，1），（0，1），均衡结果为（1，2） 对第二个纳什均衡点W：（1，0），（1，0），均衡结果为（a，1） 对第三个纳什均衡点M： 均衡结果为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,109,例2.3.2（续）,当 时， （2.3.25） 又 （2.3.26）,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,110,例2.3.2（续）,同样，将（2.3.25）和（2.3.26）分别作下图:,图2.3.2 时的纳什均衡,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,111,例2.3.1（续）,同时满足（2.3.25）和（2.3.26）的点对 为O点和线段MN，则此时纳什均衡为： 前一个的均衡结果为（1，2），后一类均衡为：,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,112,例2.3.3 小偷与守卫的博弈,由于对博弈论有卓越贡献而成为1994年诺贝尔经济学奖获得者的泽尔顿教授，1996年3月在上海的一次演讲中，举了这个小偷与守卫之间博弈的例子。故事的背景是这样的：一守卫看守一个仓库，一小偷要在夜晚去偷仓库的东西。但是守卫有可能晚上睡觉也可能不睡，如果守卫睡觉，小偷偷窃就会成功，他将获得正效用V，而守卫由于失职，他将获得负效用D；而守卫如果不睡，守卫能抓住小偷，小偷将获得负效用P；而小偷也有可能不去偷，那样守卫如果睡觉，他获得正效用S。,博弈论及其应用 （汪贤裕）,#,博弈论及其应用 （汪贤裕）,113,例2.3.3 小偷与守卫的博弈(续),守卫有睡和不睡两种策略选择，