博弈中纯策略纳什均衡点课件.ppt
《博弈中纯策略纳什均衡点课件.ppt》由会员分享,可在线阅读,更多相关《博弈中纯策略纳什均衡点课件.ppt(163页珍藏版)》请在三一办公上搜索。
1、博弈论及其应用,第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、食槽,但需要支付2个单位的劳动成本。在吃食的过程中,若大猪先到,大猪能吃7个单位的食料,小猪只能吃1个单位。若小猪先到,小猪能吃到4个单位的食料,大猪只能吃4个单位。若两只猪同时到,大猪吃5个单位,小猪吃3个单位的食料。大猪和小猪都有两个策略,按或等待。,博弈论及其应用(汪贤裕),6,智猪博弈(续),两只猪在不同策略下的支付矩阵:大猪和小猪分别采取什么样的策略,且各自的收益分别为多少?,博弈论及其应用(汪贤裕),7,夫妻爱好问题,OR,博弈论及其应用(汪贤裕),8,猜钱币游戏,博弈论及其应用(汪贤裕),9,完全信息静态博弈三要素,局中人集合 局中人集合即博弈参加人的集合。若给定局中人,则记 策
3、略集 每个局中人 有一个策略集Si,策略集Si,可以是有限集,也可以是无限集,当策略集是有限集时,我们记:当每个局中人 选定一个策略si 后,形成一个策略组合,并称为一个局势,记为:我们也引入如下记号:显然,也是一个局势,且。支付函数 每个局中人有一个支付函数。是局势 s 的函数,是局中人在局势下所能得到的收益。当然,每个局中人都希望自己的尽可能大。,完全信息静态博弈三要素,完全信息静态博弈就是在上述三要素的基础上,分 析各局中人为实现自身利益最大化的策略行为分析。简记为:,博弈论及其应用(汪贤裕),10,博弈论及其应用(汪贤裕),11,2.1.2 占优均衡,定义2.1.1 严格占优策略 定义
4、2.1.2 占优均衡 定义2.1.3 重复剔除占优均衡,博弈论及其应用(汪贤裕),12,定义2.1.1 严格占优策略,在博弈 中,若 和 是局中人 的两个策略,对任意策略组合 都有:(2.1.1)则称,局中人 的策略 严格占优策略,或称策略 相对于 是严格劣策略。囚徒困境中、犯罪嫌疑人A和B策略(承认)就是一个严格占优策略。,博弈论及其应用(汪贤裕),13,定义2.1.2 占优均衡,在博弈 中,若每一个局中人 都存在一个策略,使得 占优于 中任何策略,那么策略组合 称为 的占优策略均衡,简称占优均衡。对应的 称为占优均衡结果。,博弈论及其应用(汪贤裕),14,定义2.1.2 占优均衡(续),囚
5、徒困境中严格占优均衡:(承认,承认),博弈论及其应用(汪贤裕),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 纯
6、策略纳什均衡点和均衡结果 定理2.2.1 重复剔除占优均衡与纯策略纳什均衡 纳什均衡点与多目标规划求解比较,博弈论及其应用(汪贤裕),19,纯策略纳什均衡点和结果,定义2.2.1 在 人非合作博弈 中,若有策略组合,使得每一个,对任意 都有(2.2.1)则称 是 的一个纯策略纳什均衡点,对应的 称为对应的均衡结果。,博弈论及其应用(汪贤裕),20,纯策略纳什均衡点和结果,夫妻爱好博弈中纯策略纳什均衡点:(足球,看足球)&(看芭蕾,看芭蕾),博弈论及其应用(汪贤裕),21,纯策略纳什均衡点和结果(续),猜钱币游戏中不存在纯策略纳什均衡点。,博弈论及其应用(汪贤裕),22,定理2.2.1,在 人非
7、合作博弈 中:若,是重复剔除占优均衡,则 一定是纯策略纳什均衡点。,博弈论及其应用(汪贤裕),23,定理2.2.1的证明,证明:用反证法。若 是重复剔除占优均衡,但不是纯策略纳什均衡点。则有 和,使得(2.2.2)那么在局中人 在对 的剔除过程中应有对任意的策略组合 满足(2.2.1)式。这里策略组合当然也包括,即 因此(2.2.2)式是不可能出现的,即(2.2.2)式与剔除严格劣策略过程矛盾。从而定理2.2.1成立。,博弈论及其应用(汪贤裕),24,纳什均衡点与多目标规划求解比较,在n人非合作博弈 中,对每一个局中人,都在寻找自己的策略 使得自己的收益 最大,但是局中人 单方面不能找到自己的
8、最佳策略,其结果是相互影响的,是由策略组合 决定的。这就是一个有相互影响的多人决策问题。有人可能这样设想:是否有一个局外人,将 个局中人的收益最大作为 个目标的多目标规划问题,即求:(2.2.3)纳什均衡点和上面的(2.2.3)的多目标规划的求解是两个不同的概念。,博弈论及其应用(汪贤裕),25,纳什均衡点与多目标规划求解比较(续),囚犯困境是一个2人非合作博弈 两个局中人策略集 和支付 函数 都表示在表1.2.1中图2.2.1 囚犯困境中的局中人 收益图,以囚徒困境为例,博弈论及其应用(汪贤裕),26,纳什均衡点与多目标规划求解比较(续),各点代表不同策略组合下双方的收益:A点对应策略组合(
9、承认,承认)B点对应策略组合(承认,不承认)C点对应策略组合(不承认,不承认)D点对应策略组合(不承认,承认)B点、C点和D点所代表的策略组合 都是单人决策的多目标规划(2.2.3)中的非劣解。但策略组合(承认,承认)是唯一的纳什均衡点。,博弈论及其应用(汪贤裕),27,纳什均衡点与多目标规划求解比较(续),结论:(一)非合作博弈中的纳什均衡点,不可能用(2.2.3)表示的多目标规划作为替代,双方有不同的思想基础。(二)博弈论与多目标规划这类多人决策问题的差异,进一步显示出纳什均衡思想在博弈论中的重要地位。,博弈论及其应用(汪贤裕),28,2.2.2 双矩阵博弈的划线法,双矩阵博弈的定义 纯策
10、略纳什均衡的简单求解方法划线法 定理2.2.2 划线法与纯策略纳什均衡,博弈论及其应用(汪贤裕),29,双矩阵博弈的定义,在博弈中,若三要素的前两个要素满足:只有两个局中人,即;策略集有限,即,此类博弈我们称为双矩阵博弈。,双矩阵博弈称呼的由来(补充1),在双矩阵博弈中,对任意策略组合,记支付函数,将两个局中人的支付函数分别记为矩阵A和矩阵B如下:,博弈论及其应用(汪贤裕),30,博弈论及其应用(汪贤裕),31,双矩阵博弈称呼的由来(补充2),(2.2.4)回到:划线法 定理2.2.2,划线法,对局中人1,在(2.2.4)式 的每一行 中,找出对方支付矩阵B中该行的最大元素,即 并在 下划线。
11、当 不唯一时,均在下面划线。对局中人2,在(2.2.4)式每一列 中,找出对方支付矩阵A中该列的最大元素 即 并在 下划线。当 不唯一时,均在下面划线。,博弈论及其应用(汪贤裕),32,划线法(续),若存在一对,使得其两个元素 和 下面都有划线,则 是纯策略纳什均衡点,和 是对应的纳什均衡结果。(4)若不存在满足(3)的数对,则该博弈无纯策略纳什均衡。,博弈论及其应用(汪贤裕),33,博弈论及其应用(汪贤裕),34,定理2.2.2,在双矩阵博弈 中划线法的使用:(1)若 和 同时得到划线,则 一定是 的纯策略纳什均衡点。(2)若不存在能够同时得到划线的数对,则 无纯策略纳什均衡点。,博弈论及其
12、应用(汪贤裕),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,在博弈 中,若局中人 的策略
13、集 是有界闭区域,支付函数 对任意 都是 的拟凹连续函数,则博弈 一定存在有纯策略纳什均衡点。注:严格拟凹函数定义点击,博弈论及其应用(汪贤裕),38,严格拟凹函数定义,设 是凸集 上的函数,对任意 及任意,若有:(2.2.8)则 为 上的拟凹函数。若(2.2.8)式中不等号为严格不等号,则称 为 上的严格拟凹函数。,无限策略纳什均衡点的求解思路,当局中人 的收益函数 都是 上的连续可微严格拟凹函数时,每个局中人都有一个最优反映函数(点击)组成含 个未知数的 个方程的方程组:(2.2.11)求解(2.2.11)式得到博弈 的一个纯策略纳什均衡点 注:,博弈论及其应用(汪贤裕),39,博弈论及其
14、应用(汪贤裕),40,反应函数的定义和求解,设 是定义2.2.2规定下的拟凹函数,有:(2.2.9)称 为局中人 在 上最优的反应函数,反应函数的定义和求解,当 对任意 是 上的严格的拟凹函数时,即只有一个元素。这时,最优反应函数为:(2.2.10)若 在闭区间 上连续可微且对任意 是严格拟凹函数,则令 可得最优反应函数:,博弈论及其应用(汪贤裕),41,博弈论及其应用(汪贤裕),42,例2.2.2 古诺模型,设市场有1、2两个寡头厂商,生产并销售同一种产品。厂商1、2生产商品的数量分别为 和,他们有不同的不变边际成本,分别为 和,无固定成本。市场的逆需求函数为 一个正常数,即该产品的市场最高
15、价格且。市场需求情况和两厂商的成本和收益确定都是共同知识。两个厂商事前没有任何协议和约定,同时分别决定生产的产量,以追求市场的最大利润(设厂商的生产产量没有限制,但)。,例2.2.2 古诺模型(续),该博弈中局中人为两个厂商,生产数量是他们的策略,即。厂商各自的利润函数:(2.2.12)(2.2.13)由(2.2.12)和(2.2.13)式可知,对任何 都是 的严格连续凹函数,对任何 都是 的严格连续凹函数。,博弈论及其应用(汪贤裕),43,博弈论及其应用(汪贤裕),44,例2.2.2 古诺模型(续),两个厂商都来确定产量以追求最大利润可以表示成:求 和,并且令 和 有:(2.2.14)(2.
16、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也是同样的,要满足边际成本等于边
17、际利润,其产量 与对方的生产产量必须满足(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 古诺模型(续),该多目标规划的非
18、劣解由下图所示的直线段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 古诺模型(续),
19、多目标规划(2.2.18)的任何满意解都是依一定的法则在非劣解中寻求满意解。而此时古诺模型的纳什均衡为:,对应的收益为图2.2.3的C点,即两厂商的收益分别是。纳什均衡点 是多目标规划(2.2.18)中的劣解。,博弈论及其应用(汪贤裕),53,例2.2.2 古诺模型(续),结论 在策略集为无限时,纳什均衡点仍然不是多目标规划中的非劣解。纳什均衡与多目标规划存在不同,是不可混淆的。造成这种差别的原因在于,纳什均衡是多人决策,而多目标规划是单人决策。博弈论的一个最显著特征:竞争环境下的多人决策。,博弈论及其应用(汪贤裕),54,伯川德双寡头垄断模型,考虑市场上有两个寡头厂商生产同一类型产品。厂商1
20、和厂商2分别选择价格 和。消费者对企业的产品的需求为:其中0b1,即只限于企业 的产品和企业 产品具有相互替代的情况。企业生产没有固定成本,并且边际成本为常数,。两个企业同时进行价格选择行动。另外企业 的策略 是所选价格,也即每个企业的策略集。,伯川德双寡头垄断模型(续),企业 选择价格,对手 选择价格,企业的利润为:(2.2.20)对于企业1来说,若企业2选定的价格为,它确定自己的价格 以追求最大利润 对企业1求 并且令 解得:(2.2.21),博弈论及其应用(汪贤裕),55,博弈论及其应用(汪贤裕),56,伯川德双寡头垄断模型(续),同理,可得企业2的最优价格(2.2.22)联立(2.2.
21、21)(2.2.22)解方程组得:(2.2.23)均衡结果为:(2.2.24),博弈论及其应用(汪贤裕),57,例2.2.4 公共地的悲剧,考虑有相同情况的 个牧民组成的某个牧民村,他们共同拥有一片草地。每年所有的牧民都会在共同的草地上放牧养羊。用 表示牧民 养羊的头数,则牧民村的养羊总头数为。购买羊崽和照看一只羊的成本为c,c不随某一牧民拥有羊的树目的多少而变化。当草地上的羊的总头数为 时,牧民养的一只羊的价值为,设。当草地上羊的总头数 较少时,每只羊有相对较多的空间,每只羊能吃到的草也丰盛些。而羊的总数 增加时,则正好相反,每只羊相对能吃到的草相对较少。并有当羊群总数 达到一个极限 时,再
22、增加一只羊将对已经牧养的羊带来损害。对一只羊的价值 的上述特征用公式表示,则为:,。,(2.2.25),博弈论及其应用(汪贤裕),58,例2.2.4 公共地的悲剧(续),每年春天,个牧民同时分别选择牧养羊的数量。假设其是连续的可分割的。牧民 的策略是选择在公共草地上牧养羊的数量,并有策略集。当其他村民养羊数为 时,牧民 牧养 只羊获得的收益为:现在要讨论的问题是:牧民 如何决定自己的牧养羊数,以获得自己的最大收益。,(2.2.26),博弈论及其应用(汪贤裕),59,例2.2.4 公共地的悲剧(续),这构成了一个 人非合作博弈的问题,需要求平衡局势,即纳什均衡。很明显,在任何 时,都是 的凹函数
23、。计算 并且令,得到:当 是一个已知函数时,求解由上式给出的 个方程和 个未知数,可以求得该体系的纯策略纳什均衡点,即平衡局势 再代回到(2.2.26)式,则有纳什均衡结果。,(2.2.27),博弈论及其应用(汪贤裕),60,例2.2.4 公共地的悲剧(续),公共地的悲剧的意义 将上面的 人非合作博弈的牧养羊纳什均衡结果与草地在非公共地的情况下,即由社会计划管理者进行管理作对比研究。在 个牧民分散独立决策牧养羊情况下,设 是第 个牧民的养羊数 最优决策,。由于 个牧民是相同情况,则:令,则由(2.2.27)式得:再将(2.2.28)的 个方程加总,有:,(2.2.29),(2.2.28),博弈
24、论及其应用(汪贤裕),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.
25、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 豪泰林价格
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 博弈 策略 均衡 课件
链接地址:https://www.31ppt.com/p-3805383.html