博弈中纯策略纳什均衡点课件.ppt

博弈论及其应用,第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,双矩阵博弈的定义,在博弈中，若三要素的前两个要素满足：只有两个局中人，即;策略集有限，即，此类博弈我们称为双矩阵博弈。,双矩阵博弈称呼的由来（补充1）,在双矩阵博弈中，对任意策略组合，记支付函数，将两个局中人的支付函数分别记为矩阵A和矩阵B如下：,博弈论及其应用（汪贤裕）,30,博弈论及其应用（汪贤裕）,31,双矩阵博弈称呼的由来（补充2）,（2.2.4）回到：划线法 定理2.2.2,划线法,对局中人1，在（2.2.4）式 的每一行 中，找出对方支付矩阵B中该行的最大元素,即 并在 下划线。当 不唯一时，均在下面划线。对局中人2，在（2.2.4）式每一列 中，找出对方支付矩阵A中该列的最大元素 即 并在 下划线。当 不唯一时，均在下面划线。,博弈论及其应用（汪贤裕）,32,划线法(续),若存在一对，使得其两个元素 和 下面都有划线，则 是纯策略纳什均衡点，和 是对应的纳什均衡结果。(4)若不存在满足（3）的数对，则该博弈无纯策略纳什均衡。,博弈论及其应用（汪贤裕）,33,博弈论及其应用（汪贤裕）,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）式中不等号为严格不等号，则称 为 上的严格拟凹函数。,无限策略纳什均衡点的求解思路,当局中人 的收益函数 都是 上的连续可微严格拟凹函数时，每个局中人都有一个最优反映函数（点击）组成含 个未知数的 个方程的方程组：（2.2.11）求解（2.2.11）式得到博弈 的一个纯策略纳什均衡点 注：,博弈论及其应用（汪贤裕）,39,博弈论及其应用（汪贤裕）,40,反应函数的定义和求解,设 是定义2.2.2规定下的拟凹函数，有：（2.2.9）称 为局中人 在 上最优的反应函数,反应函数的定义和求解,当 对任意 是 上的严格的拟凹函数时，即只有一个元素。这时，最优反应函数为:（2.2.10）若 在闭区间 上连续可微且对任意 是严格拟凹函数，则令 可得最优反应函数：,博弈论及其应用（汪贤裕）,41,博弈论及其应用（汪贤裕）,42,例2.2.2 古诺模型,设市场有1、2两个寡头厂商，生产并销售同一种产品。厂商1、2生产商品的数量分别为 和，他们有不同的不变边际成本，分别为 和，无固定成本。市场的逆需求函数为 一个正常数，即该产品的市场最高价格且。市场需求情况和两厂商的成本和收益确定都是共同知识。两个厂商事前没有任何协议和约定，同时分别决定生产的产量，以追求市场的最大利润（设厂商的生产产量没有限制，但）。,例2.2.2 古诺模型(续),该博弈中局中人为两个厂商，生产数量是他们的策略，即。厂商各自的利润函数：（2.2.12）（2.2.13）由（2.2.12）和（2.2.13）式可知，对任何 都是 的严格连续凹函数，对任何 都是 的严格连续凹函数。,博弈论及其应用（汪贤裕）,43,博弈论及其应用（汪贤裕）,44,例2.2.2 古诺模型（续）,两个厂商都来确定产量以追求最大利润可以表示成：求 和，并且令 和 有：（2.2.14）（2.2.15）,例2.2.2 古诺模型（续）,求解最优反应函数（2.2.14）和（2.2.15）组成的方程组：（2.2.16）（2.2.17）组成该博弈的平衡局势，即纯策略纳什均衡点。均衡结果，分别为：。,博弈论及其应用（汪贤裕）,45,博弈论及其应用（汪贤裕）,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，即只限于企业 的产品和企业 产品具有相互替代的情况。企业生产没有固定成本，并且边际成本为常数，。两个企业同时进行价格选择行动。另外企业 的策略 是所选价格，也即每个企业的策略集。,伯川德双寡头垄断模型（续）,企业 选择价格，对手 选择价格，企业的利润为：（2.2.20）对于企业1来说，若企业2选定的价格为，它确定自己的价格 以追求最大利润 对企业1求 并且令 解得：（2.2.21）,博弈论及其应用（汪贤裕）,55,博弈论及其应用（汪贤裕）,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 豪泰林价格竞争模型,在古诺特模型中，产品是同质的。但在更多的实际问题中，不同的企业生产的产品是有差异的，替代弹性不会是无限的，此时消费者对不同的产品有不同的偏好。考虑产品差异的一种特殊的情况，即空间上的差异,豪泰林模型,豪泰林价格竞争模型（续）,假定有一个长度为1的线性城市，消费者均匀地分布在0，1区间里，其分布函数的密度为1。假设有两个商店分别位于城市的两端，商店1位于处，商店2位于处，他们出售物质性能相同的产品。每个商店具有相同的单位产品成本为。消费者购买商品的旅行成本与离商店的距离成正比例，单位距离的成本为。所以住在的消费者如果去商店1去购买，要花费的旅行成本；如果去商店2去购买，要花费的旅行成本。为方便讨论，再假定消费者都有单位的物质需求，即消费1个单位消费品。另外所有消费者都可能到两家商店购买，即他们都能获得消费剩余。,博弈论及其应用（汪贤裕）,65,豪泰林价格竞争模型（续）,模型的建立令 为商店的商品 的价格，商店 的出价，即是它的策略，因而商店 的策略集为，。商店的收益函数令 为需求函数，。那么存在一点，住在 左边的消费者都将到商店1去购买，住在 右边的消费者都将到商店2去购买，我们说住在 处的消费者在两个商店之间是无差异的。这里 应该满足：（2.2.38）,博弈论及其应用（汪贤裕）,66,博弈论及其应用（汪贤裕）,67,豪泰林价格竞争模型（续）,解（2.2.38）式得需求函数分别为：（2.2.39）（2.2.40）两商店利润函数分别为：（2.2.41）（2.2.42）,豪泰林价格竞争模型（续）,商店选择自己的价格 以最大化自己的利润。求 并且令，有最优反应函数如下：（2.2.43）（2.2.44）（2.2.43）（2.2.44）式联立解方程组得：（2.2.45）,博弈论及其应用（汪贤裕）,68,博弈论及其应用（汪贤裕）,69,豪泰林价格竞争模型（续）,即为纳什均衡点，对应的均衡结果，即每个商店的均衡利润为：,博弈论及其应用（汪贤裕）,70,2.3 混合策略纳什均衡,2.3.1 混合策略纳什均衡 2.3.2 混合策略纳什均衡点的存在性定理 2.3.3 双矩阵博弈的纳什均衡,博弈论及其应用（汪贤裕）,71,2.3.1 混合策略纳什均衡,定义2.3.1 混合策略 混合策略下 人非合作博弈三要素 定义2.3.2混合策略纳什均衡点和均衡结果,博弈论及其应用（汪贤裕）,72,混合策略的定义,对于每个，局中人 的纯策略集。若局中人 对每一个纯策略 以 概率 进行选择，则 被称为局中人 的一个混合策略。其中，。,混合策略的定义,局中人 混合策略就是定义在其纯策略集 上的一个概率分布。局中人 的混合策略集记为：（2.3.1）记 为博弈 的一个混合策略组合。,博弈论及其应用（汪贤裕）,73,博弈论及其应用（汪贤裕）,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),定理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有严格占优策略。之后，采用重复剔除法，可得重复剔除占优均衡，同时求得纳什均衡。,存在策略占优时纳什均衡的求解,若，则局中人1的两个策略无差异，即采用任何纯策略或任何混合策略都有相同的收益。若，则局中人2的两个策略无差异，即采用任何纯策略或任何混合策略都有相同的收益。这种情况没有讨论的意义。,博弈论及其应用（汪贤裕）,87,不存在策略占优时纳什均衡的求解,局中人1的支付矩阵A中，有：，且至少有一个等式不成立；或，且至少有一个等式不成立。这时，若令（2.3.11）必有，且Q和q同号。,博弈论及其应用（汪贤裕）,88,不存在策略占优时纳什均衡的求解(续),局中人2的支付矩阵B中，有：，且至少有一个等式不成立；或，且至少有一个等式不成立。这时，若令（2.3.12）必有，且R和r同号。,博弈论及其应用（汪贤裕）,89,不存在策略占优时纳什均衡的求解(续),此时令 分别表示局中人1和2的混合策略，其中 博弈的混合策略局势由一对数 确定。分别表示局中人1，2在上述混合策略 下得到的期望支付。,博弈论及其应用（汪贤裕）,90,不存在策略占优时纳什均衡的求解(续),由定理2.3.1可知，是博弈的平衡点的充要条件是（2.3.13）（2.3.14）（2.3.15）（2.3.16）,博弈论及其应用（汪贤裕）,91,设双矩阵博弈局中人1，2的支付矩阵分别为：设局中人1的混合策略为：设局中人1的混合策略为：简记混合策略组合为（x,y）。则局中人1的期望收益为：,不存在策略优超时纳什均衡的求解（续）,博弈论及其应用（汪贤裕）,92,博弈论及其应用（汪贤裕）,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）,不存在策略占优时纳什均衡的求解（续）,同样由于，满足（2.3.20）和（2.3.21）式的应满足（2.3.22）将（2.3.18）和（2.3.22）结合起来，就得到 双矩阵博弈在不存在占优策略情形下纳什均衡点，相应的计算 和，则可得到对应的纳什均衡结果。,博弈论及其应用（汪贤裕）,99,博弈论及其应用（汪贤裕）,100,例2.3.1 一般双矩阵博弈,设双矩阵博弈中局中人1，2的支付矩阵分别为：下面求该博弈的混合策略下的纳什均衡结果。,博弈论及其应用（汪贤裕）,101,例2.3.1 一般双矩阵博弈（续）,由：,博弈论及其应用（汪贤裕）,102,例2.3.1 一般双矩阵博弈（续）,两个不等式作图：,博弈论及其应用（汪贤裕）,103,例2.3.1 一般双矩阵博弈（续）,结论有唯一点 满足两个不等式组。则该博弈的纳什均衡为对应的均衡结果为：,例2.3.2 含一个参数a的 22双矩阵博弈,设双矩阵博弈局中人1，2的支付矩阵分别为：,博弈论及其应用（汪贤裕）,104,博弈论及其应用（汪贤裕）,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 小偷与守卫的博弈(续),守卫有睡和不睡两种策略选择，小偷也有偷和不偷两种策略选择，各自收益矩阵如下：表2.3.1 小偷与守卫的收益矩阵 不存在占优策略,博弈论及其应用（汪贤裕）,114,小偷与守卫的博弈（续）,由 得（2.3.27）由 得（2.3.28）,图2.3.3 小偷与守卫的纳什均衡点,博弈论及其应用（汪贤裕）,115,小偷与守卫的博弈（续）,混合策略的纳什均衡点 小偷将以 的概率偷，以 的概率不偷；守卫以 的概率去睡觉，以 的概率不睡觉。,博弈论及其应用（汪贤裕）,116,2.4 矩阵博弈,2.4.1 矩阵博弈 2.4.2 保守策略与纳什均衡 2.4.3 混合策略纳什均衡 2.4.4 矩阵博弈的求解,博弈论及其应用（汪贤裕）,117,2.4.1 矩阵博弈,定义2.4.1 矩阵博弈 矩阵博弈保守支付值寻求的思路 定理2.4.1 两个保守支付值的关系,博弈论及其应用（汪贤裕）,118,定义2.4.1 矩阵博弈,对于博弈 的三要素中，满足下列三条件的称为矩阵博弈。局中人集；局中人1有有限个策略组成的策略集，局中人2有有限个策略组成的策略集；任取，任取，则 构成一个策略组合。对于一个策略组合，局中人1的支付为，局中人2的支付为，且满足：，。,定义2.4.1 矩阵博弈(续),由于两个局中人的策略数都是有限的，并且对任意策略组合 两人的支付的和为0，则矩阵博弈又称为二人有限零和博弈。,二人有限零和博弈,博弈论及其应用（汪贤裕）,119,博弈论及其应用（汪贤裕）,120,矩阵博弈保守支付值寻求的思路,一般地，如果局中人1采用他的第 个策略，则局中人1至少可以得到支付为，这就是支付矩阵第 行元素中的最小元素。由于局中人1希望所得到越大越好，因此，他可以选择 使上式为最大。这就是说，局中人1可以选择，使他得到的支付不少于（2.4.1）,矩阵博弈保守支付值寻求的思路,同样，如果局中人2采用他的第 个策略，由于局中人1希望支付值越大越好，则局中人2至多失去 这是支付矩阵第列的最大元素。由于局中人2希望支付值越小越好，因此，他可以选择使上式为最小。这就是说，局中人2可以选择，保证他失去的不大于（2.4.2）也可以说，如果局中人2处理得当，局中人1得到的支付不会大于（2.4.2）中的值。,博弈论及其应用（汪贤裕）,121,定理2.4.1 两个保守支付值的关系,矩阵博弈A中，则：（2.4.3）定理2.4.1证明,博弈论及其应用（汪贤裕）,122,博弈论及其应用（汪贤裕）,123,定理2.4.1证明,对于每一个，有 对于每一个，有 因此，对于任意的 和任意的，有 上式不等号右边对任意 都成立，则有 上式不等号左边对任意都成立，则有 以上就是需证的（2.4.3）式。,博弈论及其应用（汪贤裕）,124,2.4.2 保守策略与纳什均衡,定义2.4.2 保守策略集 例2.4.1 定理2.4.2 纯策略纳什均衡点存在的充分必要条件 例2.4.2,博弈论及其应用（汪贤裕）,125,保守策略集的定义,在矩阵博弈A中，令：（2.4.4）（2.4.5）则 和 分别为局中人1和2的保守策略集。,博弈论及其应用（汪贤裕）,126,例2.4.1,有矩阵博弈 保守策略的计算过程如表.则,例2.4.1（续）,很显然，矩阵博弈中，局中人的保守策略一定存在，但局中人采取保守策略集中的策略组合，不能实现博弈的稳定和均衡。如例2.4.1中，当局中人1取保守策略，局中人2取保守策略 就对局中人1不利。,博弈论及其应用（汪贤裕）,127,博弈论及其应用（汪贤裕）,128,矩阵博弈的纯策略纳什均衡,由定义2.2.1，矩阵博弈的纯策略纳什均衡是指满足下式的策略组合：（2.4.6）与一般博弈一样，矩阵博弈的纯策略纳什均衡点可能不存在，例如上例2.4.1。,博弈论及其应用（汪贤裕）,129,定理 2.4.2,矩阵博弈中，纯策略纳什均衡点存在的充分必要条件为：（2.4.7）定理的证明,博弈论及其应用（汪贤裕）,130,定理2.4.2的证明,充分性：若（2.4.7）式成立，即。必有一个 和，使 和 所以 但 于是有。因此，对一切 和一切，有（2.4.6）式成立,博弈论及其应用（汪贤裕）,131,定理2.4.2的证明（续）,必要性：设 是博弈的纳什均衡点，则对于一切 和 都有（2.4.8）由（2.4.8）式左边的不等式有 因而（2.4.9）同理，由（2.4.8）式右边的不等式有（2.4.10）由，（2.4.9）和（2.4.10）式得到由定理2.4.1反方向的不等式成立，因此。,博弈论及其应用（汪贤裕）,132,例2.4.2,有下列矩阵博弈 则纯策略纳什均衡为。同时保守策略为,博弈论及其应用（汪贤裕）,133,小结,在任意一个n人非合作博弈中，每个局中人都可以定义自身的保守策略和对应的保守策略下的收益。但由各局中人的保守策略组成的策略组合一般是无稳定性的，因此也不是博弈论中讨论的重点，但在有的情况中保守策略仍是有用的。例如在4.3中，谈判解的初始点可以用保守策略下的收益来确定，详见（4.3.1）和（4.3.2）式。,博弈论及其应用（汪贤裕）,134,2.4.3 混合策略纳什均衡,定理2.4.3 混合策略纳什均衡点存在的充分必要条件 定理2.4.4 不同纳什均衡点的均衡结果相同 定义2.4.3 博弈的值 定理2.4.5 矩阵博弈混合策略博弈的值,博弈论及其应用（汪贤裕）,135,定理2.4.3,矩阵博弈A中，混合策略纳什均衡点存在的充分必要条件为：,博弈论及其应用（汪贤裕）,136,定理2.4.4,在矩阵博弈A中，设 和 分别都 是纳什均衡点，则。定理2.4.4的证明,博弈论及其应用（汪贤裕）,137,定理2.4.4的证明,由于 和 分别都是矩阵A的纳什均衡，则由（2.4.12）式，得（2.4.14）（2.4.15）所以（2.4.16）式中，第一个不等号来自（2.4.14）中后一个不等号，第二个不等号来自（2.4.15）中前一个不等号，第三个不等号来自（2.4.15）中后一个不等号，第四个不等号来自（2.4.14）中前一个不等号。由（2.4.16）式，显然