纳什均衡四川大学.pptx
《纳什均衡四川大学.pptx》由会员分享,可在线阅读,更多相关《纳什均衡四川大学.pptx(163页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)2主要内容:主要内容:2.1 基本概念基本概念 2.2 纳什均衡纳什均衡 2.3 混合策略纳什均衡混合策略纳什均衡 2.4 矩阵博弈矩阵博弈第2章 纳什均衡第1页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)32.1 基本概念 基本概念基本概念 占优均衡占优均衡 第2页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)4基本概念 例智猪博弈例智猪博弈 例夫妻爱好问题例夫妻爱好问题 例猜钱币游戏例猜钱币游戏 完全信息静态博弈的三个基本要素完全信息静
2、态博弈的三个基本要素 第3页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)5智猪博弈 猪圈里有两头猪,一头大猪,一头小猪。猪猪圈里有两头猪,一头大猪,一头小猪。猪圈的一边有一个食槽,另一边安装一个控制圈的一边有一个食槽,另一边安装一个控制按钮,它能控制食料的供应。按一下按钮有按钮,它能控制食料的供应。按一下按钮有8个单位的食料进入猪食槽,但需要支付个单位的食料进入猪食槽,但需要支付2个个单位的劳动成本。在吃食的过程中,若大猪单位的劳动成本。在吃食的过程中,若大猪先到,大猪能吃先到,大猪能吃7个单位的食料,小猪只能个单位的食料,小猪只能吃吃1个单位。若小猪
3、先到,小猪能吃到个单位。若小猪先到,小猪能吃到4个单个单位的食料,大猪只能吃位的食料,大猪只能吃4个单位。若两只猪个单位。若两只猪同时到,大猪吃同时到,大猪吃5个单位,小猪吃个单位,小猪吃3个单位的个单位的食料。大猪和小猪都有两个策略,按或等待。食料。大猪和小猪都有两个策略,按或等待。第4页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)6智猪博弈(续)两只猪在不同策略下的支付矩阵:两只猪在不同策略下的支付矩阵:大猪和小猪分别采取什么样的策略,且各自的收益分别为多少大猪和小猪分别采取什么样的策略,且各自的收益分别为多少?第5页/共163页博弈论及其应用(汪
4、贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)7夫妻爱好问题 OR第6页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)8猜钱币游戏 第7页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)9完全信息静态博弈三要素 局中人集合局中人集合 局中人集合即博弈参加人的集合。若给定局中人局中人集合即博弈参加人的集合。若给定局中人 ,则记,则记 策略集策略集 每个局中人每个局中人 有一个策略集有一个策略集Si,策略集,策略集Si,可以是有限集,也可以是有限集,也可以是无限集,当策略集是有限集时,我们记:可以是无限集,当策
5、略集是有限集时,我们记:当每个局中人当每个局中人 选定一个策略选定一个策略si 后,形成一个策略组合后,形成一个策略组合 ,并称为一个,并称为一个局势,记为:局势,记为:我们也引入如下记号:我们也引入如下记号:显然,显然,也是一个局势,且也是一个局势,且 。支付函数支付函数 每个局中人有一个支付函数。是局势每个局中人有一个支付函数。是局势 s 的函数,是局中人在局势下所能的函数,是局中人在局势下所能得到的收益。当然,每个局中人都希望自己的尽可能大。得到的收益。当然,每个局中人都希望自己的尽可能大。第8页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)10完
6、全信息静态博弈三要素 完全信息静态博弈就是在上述三要素的基础上,分完全信息静态博弈就是在上述三要素的基础上,分 析各局中人为实现自身利益最大化的策略行为分析。析各局中人为实现自身利益最大化的策略行为分析。简记为简记为:第9页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)11占优均衡 定义严格占优策略定义严格占优策略 定义占优均衡定义占优均衡 定义重复剔除占优均衡定义重复剔除占优均衡 第10页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)12定义严格占优策略 在博弈在博弈 中,若中,若 和和 是局中人是局中人 的的两
7、个策略,对任意策略组合两个策略,对任意策略组合 都有:都有:()()则称,局中人则称,局中人 的策略的策略 严格占优策略严格占优策略 ,或称策略,或称策略 相对于相对于 是是严格劣策略严格劣策略。囚徒困境囚徒困境中、中、犯罪嫌疑人A和B策略(承认)就是一策略(承认)就是一个严格占优策略。个严格占优策略。第11页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)13定义占优均衡 在博弈在博弈 中,若每一个局中人中,若每一个局中人 都存在一个策略都存在一个策略 ,使得,使得 占优于占优于 中任何策略,那么策略组合中任何策略,那么策略组合 称为称为 的占优策略均衡
8、,简称的占优策略均衡,简称占优均衡占优均衡。对应的。对应的 称为称为占优均衡结果占优均衡结果。第12页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)14定义占优均衡(续)囚徒困境囚徒困境中严格占优均衡:中严格占优均衡:(承认,承认)(承认,承认)均衡结果第13页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)15定义重复剔除占优均衡 在博弈在博弈 中,经过重复剔出严格劣策略后,每个局中人中,经过重复剔出严格劣策略后,每个局中人 只剩下一个唯一只剩下一个唯一的策略:的策略:那么,策略组合那么,策略组合 称为博弈称为博弈
9、 的的重复剔除占优均衡。重复剔除占优均衡。对应对应 称为称为 的的重复剔除占优均衡结果重复剔除占优均衡结果。第14页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)16定义重复剔除占优均衡(续)智猪博弈智猪博弈中重复剔除占优均衡中重复剔除占优均衡:(按,不按)均衡结果第15页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)172.2 纳什均衡 纯策略纳什均衡纯策略纳什均衡 双矩阵博弈的划线法双矩阵博弈的划线法 无限策略的纯策略纳什均衡无限策略的纯策略纳什均衡第16页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博
10、弈论及其应用(汪贤裕)(汪贤裕)18纯策略纳什均衡 定义纯策略纳什均衡点和均衡结果定义纯策略纳什均衡点和均衡结果 定理重复剔除占优均衡与纯策略纳什均衡定理重复剔除占优均衡与纯策略纳什均衡 纳什均衡点与多目标规划求解比较第17页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)19纯策略纳什均衡点和结果 定义定义 在在 人非合作博弈人非合作博弈 中,若有策略组合中,若有策略组合 ,使得每一个,使得每一个 ,对任意,对任意 都有都有 ()()则称则称 是是 的一个的一个纯策略纳什均衡点纯策略纳什均衡点,对,对应的应的 称为对应的称为对应的均衡结果。均衡结果。第1
11、8页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)20纯策略纳什均衡点和结果夫妻爱好博弈中纯策略纳什均衡点:(足球,看足球)&(看芭蕾,看芭蕾)均衡结果均衡结果第19页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)21纯策略纳什均衡点和结果(续)猜钱币游戏中不存在纯策略纳什均衡点。第20页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)22定理 在在 人非合作博弈人非合作博弈 中:中:若,若,是是重复剔除占优均衡重复剔除占优均衡,则则 一定是一定是纯策略纳什均衡点纯策略纳什均衡
12、点。第21页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)23定理的证明证明:证明:用用反证法反证法。若若 是重复剔除占优均衡,但不是纯策略纳什均衡点。是重复剔除占优均衡,但不是纯策略纳什均衡点。则有则有 和和 ,使得使得 ()()那么在局中人那么在局中人 在对在对 的剔除过程中应有对任意的策略组合的剔除过程中应有对任意的策略组合 满足满足()式。这里策略组合当然也包括()式。这里策略组合当然也包括 ,即,即 因此()式是不可能出现的,即()式与剔除严格劣策略过程矛盾。因此()式是不可能出现的,即()式与剔除严格劣策略过程矛盾。从而定理成立。从而定理成立
13、。第22页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)24纳什均衡点与多目标规划求解比较在在n人非合作博弈人非合作博弈 中,对每一个局中人中,对每一个局中人 ,都在寻找自己的策略,都在寻找自己的策略 使得自己的收益使得自己的收益 最大,但是局中人最大,但是局中人 单方面不能找到自己的最佳策略,其结单方面不能找到自己的最佳策略,其结果是相互影响的,是由策略组合果是相互影响的,是由策略组合 决定的。决定的。这就是一个有相互影响的多人决策问题。有人可能这样设想:这就是一个有相互影响的多人决策问题。有人可能这样设想:是否有一个局外人,将是否有一个局外人,将 个
14、局中人的收益最大作为个局中人的收益最大作为 个目标个目标的的多目标规划问题多目标规划问题,即求:,即求:()()纳什均衡点和上面的()的多目标规划的求解是两个不同的纳什均衡点和上面的()的多目标规划的求解是两个不同的概念。概念。第23页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)25纳什均衡点与多目标规划求解比较(续)囚犯困境是一个囚犯困境是一个2人非合作博弈人非合作博弈 两个局中人策略集两个局中人策略集 和支付和支付 函数函数 都表示在表中都表示在表中图囚犯困境中的局中人图囚犯困境中的局中人 收益图收益图以囚徒困境为例以囚徒困境为例第24页/共163
15、页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)26纳什均衡点与多目标规划求解比较(续)各点代表不同策略组合下双方的收益:A点对应策略组合(承认,承认)B点对应策略组合(承认,不承认)C点对应策略组合(不承认,不承认)D点对应策略组合(不承认,承认)B点、C点和D点所代表的策略组合 都是单人决策的多目标规划()中的非劣解。但策略组合(承认,承认)是唯一的纳什均衡点。第25页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)27纳什均衡点与多目标规划求解比较(续)结论:结论:(一)非合作博弈中的纳什均衡点,不可能用()表示的多目标规
16、划作为替代,双方有(一)非合作博弈中的纳什均衡点,不可能用()表示的多目标规划作为替代,双方有不同的思想基础。不同的思想基础。(二)博弈论与多目标规划这类多人决策问题的差异,进一步显示出纳什均衡思想在博(二)博弈论与多目标规划这类多人决策问题的差异,进一步显示出纳什均衡思想在博弈论中的重要地位。弈论中的重要地位。第26页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)28双矩阵博弈的划线法 双矩阵博弈的定义双矩阵博弈的定义 纯策略纳什均衡的简单求解方法纯策略纳什均衡的简单求解方法划线法划线法 定理划线法与纯策略纳什均衡定理划线法与纯策略纳什均衡第27页/共
17、163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)29双矩阵博弈的定义在博弈中,若三要素的前两个要素满足:在博弈中,若三要素的前两个要素满足:只有只有两个局中人两个局中人,即,即 ;策略集有限策略集有限,即,即 ,此类博弈我们称为此类博弈我们称为双矩阵博弈双矩阵博弈。第28页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)30双矩阵博弈称呼的由来(补充1)在双矩阵博弈中,对任意策略组合在双矩阵博弈中,对任意策略组合 ,记支付函数,记支付函数 ,将两个局中人的支付函数分别记为矩阵,将两个局中人的支付函数分别记为矩阵A和矩阵和矩
18、阵B如下:如下:第29页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)31双矩阵博弈称呼的由来(补充2)()回到:划线法 定理第30页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)32划线法 (1)对局中人对局中人1,在()式,在()式 的每一行的每一行 中,找出对中,找出对方支付矩阵方支付矩阵B中该行的最大元素中该行的最大元素 ,即 并在并在 下划线。当下划线。当 不唯一时,均在下面划线。不唯一时,均在下面划线。(2)对局中人对局中人2,在()式每一列,在()式每一列 中,找出对方支付矩阵中,找出对方支付矩阵A中
19、该列的最大元素中该列的最大元素 即即 并在并在 下划线。当下划线。当 不唯一时,均在下面划线。不唯一时,均在下面划线。第31页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)33划线法(续)(3)若存在一对若存在一对 ,使得其两个元素,使得其两个元素 和和 下面都有划线,则下面都有划线,则 是纯策略纳什均衡点,是纯策略纳什均衡点,和和 是对应的纳什均衡是对应的纳什均衡结果。结果。(4)若不存在满足(若不存在满足(3)的数对,则该博弈无纯策略纳什均衡。)的数对,则该博弈无纯策略纳什均衡。第32页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应
20、用(汪贤裕)(汪贤裕)34定理 在双矩阵博弈在双矩阵博弈 中划线法的使用:中划线法的使用:(1)若若 和和 同时得到划线,则同时得到划线,则 一定一定是是 的纯策略纳什均衡点。的纯策略纳什均衡点。(2)若不存在能够同时得到划线的数对,则若不存在能够同时得到划线的数对,则 无无纯策略纳什均衡点。纯策略纳什均衡点。第33页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)35定理的证明设设 和和 都得到划线,则下面两式同时成立:都得到划线,则下面两式同时成立:()()()()是博弈的是博弈的纯策略纳什均衡点纯策略纳什均衡点。若不存在同时得到划线的数对,即不存在若
21、不存在同时得到划线的数对,即不存在 同时满足()和()式,则博弈同时满足()和()式,则博弈 也就不也就不存在纯策略纳什均衡点。存在纯策略纳什均衡点。第34页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)36无限策略的纯策略纳什均衡 定理无限纯策略纳什均衡点存在性定理定理无限纯策略纳什均衡点存在性定理 无无限策略纳什均衡点的求解思路限策略纳什均衡点的求解思路 例古诺模型例古诺模型 例伯川德双寡头垄断模型例伯川德双寡头垄断模型 例公共地的悲剧例公共地的悲剧 例豪泰林价格竞争模型例豪泰林价格竞争模型第35页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用
22、博弈论及其应用(汪贤裕)(汪贤裕)37定理 在博弈在博弈 中,若局中人中,若局中人 的的策略集策略集 是有界闭区域,支付函数是有界闭区域,支付函数 对任意对任意 都是都是 的拟凹连续函数,则博的拟凹连续函数,则博弈弈 一定存在有纯策略纳什均衡点。一定存在有纯策略纳什均衡点。注:严格拟凹函数定义点击注:严格拟凹函数定义点击 第36页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)38严格拟凹函数定义严格拟凹函数定义 设设 是凸集是凸集 上的函数,对任意上的函数,对任意 及任意及任意 ,若有:,若有:()则则 为为 上的上的拟凹函数拟凹函数。若()式中不等号为
23、严格不等号,则称若()式中不等号为严格不等号,则称 为为 上的上的严格拟凹函数严格拟凹函数。第37页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)39无限策略纳什均衡点的求解思路当局中人当局中人 的收益函数的收益函数 都是都是 上的连续可微严格拟凹函数时,每个局中上的连续可微严格拟凹函数时,每个局中人都有一个最优反映函数(点击人都有一个最优反映函数(点击 )组成含)组成含 个未知数的个未知数的 个方程的方程组:个方程的方程组:()()求解()式得到博弈求解()式得到博弈 的一个纯策略纳什均衡点的一个纯策略纳什均衡点 注:第38页/共163页博弈论及其应用
24、(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)40反应函数的定义和求解 设设 是定义规定下的拟凹函数,有:是定义规定下的拟凹函数,有:()称称 为局中人为局中人 在在 上最优的上最优的反应函数反应函数 第39页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)41反应函数的定义和求解 当当 对任意对任意 是是 上的严格的拟凹函数时,上的严格的拟凹函数时,即只有一个,即只有一个元素。这时,最优反应函数为元素。这时,最优反应函数为:()若若 在闭区间在闭区间 上连续可微且对任意上连续可微且对任意 是严格拟凹函数,是严格拟凹函数,则令则令 可得最优反
25、应函数:可得最优反应函数:第40页/共163页博弈论及其应用(汪贤裕)#博弈论及其应用博弈论及其应用(汪贤裕)(汪贤裕)42例古诺模型 设市场有设市场有1、2两个寡头厂商,生产并销售同一种产品。厂商两个寡头厂商,生产并销售同一种产品。厂商1、2生产商品的数量分生产商品的数量分别为别为 和和 ,他们有不同的不变边际成本,分别为,他们有不同的不变边际成本,分别为 和和 ,无固定成本。市场的逆需求,无固定成本。市场的逆需求函数为函数为 一个正常数,即该产品的市场最高价格且一个正常数,即该产品的市场最高价格且 。市场需求情况和两厂商的成本和收益确定都是共同知识。两个厂商事前。市场需求情况和两厂商的成本
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 均衡 四川大学
限制150内