《纳什均衡四川大学课件》由会员分享,可在线阅读,更多相关《纳什均衡四川大学课件(163页珍藏版)》请在金锄头文库上搜索。
1、博弈论及其应用博弈论及其应用第2章 纳什均衡2010-3-31纳什均衡四川大学课件博弈论及其应用 (汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)2主要内容:主要内容:2.1 2.1 基本概念基本概念 2.2 2.2 纳什均衡纳什均衡 2.3 2.3 混合策略纳什均衡混合策略纳什均衡 2.4 2.4 矩阵博弈矩阵博弈第2章 纳什均衡2纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)32.1 基本概念 2.1.1 2.1.1 基本概念基本概念 2.1.2 2.1.2 占优均衡占优均衡 3纳什均
2、衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)42.1.1 基本概念 例例2.1.1 2.1.1 智猪博弈智猪博弈 例例2.1.2 2.1.2 夫妻爱好问题夫妻爱好问题 例例2.1.3 2.1.3 猜钱币游戏猜钱币游戏 完全信息静态博弈的三个基本要素完全信息静态博弈的三个基本要素 4纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)5智猪博弈 猪圈里有两头猪,一头大猪,一头小猪。猪圈猪圈里有两头猪,一头大猪,一头小猪。
3、猪圈的一边有一个食槽,另一边安装一个控制按钮,的一边有一个食槽,另一边安装一个控制按钮,它能控制食料的供应。按一下按钮有它能控制食料的供应。按一下按钮有8 8个单位个单位的食料进入猪食槽,但需要支付的食料进入猪食槽,但需要支付2 2个单位的劳个单位的劳动成本。在吃食的过程中,若大猪先到,大猪动成本。在吃食的过程中,若大猪先到,大猪能吃能吃7 7个单位的食料,小猪只能吃个单位的食料,小猪只能吃1 1个单位。若个单位。若小猪先到,小猪能吃到小猪先到,小猪能吃到4 4个单位的食料,大猪个单位的食料,大猪只能吃只能吃4 4个单位。若两只猪同时到,大猪吃个单位。若两只猪同时到,大猪吃5 5个个单位,小猪
4、吃单位,小猪吃3 3个单位的食料。大猪和小猪都个单位的食料。大猪和小猪都有两个策略,按或等待。有两个策略,按或等待。 5纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)6智猪博弈(续)两只猪在不同策略下的支付矩阵:两只猪在不同策略下的支付矩阵:大猪和小猪分别采取什么样的策略,且各自的收益分别为多少大猪和小猪分别采取什么样的策略,且各自的收益分别为多少? ?6纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)7夫妻爱
5、好问题 OROR7纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)8猜钱币游戏 8纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)9完全信息静态博弈三要素 局中人集合局中人集合 局中人集合即博弈参加人的集合。若给定局中人局中人集合即博弈参加人的集合。若给定局中人 ,则记,则记 策略集策略集 每个局中人每个局中人 有一个策略集有一个策略集S Si i ,策略集,策略集S Si i , 可以是有限集,也可以是无可以是
6、有限集,也可以是无限集,当策略集是有限集时,我们记:限集,当策略集是有限集时,我们记: 当每个局中人当每个局中人 选定一个策略选定一个策略s si i 后,形成一个策略组合后,形成一个策略组合 ,并称为一个局势,并称为一个局势,记为:记为: 我们也引入如下记号:我们也引入如下记号: 显然,显然, 也是一个局势,且也是一个局势,且 。支付函数支付函数 每个局中人有一个支付函数。是局势每个局中人有一个支付函数。是局势 s 的函数,是局中人在局势下所能得到的的函数,是局中人在局势下所能得到的收益。当然,每个局中人都希望自己的尽可能大。收益。当然,每个局中人都希望自己的尽可能大。9纳什均衡四川大学课件
7、博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)10完全信息静态博弈三要素 完全信息静态博弈就是在上述三要素的基础上,分完全信息静态博弈就是在上述三要素的基础上,分 析各局中人为实现自身利益最大化的策略行为分析。析各局中人为实现自身利益最大化的策略行为分析。 简记为简记为:10纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)112.1.2 占优均衡 定义定义2.1.1 2.1.1 严格占优策略严格占优策略 定义定义2.1.2 2.1
8、.2 占优均衡占优均衡 定义定义2.1.3 2.1.3 重复剔除占优均衡重复剔除占优均衡 11纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)12定义2.1.1 严格占优策略 在博弈在博弈 中,若中,若 和和 是局中人是局中人 的两个的两个策略,对任意策略组合策略,对任意策略组合 都有:都有: (2.1.12.1.1)则)则称,局中人称,局中人 的策略的策略 严格占优策略严格占优策略 ,或称策略,或称策略 相对于相对于 是是严格劣策略严格劣策略。 囚徒困境囚徒困境中、中、犯罪嫌疑人犯罪嫌疑人A A和和B
9、 B策略(承认)就是一个严策略(承认)就是一个严格占优策略。格占优策略。12纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)13定义2.1.2 占优均衡 在博弈在博弈 中,若每一个局中人中,若每一个局中人 都存在一个策略都存在一个策略 ,使得,使得 占优于占优于 中任何策略,那么策略组合中任何策略,那么策略组合 称为称为 的占优策略均衡,简称的占优策略均衡,简称占优均衡占优均衡。对应的。对应的 称为称为占优均衡结果占优均衡结果。13纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (
10、汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)14定义2.1.2 占优均衡(续) 囚徒困境囚徒困境中严格占优均衡:中严格占优均衡: (承认,承认)(承认,承认)均衡结果14纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)15定义2.1.3 重复剔除占优均衡 在博弈在博弈 中,经过重复剔出严格劣策略中,经过重复剔出严格劣策略后,每个局中人后,每个局中人 只剩下一个唯一的策略:只剩下一个唯一的策略: 那么,策略组合那么,策略组合 称为博弈称为博弈 的的重复重复剔除占优均衡。剔除占优均衡
11、。 对应对应 称为称为 的的重复剔除占优均衡结果重复剔除占优均衡结果。 15纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)16定义2.1.3 重复剔除占优均衡(续)智猪博弈智猪博弈中重复剔除占优均衡中重复剔除占优均衡: (按,不按)(按,不按)均衡结果16纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)172.2 纳什均衡 2.2.1 2.2.1 纯策略纳什均衡纯策略纳什均衡 2.2.2 2.2.2 双矩阵博弈
12、的划线法双矩阵博弈的划线法 2.2.3 2.2.3 无限策略的纯策略纳什均衡无限策略的纯策略纳什均衡17纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)182.2.1 纯策略纳什均衡 定义定义2.2.1 2.2.1 纯策略纳什均衡点和均衡结果纯策略纳什均衡点和均衡结果 定理定理2.2.1 2.2.1 重复剔除占优均衡与纯策略纳什均衡重复剔除占优均衡与纯策略纳什均衡 纳什均衡点与多目标规划求解比较纳什均衡点与多目标规划求解比较18纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤
13、裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)19纯策略纳什均衡点和结果 定义定义2.2.12.2.1 在在 人非合作博弈人非合作博弈 中,若有策略组合中,若有策略组合 ,使得每一个,使得每一个 ,对任意,对任意 都有都有 (2.2.12.2.1) 则称则称 是是 的一个的一个纯策略纳什均衡点纯策略纳什均衡点,对应的,对应的 称为对应的称为对应的均衡结果。均衡结果。19纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)20纯策略纳什均衡点和结果夫妻爱好夫妻爱好博弈中纯策略纳什均衡点:博弈
14、中纯策略纳什均衡点: (足球,看足球)(足球,看足球)& &(看芭蕾,看芭蕾)(看芭蕾,看芭蕾)均衡结果均衡结果20纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)21纯策略纳什均衡点和结果(续)猜钱币游戏猜钱币游戏中不存在纯策略纳什均衡点中不存在纯策略纳什均衡点。21纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)22定理2.2.1 在在 人非合作博弈人非合作博弈 中:中: 若,若, 是是重复剔除占优均衡重复剔
15、除占优均衡, 则则 一定是一定是纯策略纳什均衡点纯策略纳什均衡点。22纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)23定理2.2.1的证明证明:证明:用用反证法反证法。 若若 是重复剔除占优均衡,但不是纯策略纳什均衡点。则有是重复剔除占优均衡,但不是纯策略纳什均衡点。则有 和和 , , , , 使得使得 (2.2.22.2.2) 那么在局中人那么在局中人 在对在对 的剔除过程中应有对任意的策略组合的剔除过程中应有对任意的策略组合 满足满足(2.2.12.2.1)式。这里策略组合当然也包括)式。这里策
16、略组合当然也包括 ,即,即 因此(因此(2.2.22.2.2)式是不可能出现的,即()式是不可能出现的,即(2.2.22.2.2)式与剔除严格劣策略过程)式与剔除严格劣策略过程矛盾。矛盾。 从而定理从而定理2.2.12.2.1成立。成立。 23纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)24纳什均衡点与多目标规划求解比较在在n n人非合作博弈人非合作博弈 中,对每一个局中人中,对每一个局中人 ,都在寻找自己的策略都在寻找自己的策略 使得自己的收益使得自己的收益 最大,最大,但是局中人但是局中人 单方
17、面不能找到自己的最佳策略,其结果是相互影单方面不能找到自己的最佳策略,其结果是相互影响的,是由策略组合响的,是由策略组合 决定的。这就是一个有相决定的。这就是一个有相互影响的多人决策问题。有人可能这样设想:是否有一个局外人,互影响的多人决策问题。有人可能这样设想:是否有一个局外人,将将 个局中人的收益最大作为个局中人的收益最大作为 个目标的个目标的多目标规划问题多目标规划问题,即求:,即求: (2.2.32.2.3) 纳什均衡点和上面的(纳什均衡点和上面的(2.2.32.2.3)的多目标规划的求解是两个不同)的多目标规划的求解是两个不同的概念。的概念。 24纳什均衡四川大学课件博弈论及其纳什均
18、衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)25纳什均衡点与多目标规划求解比较(续)囚犯困境是一个囚犯困境是一个2 2人非合作博弈人非合作博弈 两个局中人策略集两个局中人策略集 和支付和支付 函数函数 都表示在表都表示在表1.2.11.2.1中中图图2.2.1 2.2.1 囚犯困境中的局中人囚犯困境中的局中人 收益图收益图以囚徒困境为例以囚徒困境为例25纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)26纳什均衡点与多目标规划求解比较(续)各点
19、代表不同策略组合下双方的收益:各点代表不同策略组合下双方的收益:A A点对应策略组合(承认,承认)点对应策略组合(承认,承认)B B点对应策略组合(承认,不承认)点对应策略组合(承认,不承认)C C点对应策略组合(不承认,不承认)点对应策略组合(不承认,不承认)DD点对应策略组合(不承认,承认)点对应策略组合(不承认,承认)B B点、点、C C点和点和D D点所代表的策略组合点所代表的策略组合 都是单人决策的多目标规划(都是单人决策的多目标规划(2.2.32.2.3) 中的非劣解。中的非劣解。但策略组合(承认,承认)是唯一的纳什均衡点。但策略组合(承认,承认)是唯一的纳什均衡点。26纳什均衡四
20、川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)27纳什均衡点与多目标规划求解比较(续)结论:结论: (一)非合作博弈中的纳什均衡点,不可能用(一)非合作博弈中的纳什均衡点,不可能用(2.2.32.2.3)表示的多目标规划作为替代,双方有不同的)表示的多目标规划作为替代,双方有不同的思想基础。思想基础。 (二)博弈论与多目标规划这类多人决策问题的差异,(二)博弈论与多目标规划这类多人决策问题的差异,进一步显示出纳什均衡思想在博弈论中的重要地位。进一步显示出纳什均衡思想在博弈论中的重要地位。27纳什均衡四川大学课件
21、博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)282.2.2 双矩阵博弈的划线法 双矩阵博弈的定义双矩阵博弈的定义 纯策略纳什均衡的简单求解方法纯策略纳什均衡的简单求解方法划线法划线法 定理定理2.2.2 2.2.2 划线法与纯策略纳什均衡划线法与纯策略纳什均衡28纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)29双矩阵博弈的定义在博弈中,若三要素的前两个要素满足:在博弈中,若三要素的前两个要素满足:只有只有两个局中人两个局中人
22、,即,即 ; ;策略集有限策略集有限,即,即 ,此类博弈我们称为此类博弈我们称为双矩阵博弈双矩阵博弈。29纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)30双矩阵博弈称呼的由来(补充1) 在双矩阵博弈中,对任意策略组合在双矩阵博弈中,对任意策略组合 ,记支付,记支付函数函数 , ,将两个局中人的支,将两个局中人的支付函数分别记为矩阵付函数分别记为矩阵A A和矩阵和矩阵B B如下:如下: 30纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及
23、其应用 (汪贤裕)(汪贤裕)31双矩阵博弈称呼的由来(补充2) (2.2.4) 回到: 划线法 定理2.2.231纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)32划线法 (1)(1)对局中人对局中人1 1,在(,在(2.2.42.2.4)式)式 的每一行的每一行 中,找出对中,找出对方支付矩阵方支付矩阵B B中该行的最大元素中该行的最大元素 , ,即即 并在并在 下划线。当下划线。当 不唯一时,均在下面划线。不唯一时,均在下面划线。(2)(2)对局中人对局中人2 2,在(,在(2.2.42.2.4)
24、式每一列)式每一列 中,找出对方支中,找出对方支付矩阵付矩阵A A中该列的最大元素中该列的最大元素 即即 并在并在 下划线。当下划线。当 不唯一时,均在下面划线。不唯一时,均在下面划线。32纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)33划线法(续)(3)(3)若存在一对若存在一对 ,使得其两个元素,使得其两个元素 和和 下面都有划线,则下面都有划线,则 是纯策略纳什均衡是纯策略纳什均衡点,点, 和和 是对应的纳什均衡结果。是对应的纳什均衡结果。(4)(4)若不存在满足(若不存在满足(3 3)的数对
25、,则该博弈无纯策略)的数对,则该博弈无纯策略纳什均衡。纳什均衡。33纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)34定理2.2.2 在双矩阵博弈在双矩阵博弈 中划线法的使用:中划线法的使用:(1)(1)若若 和和 同时得到划线,则同时得到划线,则 一定是一定是 的纯策略纳什均衡点。的纯策略纳什均衡点。(2)(2)若不存在能够同时得到划线的数对,则若不存在能够同时得到划线的数对,则 无纯无纯策略纳什均衡点。策略纳什均衡点。34纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤
26、裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)35定理2.2.2的证明设设 和和 都得到划线,则下面两式同时成立:都得到划线,则下面两式同时成立: (2.2.52.2.5) (2.2.62.2.6) 是博弈的是博弈的纯策略纳什均衡点纯策略纳什均衡点。若不存在同时得到划线的数对,即不存在若不存在同时得到划线的数对,即不存在 同时满同时满足(足(2.2.52.2.5)和()和(2.2.62.2.6)式,则博弈)式,则博弈 也就不存在纯策也就不存在纯策略纳什均衡点。略纳什均衡点。 35纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及
27、其应用博弈论及其应用 (汪贤裕)(汪贤裕)362.2.3无限策略的纯策略纳什均衡 定理定理2.2.3 2.2.3 无限纯策略纳什均衡点存在性定理无限纯策略纳什均衡点存在性定理 无限策略纳什均衡点的求解思路无限策略纳什均衡点的求解思路 例例2.2.2 2.2.2 古诺模型古诺模型 例例2.2.3 2.2.3 伯川德双寡头垄断模型伯川德双寡头垄断模型 例例2.2.4 2.2.4 公共地的悲剧公共地的悲剧 例例2.2.5 2.2.5 豪泰林价格竞争模型豪泰林价格竞争模型36纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕
28、)(汪贤裕)37定理2.2.3 在博弈在博弈 中,若局中人中,若局中人 的策的策略集略集 是有界闭区域,支付函数是有界闭区域,支付函数 对对任意任意 都是都是 的拟凹连续函数,则博弈的拟凹连续函数,则博弈 一定存在有纯策略纳什均衡点。一定存在有纯策略纳什均衡点。注:严格拟凹函数定义点击注:严格拟凹函数定义点击 37纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)38严格拟凹函数定义严格拟凹函数定义 设设 是凸集是凸集 上的函数,对任意上的函数,对任意 及任及任意意 ,若有:,若有: (2.2.82.2.
29、8) )则则 为为 上的上的拟凹函数拟凹函数。 若(若(2.2.82.2.8)式中不等号为严格不等号,则称)式中不等号为严格不等号,则称 为为 上的上的严格拟凹函数严格拟凹函数。38纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)39无限策略纳什均衡点的求解思路当局中人当局中人 的收益函数的收益函数 都是都是 上的连续上的连续可微严格拟凹函数时,每个局中人都有一个最优反映函可微严格拟凹函数时,每个局中人都有一个最优反映函数(点击数(点击 )组成含)组成含 个未知数的个未知数的 个方程的方程组:个方程的方
30、程组: (2.2.112.2.11) 求解(求解(2.2.112.2.11)式得到博弈)式得到博弈 的一个纯策略纳什均衡点的一个纯策略纳什均衡点 注:39纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)40反应函数的定义和求解 设设 是定义是定义2.2.22.2.2规定下的拟凹函数,有:规定下的拟凹函数,有: (2.2.9) 称称 为局中人为局中人 在在 上最优的上最优的反应函数反应函数 40纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及
31、其应用 (汪贤裕)(汪贤裕)41反应函数的定义和求解 当当 对任意对任意 是是 上的严格的拟凹函数上的严格的拟凹函数时,时, ,即只有一个元素。这时,最优反应,即只有一个元素。这时,最优反应函数为函数为: : (2.2.10) 若若 在闭区间在闭区间 上连续可微且对上连续可微且对任意任意 是严格拟凹函数,则令是严格拟凹函数,则令 可得最优可得最优反应函数:反应函数: 41纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)42例2.2.2 古诺模型 设市场有设市场有1 1、2 2两个寡头厂商,生产并销售同一
32、种两个寡头厂商,生产并销售同一种产品。厂商产品。厂商1 1、2 2生产商品的数量分别为生产商品的数量分别为 和和 ,他们有,他们有不同的不变边际成本,分别为不同的不变边际成本,分别为 和和 ,无固定成本。,无固定成本。市场的逆需求函数为市场的逆需求函数为 一个正常数,即该产品的市场最高价格且一个正常数,即该产品的市场最高价格且 。市场需求情况和两厂商的成本和收益。市场需求情况和两厂商的成本和收益确定都是共同知识。两个厂商事前没有任何协议和约定,确定都是共同知识。两个厂商事前没有任何协议和约定,同时分别决定生产的产量,以追求市场的最大利润(设同时分别决定生产的产量,以追求市场的最大利润(设厂商的
33、生产产量没有限制,但厂商的生产产量没有限制,但 )。)。 42纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)43例2.2.2 古诺模型(续) 该博弈中局中人为两个厂商,生产数量是他们的策略,该博弈中局中人为两个厂商,生产数量是他们的策略, 即即 。厂商各自的利润函数:。厂商各自的利润函数: (2.2.122.2.12) (2.2.132.2.13) 由(由(2.2.122.2.12)和()和(2.2.132.2.13)式可知,)式可知, 对任何对任何 都是都是 的严格连续凹函数,的严格连续凹函数, 对
34、任何对任何 都是都是 的严格连续的严格连续凹函数。凹函数。43纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)44例2.2.2 古诺模型(续) 两个厂商都来确定产量以追求最大利润可以表示成:两个厂商都来确定产量以追求最大利润可以表示成: 求求 和和 ,并且令,并且令 和和 有:有: (2.2.14) (2.2.15) 44纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)45例2.2.2 古诺模型(续) 求解最优反
35、应函数(求解最优反应函数(2.2.14)和和(2.2.15)组成的组成的方程组:方程组:(2.2.16) (2.2.17) 组成该博弈的平衡局势,即纯策略纳什均衡点。组成该博弈的平衡局势,即纯策略纳什均衡点。均衡结果,分别为:均衡结果,分别为: 。 45纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)46例2.2.2 古诺模型(续) 该博弈的纯策略纳什均衡的意义该博弈的纯策略纳什均衡的意义 以厂商以厂商1 1为例,由为例,由 ,决定以边际利润等于边,决定以边际利润等于边际成本来确定生产量,才是最优的。但
36、边际利润不仅与自己的际成本来确定生产量,才是最优的。但边际利润不仅与自己的产量产量 有关,也受到厂商有关,也受到厂商2 2的产量的产量 的影响。从反应函数可知,的影响。从反应函数可知,要满足边际成本等于边际利润,其产量要满足边际成本等于边际利润,其产量 与对方生产的产量与对方生产的产量 的关系必须满足(的关系必须满足(2.2.142.2.14)式。厂商)式。厂商2 2也是同样的,要满足边际也是同样的,要满足边际成本等于边际利润,其产量成本等于边际利润,其产量 与对方的生产产量必须满足与对方的生产产量必须满足(2.2.152.2.15)式。求解()式。求解(2.2.142.2.14)和()和(2
37、.2.152.2.15)构成了纳什均衡。)构成了纳什均衡。46纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)47例2.2.2 古诺模型(续)纳什均衡点和多目标规划中解概念的差异纳什均衡点和多目标规划中解概念的差异 1 1 以例以例2.2.22.2.2古诺模型为例,将有限策略放宽至无限古诺模型为例,将有限策略放宽至无限 2 2 假设厂商假设厂商1 1和厂商和厂商2 2有相同的不变边际成本,即有相同的不变边际成本,即 47纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪
38、贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)48例2.2.2 古诺模型(续)将古诺模型中两厂商如何取得自己收益最大作为多目标将古诺模型中两厂商如何取得自己收益最大作为多目标规划问题:规划问题:(2.2.18) 其中其中 和和 均由(均由(2.2.122.2.12)和()和(2.2.132.2.13)两式确定()两式确定( )。)。48纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)49例2.2.2 古诺模型(续) 该多目标规划的非劣解由下图所示的直线段该多目标规划的非劣解由下图所示的直线段A
39、BAB确定:确定: 图图2.2.3 2.2.3 古诺模型的纳什均衡与多目标规划的关系古诺模型的纳什均衡与多目标规划的关系49纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)50例2.2.2 古诺模型(续)上图中上图中D D点表示两厂商均生产点表示两厂商均生产 时双方的时双方的收益。收益。直线直线ABAB的确定的确定 若两厂商由一个垄断集团控制,则最优产量为下若两厂商由一个垄断集团控制,则最优产量为下式的最优解:式的最优解:50纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕
40、)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)51例2.2.2 古诺模型(续) 取取 ,求解上式,则当,求解上式,则当 时,时, 有最值有最值 。也就是说,当厂商。也就是说,当厂商1 1采取策略采取策略 ,厂商,厂商2 2采取采取 ,而,而 时,厂商时,厂商1 1的收益的收益 和厂商和厂商2 2的收益的收益 满足满足 。这样,厂商。这样,厂商1 1和厂商和厂商2 2的收益的帕累托边界为直线段的收益的帕累托边界为直线段ABAB。对应。对应多目标规划(多目标规划(2.2.182.2.18)的非劣解为:)的非劣解为: , ,51纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论
41、及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)52例2.2.2 古诺模型(续) 多目标规划(多目标规划(2.2.182.2.18)的任何满意解都是依一定的)的任何满意解都是依一定的法则在非劣解中寻求满意解。而此时古诺模型的纳什均法则在非劣解中寻求满意解。而此时古诺模型的纳什均衡为:衡为: 对应的收益为图对应的收益为图2.2.32.2.3的的C C点,即两厂商的收益点,即两厂商的收益分别是分别是 。纳什均衡点。纳什均衡点 是多是多目标规划(目标规划(2.2.182.2.18)中的劣解。)中的劣解。52纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及
42、其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)53例2.2.2 古诺模型(续)结论结论 在策略集为无限时,纳什均衡点仍然不是多目标规在策略集为无限时,纳什均衡点仍然不是多目标规划中的非劣解。划中的非劣解。 纳什均衡与多目标规划存在不同,是不可混淆的。纳什均衡与多目标规划存在不同,是不可混淆的。造成这种差别的原因在于,纳什均衡是多人决策,而多造成这种差别的原因在于,纳什均衡是多人决策,而多目标规划是单人决策。目标规划是单人决策。 博弈论的一个最显著特征:博弈论的一个最显著特征:竞争环境下的多人决策竞争环境下的多人决策。53纳什均衡四川大学课件博弈论及其纳什均衡
43、四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)54伯川德双寡头垄断模型 考虑市场上有两个寡头厂商生产同一类型产品。厂考虑市场上有两个寡头厂商生产同一类型产品。厂商商1 1和厂商和厂商2 2分别选择价格分别选择价格 和和 。消费者对企业的产。消费者对企业的产品的需求为:品的需求为: 其中其中0b1,即只限于企业,即只限于企业 的产品和企业的产品和企业 产品具有相产品具有相互替代的情况。企业生产没有固定成本,并且边际成本互替代的情况。企业生产没有固定成本,并且边际成本为常数为常数 , 。 两个企业同时进行价格选择行动。另外企业两个企业同时进行
44、价格选择行动。另外企业 的策的策略略 是所选价格是所选价格 ,也即每个企业的策略集,也即每个企业的策略集 。 54纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)55伯川德双寡头垄断模型(续) 企业企业 选择价格选择价格 ,对手,对手 选择价格选择价格 ,企业的利润,企业的利润为:为: (2.2.20) 对于企业对于企业1 1来说,若企业来说,若企业2 2选定的价格为选定的价格为 ,它确定自,它确定自己的价格己的价格 以追求最大利润以追求最大利润 对企业对企业1 1求求 并且令并且令 解得:解得: (2
45、.2.21) 55纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)56 伯川德双寡头垄断模型(续) 同理,可得企业同理,可得企业2 2的最优价格的最优价格 (2.2.22) 联立联立(2.2.21)(2.2.22)解方程组得:解方程组得: (2.2.23)均衡结果为:均衡结果为: (2.2.24) 56纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)57例2.2.4 公共地的悲剧 考虑有相同情况的考虑有相同情况的
46、 个牧民组成的某个牧民村,他们共同拥有一个牧民组成的某个牧民村,他们共同拥有一片草地。每年所有的牧民都会在共同的草地上放牧养羊。用片草地。每年所有的牧民都会在共同的草地上放牧养羊。用 表示牧表示牧民民 养羊的头数,则牧民村的养羊总头数为养羊的头数,则牧民村的养羊总头数为 。购。购买羊崽和照看一只羊的成本为买羊崽和照看一只羊的成本为c c,c c不随某一牧民拥有羊的树目的多少不随某一牧民拥有羊的树目的多少而变化。当草地上的羊的总头数为而变化。当草地上的羊的总头数为 时,牧民养的一只羊的价值为时,牧民养的一只羊的价值为 ,设,设 。当草地上羊的总头数。当草地上羊的总头数 较少时,每只羊有相对较多的
47、较少时,每只羊有相对较多的空间,每只羊能吃到的草也丰盛些。而羊的总数空间,每只羊能吃到的草也丰盛些。而羊的总数 增加时,则正好相增加时,则正好相反,每只羊相对能吃到的草相对较少。并有当羊群总数反,每只羊相对能吃到的草相对较少。并有当羊群总数 达到一个极达到一个极限限 时,再增加一只羊将对已经牧养的羊带来损害。对一只羊的价时,再增加一只羊将对已经牧养的羊带来损害。对一只羊的价值值 的上述特征用公式表示,则为的上述特征用公式表示,则为: : , 。(2.2.25)(2.2.25)57纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应
48、用 (汪贤裕)(汪贤裕)58例2.2.4 公共地的悲剧(续) 每年春天,每年春天, 个牧民同时分别选择牧养羊的数量。假设其个牧民同时分别选择牧养羊的数量。假设其是连续的可分割的。牧民是连续的可分割的。牧民 的策略是选择在公共草地上牧养羊的策略是选择在公共草地上牧养羊的数量的数量 ,并有策略集,并有策略集 。当其他村民养羊。当其他村民养羊数为数为 时,牧民时,牧民 牧养牧养 只羊获得的收只羊获得的收益为:益为: 现在要讨论的问题是:牧民现在要讨论的问题是:牧民 如何决定自己的牧养羊数如何决定自己的牧养羊数 , ,以获得自己的最大收益,以获得自己的最大收益。(2.2.26(2.2.26) )58纳
49、什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)59例2.2.4 公共地的悲剧(续) 这构成了一个这构成了一个 人非合作博弈的问题,需要求平衡局势,人非合作博弈的问题,需要求平衡局势,即纳什均衡。很明显,即纳什均衡。很明显, 在任何在任何 时,都是时,都是 的凹函数。计的凹函数。计算算 并且并且令 ,得到:,得到: 当当 是一个已知函数时,求解由上式给出的是一个已知函数时,求解由上式给出的 个方程和个方程和 个未知数,可以求得该体系的纯策略纳什均衡点,即平衡局个未知数,可以求得该体系的纯策略纳什均衡点,即
50、平衡局势势 再代回到(再代回到(2.2.262.2.26)式,则有纳什均衡结果)式,则有纳什均衡结果。(2.2.27(2.2.27) )59纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)60例2.2.4 公共地的悲剧(续) 公共地的悲剧的意义公共地的悲剧的意义 将上面的将上面的 人非合作博弈的牧养羊纳什均衡结果与草地在非公共地的情况下,即人非合作博弈的牧养羊纳什均衡结果与草地在非公共地的情况下,即由社会计划管理者进行管理作对比研究。由社会计划管理者进行管理作对比研究。 在在 个牧民分散独立决策牧养羊情
51、况下,设个牧民分散独立决策牧养羊情况下,设 是第是第 个牧民的养羊数个牧民的养羊数 最优决策,最优决策, 。由于。由于 个牧民是相同情况个牧民是相同情况, ,则则: : , , 。 令令 ,则由(,则由(2.2.272.2.27)式得:)式得: 再将(再将(2.2.282.2.28)的)的 个方程加总,有:个方程加总,有: (2.2.29(2.2.29) )(2.2.28(2.2.28) )60纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)61例2.2.4 公共地的悲剧(续) 若草地是由社会计划者管理
52、,社会计划者选择草地的最优牧若草地是由社会计划者管理,社会计划者选择草地的最优牧养量是养量是 ,则,则 应该是下式的解:应该是下式的解: 若上式的最优解为若上式的最优解为 ,则,则 应满足应满足 (边际收益等于边际成本),(边际收益等于边际成本),即:即: 比较(比较(2.2.292.2.29)式和()式和(2.2.312.2.31)式,下面我们证明)式,下面我们证明 。 由式(由式(2.2.292.2.29)和()和(2.2.312.2.31)式有:)式有: (2.2.30(2.2.30) )(2.2.31(2.2.31) )(2.2.32(2.2.32) )61纳什均衡四川大学课件博弈论及
53、其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)62例2.2.4 公共地的悲剧(续) 令令 由(由(2.2.322.2.32)式和()式和(2.2.252.2.25)式有:)式有: 由(由(2.2.332.2.33)式和()式和(2.2.252.2.25)式得:)式得: 由(由(2.2.342.2.34)和()和(2.2.352.2.35)有:)有: (2.2.33(2.2.33) )(2.2.34(2.2.34) )(2.2.35(2.2.35) )(2.2.36(2.2.36) ) 由于由于 个牧民是对称的,则他们分散养羊的总
54、收益为:个牧民是对称的,则他们分散养羊的总收益为: ,而社会计划管理者的养羊带来的总收益为,而社会计划管理者的养羊带来的总收益为: : 。62纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)63例2.2.4 公共地的悲剧(续) 由于由于 是(是(2.2.302.2.30)式的最优解,则必有)式的最优解,则必有: : (2.2.362.2.36)式表明,在均衡点时,)式表明,在均衡点时, 个牧民牧养羊的个牧民牧养羊的总数超过社会最优条件下的牧养总数。并由(总数超过社会最优条件下的牧养总数。并由(2.2.3
55、72.2.37)式,式, 个牧民养羊的总收益低于社会计划管理者的总收个牧民养羊的总收益低于社会计划管理者的总收益。由于每个牧民都只考虑自己的利益,并不管其行为益。由于每个牧民都只考虑自己的利益,并不管其行为对其他牧民带来的影响,致使公共草地被过度使用,并对其他牧民带来的影响,致使公共草地被过度使用,并且得不偿失。这就是经济学中的且得不偿失。这就是经济学中的“公共地的悲剧公共地的悲剧”。(2.2.37(2.2.37) )63纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)64例2.2.5 豪泰林价格竞争模
56、型 在古诺特模型中,产品是同质的。但在更多的实际问题在古诺特模型中,产品是同质的。但在更多的实际问题中,不同的企业生产的产品是有差异的,替代弹性不会中,不同的企业生产的产品是有差异的,替代弹性不会是无限的,此时消费者对不同的产品有不同的偏好。是无限的,此时消费者对不同的产品有不同的偏好。 考虑产品差异的一种特殊的情况,即考虑产品差异的一种特殊的情况,即空间上的差异空间上的差异豪泰林模型豪泰林模型64纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)65豪泰林价格竞争模型(续) 假定有一个长度为假定有一个长
57、度为1 1的线性城市,消费者均匀地分布在的线性城市,消费者均匀地分布在00,11区区间里,其分布函数的密度为间里,其分布函数的密度为1 1。假设有两个商店分别位于城市的。假设有两个商店分别位于城市的两端,商店两端,商店1 1位于处位于处 ,商店,商店2 2位于处位于处 ,他们出售物质,他们出售物质性能相同的产品。每个商店具有相同的单位产品成本为性能相同的产品。每个商店具有相同的单位产品成本为 。消。消费者购买商品的旅行成本与离商店的距离成正比例,单位距离的费者购买商品的旅行成本与离商店的距离成正比例,单位距离的成本为成本为 。所以住在的消费者如果去商店。所以住在的消费者如果去商店1 1去购买,
58、要花费的旅去购买,要花费的旅行成本行成本 ;如果去商店;如果去商店2 2去购买,要花费的旅行成本去购买,要花费的旅行成本 。为方便讨论,再假定消费者都有单位的物质需求,即消费。为方便讨论,再假定消费者都有单位的物质需求,即消费1 1个个单位消费品。另外所有消费者都可能到两家商店购买,即他们都单位消费品。另外所有消费者都可能到两家商店购买,即他们都能获得消费剩余。能获得消费剩余。65纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)66豪泰林价格竞争模型(续)模型的建立模型的建立令令 为商店的商品为商店的商
59、品 的价格的价格 ,商店,商店 的出价,即是它的策略,因而商店的出价,即是它的策略,因而商店 的策略集为的策略集为 , 。商店的收益函数商店的收益函数令令 为需求函数,为需求函数, 。那么存在一点那么存在一点 ,住在,住在 左边的消费者都将到商店左边的消费者都将到商店1 1去购买,住在去购买,住在 右边的消费者都将到商店右边的消费者都将到商店2 2去购买,去购买,我们说住在我们说住在 处的消费者在两个商店之间是无差异处的消费者在两个商店之间是无差异的。这里的。这里 应该满足:应该满足: (2.2.38)66纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕
60、)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)67豪泰林价格竞争模型(续)解(解(2.2.382.2.38)式得需求函数分别为:)式得需求函数分别为:(2.2.39) (2.2.40)两商店利润函数分别为:两商店利润函数分别为:(2.2.41) (2.2.42)67纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)68豪泰林价格竞争模型(续)商店选择自己的价格商店选择自己的价格 以最大化自己的利润。以最大化自己的利润。求求 并且令并且令 ,有最优反应函数如下:,有最优反应函数如下:(2.2.43)
61、(2.2.44) (2.2.43)(2.2.44)式联立解方程组得:式联立解方程组得: (2.2.45)68纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)69豪泰林价格竞争模型(续) 即为纳什均衡点,对应的均衡结果,即即为纳什均衡点,对应的均衡结果,即每个商店的均衡利润为:每个商店的均衡利润为:69纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)702.3 混合策略纳什均衡 2.3.1 2.3.1 混合策略纳什
62、均衡混合策略纳什均衡 2.3.2 2.3.2 混合策略纳什均衡点的存在性定理混合策略纳什均衡点的存在性定理 2.3.3 2.3.3 双矩阵博弈的纳什均衡双矩阵博弈的纳什均衡70纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)712.3.1 混合策略纳什均衡 定义定义2.3.1 2.3.1 混合策略混合策略 混合策略下混合策略下 人非合作博弈三要素人非合作博弈三要素 定义定义2.3.22.3.2混合策略纳什均衡点和均衡结果混合策略纳什均衡点和均衡结果71纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博
63、弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)72混合策略的定义 对于每个对于每个 ,局中人,局中人 的纯策略集的纯策略集 。若局中人。若局中人 对每一个纯策略对每一个纯策略 以以 概率概率 进行选择,则进行选择,则 被称为局中人被称为局中人 的一个的一个混合策略混合策略。其中。其中 , , 。 72纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)73混合策略的定义 局中人局中人 混合策略就是定义在其纯策略集混合策略就是定义在其纯策略集 上的一个上的一个概率分布
64、。概率分布。 局中人局中人 的的混合策略集混合策略集记为记为 : (2.3.12.3.1) 记记 为博弈为博弈 的一个的一个混合策略组合混合策略组合。73纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)74混合策略下 n 人非合作博弈三要素(1)(1)局中人的集局中人的集 ;(2)(2)每个局中人每个局中人 有一个有一个混合策略的集混合策略的集 其中其中 满足(满足(2.3.12.3.1););(3)(3)每个局中人有一个每个局中人有一个支付函数支付函数 并设并设 是局中人是局中人 的支付函数的支付函数
65、 在混合策略局势在混合策略局势 下得到的期望支付。下得到的期望支付。 在在混混合合策策略略的的情情形形下下,一一个个 人人非非合合作作博博弈弈可可以以用用下下面面的的记记号号来表示:来表示: 74纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)75混合策略纳什均衡点和均衡结果 设设 是是 人非合作博弈人非合作博弈 的一个混合策略局势。的一个混合策略局势。如果对于每一个如果对于每一个 和每个和每个 ,有,有 : : , , (2.3.22.3.2) 则称则称 是是 (在混合策略下)的一个(在混合策略下)的
66、一个混合策略纳什均衡点混合策略纳什均衡点, 为对应的为对应的均衡结果均衡结果。 为混合策略为混合策略 下局中人下局中人 的期望收益。的期望收益。75纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)762.3.2 混合策略纳什均衡点的存在性定理 定理定理2.3.1 2.3.1 混合策略纳什均衡点的充分必要条件混合策略纳什均衡点的充分必要条件 定理定理2.3.2 2.3.2 混合策略纳什均衡点的存在性混合策略纳什均衡点的存在性76纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕
67、)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)77定理2.3.1 设设 是是 人非合作博弈。人非合作博弈。 是是 的一个混的一个混合策略纳什均衡点的充分必要条件是:对于每个局中人合策略纳什均衡点的充分必要条件是:对于每个局中人 和每个纯策略和每个纯策略 ,有,有 。 (2.3.3) 这里这里 是将局中人是将局中人 的混合策略的混合策略 换成一换成一个纯策略个纯策略 后的期望支付。后的期望支付。 定理定理2.3.12.3.1证明证明77纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)78定
68、理2.3.1证明 必要性。必要性。显然成立。显然成立。 充分性。充分性。设(设(2.3.32.3.3)式成立,即对于每个)式成立,即对于每个 有有 , (2.3.4) 设设 是局中人是局中人 的任意一个混合策略。(的任意一个混合策略。(2.3.42.3.4)中)中 个不等式两端依次乘以个不等式两端依次乘以 ,得到,得到 , (2.3.5) 对对 从从1 1到到 求和:求和: (2.3.6) (2.3.62.3.6)式中的左端就是)式中的左端就是 ,右端的和式等于,右端的和式等于 1 1。 由此可知,由此可知, 是是 的混合策略纳什均衡。的混合策略纳什均衡。78纳什均衡四川大学课件博弈论及其纳什
69、均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)79定理2.3.2 每个每个 人非合作博弈人非合作博弈 必有必有混混合策略纳什均衡合策略纳什均衡79纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)80定理2.3.2证明 证明:设证明:设 是是 的任意混合策略局的任意混合策略局势。对于每个势。对于每个 的每个纯策的每个纯策 , ,定义定义 对于每个对于每个 ,定义,定义 (2.3.7(2.3.7) )(2.3.8)(2.3.8)80纳什均衡四川大学
70、课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)81定理2.3.2证明(续) Brouwer Brouwer 不不动点定理:定点定理:定义在有限在有限维欧欧式空式空间紧凸集凸集S S上上从从S S映入其本身的映入其本身的连续映射必有不映射必有不动点点。易知,易知, , , 所以所以 是局是局 中人中人 的一个混合策略。的一个混合策略。 是是 的连续函数,所以的连续函数,所以 是是 的连续函数。根据的连续函数。根据 BrouwerBrouwer 不动点定理,存在不动点定理,存在不动点不动点 ,其中其中 ,使得,使得 (2
71、.3.9)(2.3.9)81纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)82定理2.3.2证明(续) 该不动点就是博弈该不动点就是博弈 的混合策略纳什均衡的证明的混合策略纳什均衡的证明 首先,对于任意的混合策略局势首先,对于任意的混合策略局势 ,每个局中人每个局中人 必有一个纯策略必有一个纯策略 ,使得,使得 ,且,且 因此,对于因此,对于 ,局中人,局中人 的策略的策略 中中必定包含一个必定包含一个 ,使得,使得 , 从而从而 。由(由(2.3.72.3.7)有:)有: 。(2.3.10(2.3.
72、10) )82纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)83定理2.3.2证明(续) 其中其中 。由此可得。由此可得: : 。 而由而由 的定义,所有的的定义,所有的 都是非负的,所以从上式可知,对于都是非负的,所以从上式可知,对于每个每个 , 。因此根据(。因此根据(2.3.72.3.7)式,有)式,有 , ,即即 。 上式对于每个上式对于每个 成立。由定理成立。由定理2.3.12.3.1可知,可知, 是是 的混合策的混合策略纳什均衡。略纳什均衡。 对于上述局中人对于上述局中人 的策略的策略 ,
73、由(,由(2.3.92.3.9)式有:)式有:83纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)842.3.3 双矩阵博弈的纳什均衡 双矩阵博弈纳什均衡的求解双矩阵博弈纳什均衡的求解 例例2.3.1 2.3.1 含一个参数含一个参数 的的 双矩阵博弈双矩阵博弈 例例2.3.2 2.3.2 小偷与守卫的博弈小偷与守卫的博弈 84纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)85 双矩阵博弈纳什均衡的求解 存在策
74、略占优时纳什均衡的求解存在策略占优时纳什均衡的求解 不存在策略占优时纳什均衡的求解不存在策略占优时纳什均衡的求解85纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)86存在策略占优时纳什均衡的求解 设双矩阵博弈局中人设双矩阵博弈局中人1 1,2 2的支付矩阵分别为的支付矩阵分别为 若若 , ,或,或 , ,则局中,则局中人人1 1有严格占优策略;有严格占优策略; 若若 , ,或,或 , ,则局中人,则局中人2 2有严格占优策略。有严格占优策略。 之后,采用重复剔除法,可得重复剔除占优均衡,同之后,采用重
75、复剔除法,可得重复剔除占优均衡,同时求得纳什均衡。时求得纳什均衡。 86纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)87存在策略占优时纳什均衡的求解 若若 , ,则局中人,则局中人1 1的两个策略无差异,的两个策略无差异,即采用任何纯策略或任何混合策略都有相同的收益。即采用任何纯策略或任何混合策略都有相同的收益。 若若 , ,则局中人,则局中人2 2的两个策略无差异,的两个策略无差异,即采用任何纯策略或任何混合策略都有相同的收益。即采用任何纯策略或任何混合策略都有相同的收益。 这种情况没有讨论的意义
76、。这种情况没有讨论的意义。 87纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)88不存在策略占优时纳什均衡的求解 局中人局中人1 1的支付矩阵的支付矩阵A A中,有:中,有: ,且至,且至少有一个等式不成立;或少有一个等式不成立;或 ,且至少有,且至少有一个等式不成立。这时,若令一个等式不成立。这时,若令 (2.3.11) 必有必有 ,且,且Q Q和和q q同号。同号。 88纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕
77、)(汪贤裕)89不存在策略占优时纳什均衡的求解(续)局中人局中人2 2的支付矩阵的支付矩阵B B中,有:中,有: ,且至,且至少有一个等式不成立;或少有一个等式不成立;或 ,且至少有,且至少有一个等式不成立。这时,若令一个等式不成立。这时,若令 (2.3.12) 必有必有 ,且,且R R和和r r同号。同号。89纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)90不存在策略占优时纳什均衡的求解(续)此时令此时令 分别表示局中人分别表示局中人1 1和和2 2的混的混合策略,其中合策略,其中 博弈的混合策略
78、局势由一对数博弈的混合策略局势由一对数 确定。确定。 分别表示局中人分别表示局中人1 1,2 2在上述混合策略在上述混合策略 下得到的期望支付。下得到的期望支付。90纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)91不存在策略占优时纳什均衡的求解(续)由定理由定理2.3.12.3.1可知,可知, 是博弈的平衡点的充要条件是是博弈的平衡点的充要条件是 (2.3.132.3.13) (2.3.142.3.14) (2.3.152.3.15) (2.3.162.3.16)91纳什均衡四川大学课件博弈论及其纳
79、什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)92 设双矩阵博弈局中人设双矩阵博弈局中人1 1,2 2的支付矩阵分别为:的支付矩阵分别为:设局中人设局中人1 1的混合策略为:的混合策略为:设局中人设局中人1 1的混合策略为:的混合策略为:简记混合策略组合为(简记混合策略组合为( x, y x, y )。则局中人)。则局中人1 1的期望收益为:的期望收益为:不存在策略优超时纳什均衡的求解(续)92纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)
80、93(2.3.132.3.13)式为:)式为:(2.3.14(2.3.14)式为:)式为:不存在策略优超时纳什均衡的求解(续)93纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)94 不存在策略优超时纳什均衡的求解(续) 由于由于 ,因此,因此(2.3.13),(2.3.14)式展开并化简后变为式展开并化简后变为 (2.3.17) (2.3.18) 其中其中: : 94纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤
81、裕)95不存在策略优超时纳什均衡的求解(续) 由于由于 ,满足(,满足(2.3.172.3.17)和()和(2.3.182.3.18)式的应)式的应满足:满足: (2.3.19)95纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)96 简记混合策略组合为(简记混合策略组合为( x, y x, y )。则局中人)。则局中人2 2的期望收益为:的期望收益为:96纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)97(2
82、.3.15)式为:(2.3.16)式为:97纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)98 不存在策略占优时纳什均衡的求解(续) 类似地,令类似地,令 则则(2.3.15),(2.3.16)简化为简化为 (2.3.202.3.20) (2.3.212.3.21) 98纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)99不存在策略占优时纳什均衡的求解(续)同样由于同样由于 ,满足,满足(2.3.20)和和(2
83、.3.21)式的应满足式的应满足 (2.3.22) 将将(2.3.18)和和(2.3.22)结合起来,就得到结合起来,就得到 双矩阵博弈在双矩阵博弈在不存在占优策略情形下纳什均衡点,相应的计算不存在占优策略情形下纳什均衡点,相应的计算 和和 ,则可得到对应的纳什均衡结果。,则可得到对应的纳什均衡结果。99纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)100例2.3.1 一般双矩阵博弈设双矩阵博弈中局中人1,2的支付矩阵分别为:下面求该博弈的混合策略下的纳什均衡结果。100纳什均衡四川大学课件博弈论及其
84、纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)101例2.3.1 一般双矩阵博弈(续)由:101纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)102例2.3.1 一般双矩阵博弈(续)两个不等式作图:102纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)103例2.3.1 一般双矩阵博弈(续)结论有唯一点 满足两个不等式组。则该博弈的纳什均衡为对应的
85、均衡结果为:103纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)104例2.3.2 含一个参数a的 22双矩阵博弈设双矩阵博弈局中人设双矩阵博弈局中人1 1,2 2的支付矩阵分别为:的支付矩阵分别为:104纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)105例2.3.2含一个参数a的 22双矩阵博弈(续) 当当 时,时,局中人局中人1 1的第一个策略相对于第二策的第一个策略相对于第二策略是严格劣策略,局中人略
86、是严格劣策略,局中人1 1会选择第二个策略。由于理会选择第二个策略。由于理智的局中人智的局中人2 2同样可以分析出局中人同样可以分析出局中人1 1的这一选择,因此的这一选择,因此,他会选择第二个策略。此时博弈的纳什均衡点为,他会选择第二个策略。此时博弈的纳什均衡点为(0,1),(),(0,1),),均衡结果为(均衡结果为(1 1,2 2)。)。 当当 时时,博弈中不存在占优策略,因此我们,博弈中不存在占优策略,因此我们使用一般方法。使用一般方法。105纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)10
87、6例2.3.2(续) 由由 , 得得 图2.3.1 时的纳什均衡 106纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)107例2.3.2(续)该博弈有该博弈有三个纳什均衡点:O O:(:((0 (0,1) 1),(0 (0,1) 1)),),WW:(:((1 (1,0) 0),(1 (1,0) 0)),), MM: 107纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)108例2.3.2(续)其其均衡结果均衡结
88、果分别是:分别是:对第一个纳什均衡点对第一个纳什均衡点O:(0,1),(0,1),均衡结果为均衡结果为(1,2)对第二个纳什均衡点对第二个纳什均衡点W:(1,0),(1,0),均衡结果为(均衡结果为(a,1)对第三个纳什均衡点对第三个纳什均衡点M: 均衡结果为:均衡结果为: 108纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)109例2.3.2(续) 当当 时,时, (2.3.25) 又又 (2.3.26)109纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)
89、博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)110例2.3.2(续)同样,将(同样,将(2.3.252.3.25)和()和(2.3.262.3.26)分别作下图)分别作下图: :图图2.3.2 时的纳什均衡时的纳什均衡 110纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)111例2.3.1(续) 同时满足(同时满足(2.3.252.3.25)和()和(2.3.262.3.26)的点对)的点对 为为OO点和线点和线段段MNMN,则此时,则此时纳什均衡纳什均衡为:为: 前一个的前一个的均衡结果均衡结
90、果为(为(1 1,2 2),后一类均衡为:),后一类均衡为:111纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)112例2.3.3 小偷与守卫的博弈 由于对博弈论有卓越贡献而成为由于对博弈论有卓越贡献而成为19941994年诺贝尔经济学奖获得年诺贝尔经济学奖获得者的泽尔顿教授,者的泽尔顿教授,19961996年年3 3月在上海的一次演讲中,举了这个小月在上海的一次演讲中,举了这个小偷与守卫之间博弈的例子。故事的背景是这样的:一守卫看守一偷与守卫之间博弈的例子。故事的背景是这样的:一守卫看守一个仓库,一
91、小偷要在夜晚去偷仓库的东西。但是守卫有可能晚上个仓库,一小偷要在夜晚去偷仓库的东西。但是守卫有可能晚上睡觉也可能不睡,如果守卫睡觉,小偷偷窃就会成功,他将获得睡觉也可能不睡,如果守卫睡觉,小偷偷窃就会成功,他将获得正效用正效用V V,而守卫由于失职,他将获得负效用,而守卫由于失职,他将获得负效用DD;而守卫如果;而守卫如果不睡,守卫能抓住小偷,小偷将获得负效用不睡,守卫能抓住小偷,小偷将获得负效用P P;而小偷也有可;而小偷也有可能不去偷,那样守卫如果睡觉,他获得正效用能不去偷,那样守卫如果睡觉,他获得正效用S S。 112纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用
92、(汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)113例2.3.3 小偷与守卫的博弈(续) 守卫有睡和不睡两种策略选择,小偷也有偷和守卫有睡和不睡两种策略选择,小偷也有偷和不偷两种策略选择,各自收益矩阵如下:不偷两种策略选择,各自收益矩阵如下:表表2.3.1 2.3.1 小偷与守卫的收益矩阵小偷与守卫的收益矩阵 不存在占优策略不存在占优策略113纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)114小偷与守卫的博弈(续) 由由 得得 (2.3.27) 由由 得得 (2.3.28)图
93、图2.3.3 小偷与守卫的纳什均衡点小偷与守卫的纳什均衡点 114纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)115小偷与守卫的博弈(续) 混合策略的纳什均衡点混合策略的纳什均衡点 小偷将以小偷将以 的概率偷,以的概率偷,以 的概率不偷;守卫的概率不偷;守卫以以 的概率去睡觉,以的概率去睡觉,以 的概率不睡觉。的概率不睡觉。 115纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1162.4 矩阵博弈 2.4
94、.1 2.4.1 矩阵博弈矩阵博弈 2.4.2 2.4.2 保守策略与纳什均衡保守策略与纳什均衡 2.4.3 2.4.3 混合策略纳什均衡混合策略纳什均衡 2.4.4 2.4.4 矩阵博弈的求解矩阵博弈的求解116纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1172.4.1 矩阵博弈 定义定义2.4.1 2.4.1 矩阵博弈矩阵博弈 矩阵博弈保守支付值寻求的思路矩阵博弈保守支付值寻求的思路 定理定理2.4.1 2.4.1 两个保守支付值的关系两个保守支付值的关系117纳什均衡四川大学课件博弈论及其纳
95、什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)118定义2.4.1 矩阵博弈 对于博弈对于博弈 的三要素中,满足下列三条件的称为的三要素中,满足下列三条件的称为矩阵博弈矩阵博弈。 局中人集局中人集 ; 局中人局中人1 1有有限个策略组成的有有限个策略组成的策略集策略集 ,局中人,局中人2 2有有限有有限个策略组成的个策略组成的策略集策略集 ; 任取任取 ,任取,任取 ,则,则 构成一个策略组合。构成一个策略组合。 对于一个策略组合对于一个策略组合 ,局中人,局中人1 1的的支付支付为为 ,局中人,局中人2 2的的支付支付为为 ,且满
96、足:,且满足: , 。 118纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)119定义2.4.1 矩阵博弈(续) 由于两个局中人的策略数都是有限的,并且对任意策由于两个局中人的策略数都是有限的,并且对任意策略组合略组合 两人的支付的和为两人的支付的和为0 0,则矩阵博弈又,则矩阵博弈又称为称为二人有限零和博弈二人有限零和博弈。二人有限零和博弈二人有限零和博弈119纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)
97、120矩阵博弈保守支付值寻求的思路 一般地,如果局中人一般地,如果局中人1 1采用他的第采用他的第 个策略,则局中个策略,则局中人人1 1至少可以得到支付为至少可以得到支付为 , 这就是支付矩阵第这就是支付矩阵第 行元素中的最小元素。由于局中行元素中的最小元素。由于局中人人1 1希望所得到越大越好,因此,他可以选择希望所得到越大越好,因此,他可以选择 使上使上式为最大。这就是说,局中人式为最大。这就是说,局中人1 1可以选择可以选择 ,使他得到,使他得到的支付不少于的支付不少于 (2.4.1) 120纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈
98、论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)121矩阵博弈保守支付值寻求的思路 同样,如果局中人同样,如果局中人2 2采用他的第采用他的第 个策略,由于局中人个策略,由于局中人1 1希望希望支付值越大越好,则局中人支付值越大越好,则局中人2 2至多失去至多失去 这是支付矩阵第列的最大元素。由于局中人这是支付矩阵第列的最大元素。由于局中人2 2希望支付值越希望支付值越小越好,因此,他可以选择使上式为最小。这就是说,局中人小越好,因此,他可以选择使上式为最小。这就是说,局中人2 2可以选择,保证他失去的不大于可以选择,保证他失去的不大于 (2.4.2) 也可以说,如果局中人也可以说,如果局中人2
99、 2处理得当,局中人处理得当,局中人1 1得到的支付不得到的支付不会大于(会大于(2.4.22.4.2)中的值。)中的值。121纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)122定理2.4.1 两个保守支付值的关系 矩阵博弈矩阵博弈A A中,中, ,则:,则: (2.4.3) 定理定理2.4.12.4.1证明证明 122纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)123定理2.4.1证明 对于每一个对于每
100、一个 ,有,有 对于每一个对于每一个 ,有,有 因此,对于任意的因此,对于任意的 和任意的和任意的 ,有,有 上式不等号右边对任意上式不等号右边对任意 都成立,则有都成立,则有 上式不等号左边对任意都成立,则有上式不等号左边对任意都成立,则有 以上就是需证的(以上就是需证的(2.4.32.4.3)式。)式。 123纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1242.4.2 保守策略与纳什均衡 定义定义2.4.2 2.4.2 保守策略集保守策略集 例例2.4.1 2.4.1 定理定理2.4.2 2.
101、4.2 纯策略纳什均衡点存在的充分必要条件纯策略纳什均衡点存在的充分必要条件 例例2.4.2 2.4.2 124纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)125保守策略集的定义 在矩阵博弈在矩阵博弈A A中,中, ,令:,令: (2.4.4) (2.4.5)则则 和和 分别为局中人分别为局中人1 1和和2 2的的保守策略集保守策略集。125纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)126例2.4.1
102、有矩阵博弈有矩阵博弈 保守策略的计算过程如表保守策略的计算过程如表. . 则则 126纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)127例2.4.1(续) 很显然,矩阵博弈中,局中人的保守策略一定存在,很显然,矩阵博弈中,局中人的保守策略一定存在,但局中人采取保守策略集中的策略组合但局中人采取保守策略集中的策略组合 ,不能,不能实现博弈的稳定和均衡。如例实现博弈的稳定和均衡。如例2.4.12.4.1中,当局中人中,当局中人1 1取保取保守策略守策略 ,局中人,局中人2 2取保守策略取保守策略 就对局
103、中人就对局中人1 1不不利。利。127纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)128矩阵博弈的纯策略纳什均衡 由定义由定义2.2.12.2.1,矩阵博弈的纯策略纳什均衡是指满足,矩阵博弈的纯策略纳什均衡是指满足下式的策略组合:下式的策略组合: (2.4.6) 与一般博弈一样,矩阵博弈的纯策略纳什均衡点与一般博弈一样,矩阵博弈的纯策略纳什均衡点可能不存在,例如上例可能不存在,例如上例2.4.12.4.1。128纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕
104、)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)129定理 2.4.2 矩矩阵阵博博弈弈中中,纯纯策策略略纳纳什什均均衡衡点点存存在在的的充充分分必必要条件为:要条件为: (2.4.72.4.7) 定理的证明定理的证明 129纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)130定理2.4.2的证明充分性:充分性:若(若(2.4.72.4.7)式成立,即)式成立,即 。必有一个。必有一个 和和 ,使使 和和 所以所以 但但 于是有于是有 。 因此,对一切因此,对一切 和一切和一切 ,有(,有(2.4
105、.62.4.6)式成立)式成立 130纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)131定理2.4.2的证明(续)必要性必要性: 设设 是博弈的纳什均衡点,则对于一切是博弈的纳什均衡点,则对于一切 和和 都都有有 (2.4.8) 由(由(2.4.82.4.8)式左边的不等式有)式左边的不等式有 因而因而 (2.4.9)同理,由(同理,由(2.4.82.4.8)式右边的不等式有)式右边的不等式有 (2.4.10)由,(由,(2.4.92.4.9)和()和(2.4.102.4.10)式得到)式得到由定理
106、由定理2.4.12.4.1反方向的不等式成立,因此反方向的不等式成立,因此 。 131纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)132例2.4.2 有下列矩阵博弈有下列矩阵博弈 则则纯策略纳什均衡纯策略纳什均衡为为 。同时。同时保守策略保守策略为为 。132纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)133小结在任意一个n人非合作博弈中,每个局中人都可以定义自身的保守策略和对应的保守策略下的收益。但由各
107、局中人的保守策略组成的策略组合一般是无稳定性的,因此也不是博弈论中讨论的重点,但在有的情况中保守策略仍是有用的。例如在4.3中,谈判解的初始点可以用保守策略下的收益来确定,详见(4.3.1)和(4.3.2)式。133纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1342.4.3 混合策略纳什均衡 定理定理2.4.3 2.4.3 混合策略纳什均衡点存在的充分必要条件混合策略纳什均衡点存在的充分必要条件 定理定理2.4.4 2.4.4 不同纳什均衡点的均衡结果相同不同纳什均衡点的均衡结果相同 定义定义2.
108、4.3 2.4.3 博弈的值博弈的值 定理定理2.4.5 2.4.5 矩阵博弈混合策略博弈的值矩阵博弈混合策略博弈的值134纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)135定理2.4.3 矩矩阵阵博博弈弈A A中中, ,混合策略纳什均衡点存在的充分必要条件为:的充分必要条件为: 135纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)136定理2.4.4 在矩阵博弈在矩阵博弈A A中,设中,设 和和 分别都分
109、别都 是纳什均衡点,则是纳什均衡点,则 。 定理定理2.4.42.4.4的证明的证明 136纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)137定理2.4.4的证明 由于由于 和和 分别都是矩阵分别都是矩阵A A的纳什均衡,则由的纳什均衡,则由(2.4.12)式,得式,得 (2.4.14) (2.4.15) 所以所以 (2.4.16) 式中,第一个不等号来自(式中,第一个不等号来自(2.4.142.4.14)中后一个不等号,第二个)中后一个不等号,第二个不等号来自(不等号来自(2.4.152.4.15
110、)中前一个不等号,第三个不等号来自)中前一个不等号,第三个不等号来自(2.4.152.4.15)中后一个不等号,)中后一个不等号,第四个不等号来自(个不等号来自(2.4.142.4.14)中前)中前一个不等号。一个不等号。 由(由(2.4.162.4.16)式,显然)式,显然 137纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)138定义2.4.3 博弈的值博弈的值 在矩阵博弈在矩阵博弈A A中,其唯一的均衡结果称为中,其唯一的均衡结果称为 该该博弈的值,记为记为 或或 。138纳什均衡四川大学课件博
111、弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)139定理2.4.5 在矩阵博弈在矩阵博弈G G中,若中,若 , ,局中人,局中人1 1的收益函数为,则的收益函数为,则 (2.4.17) (2.4.18) 引理引理139纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)140引理1 1)设有一个)设有一个 维数组维数组 , ,并设并设 ,则,则 (2.4.19) 2 2)设有一个)设有一个 维数组维数组 , ,并设并设 ,则,则 (2.
112、4.20)1 1)的证明)的证明2 2)的证明与)的证明与1 1)的相似)的相似 140纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)141引理1)的证明 假定假定 则则 因而对每一个因而对每一个 ,有,有 将上面将上面 个不等式相加,有个不等式相加,有 因此,因此, (2.4.21) 另一方面,另一方面, 是一个特殊的混合策略,其中第是一个特殊的混合策略,其中第 个分量为个分量为1 1。我们有。我们有 (2.4.22) 由(由(2.4.212.4.21)和()和(2.4.222.4.22)可知,)可
113、知, 141纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)142定理2.4.6 设设 和和 是两个矩阵博弈,其中局中人是两个矩阵博弈,其中局中人1 1和和局中人局中人2 2在在 和和 中有相同的策略集,局中人中有相同的策略集,局中人1 1的支付函数分别为的支付函数分别为 和和 ,其中,其中, , , 是一个不变常数。则矩阵博弈是一个不变常数。则矩阵博弈 和和 有相同的纳什均衡点,且有相同的纳什均衡点,且 。142纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)
114、博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1432.4.4 矩阵博弈的求解 2.4.4.1 2.4.4.1 策略优超与重复剔除劣策略策略优超与重复剔除劣策略 2.4.4.2 2.4.4.2 图解法图解法 2.4.4.3 2.4.4.3 线性规划法线性规划法143纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1442.4.4.1 策略优超与重复剔除劣策略 策略优超与弱优超策略优超与弱优超 重复剔除劣策略重复剔除劣策略 例例2.4.12.4.1144纳什均衡四川大学课件博弈论及其纳什均衡四川大学课
115、件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)145策略优超与弱优超 对矩阵博弈对矩阵博弈G G,令局中人,令局中人1 1的收益矩阵为的收益矩阵为 ,当,当 (2.4.23) 我们称局中人我们称局中人1 1的策略的策略 优超优超策略策略 ,或称局中人,或称局中人1 1的策的策略略 被被策略策略 优超优超。若(。若(2.4.232.4.23)中的严格不等号换成)中的严格不等号换成“”“”,则相应的称为局中人,则相应的称为局中人1 1的策略的策略 弱优超弱优超策略策略 ,或称,或称局中人局中人1 1的策略的策略 被被策略策略 弱优超弱优超。 当当 (2
116、.4.24) 我们称局中人我们称局中人2 2的策略的策略 优超优超策略策略 ,或称局中人,或称局中人2 2的策的策略略 被被策略策略 优超优超。若(。若(2.4.242.4.24)中的严格不等号换成)中的严格不等号换成“”“”,则相应的称为局中人,则相应的称为局中人2 2的策略的策略 弱优超弱优超策略策略 ,或称,或称局中人局中人2 2的策略的策略 被被策略策略 弱优超弱优超。145纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)146重复剔除劣策略 类似于双矩阵博弈中类似于双矩阵博弈中重复剔出劣策略重
117、复剔出劣策略的方法,我们可以在矩的方法,我们可以在矩阵博弈中重复剔出被优超的策略,简化矩阵博弈,或直接求出矩阵博弈中重复剔出被优超的策略,简化矩阵博弈,或直接求出矩阵博弈中的纳什均衡。而对被剔出的策略,它在原博弈混合策略阵博弈中的纳什均衡。而对被剔出的策略,它在原博弈混合策略纳什均衡点中(这里是两个向量纳什均衡点中(这里是两个向量 和和 ),对应的分量为零。),对应的分量为零。 由于在矩阵博弈由于在矩阵博弈G G中,博弈的值中,博弈的值 是唯一的,若我们只需是唯一的,若我们只需要要求矩阵博弈求矩阵博弈G G的值的值 时,可以在重复剔除被优超策略时,考时,可以在重复剔除被优超策略时,考虑使用虑使
118、用弱优超去剔除弱优超去剔除被弱优超的策略。被弱优超的策略。146纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)147例2.4.1设有矩阵博弈设有矩阵博弈GG,其局中人,其局中人1 1的收益矩阵的收益矩阵A A如下:如下:采用重复剔除被优超策略的方法,可以将博弈采用重复剔除被优超策略的方法,可以将博弈GG简化如下:简化如下: 在最右边的矩阵中,第一行对应着局中人1的第二个策略,第二行对应着局中人1的第三个策略;第一列对应着局中人2的第一个策略,第二列对应着局中人2的第四个策略。147纳什均衡四川大学课件
119、博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)148例例2.4.12.4.1(续)(续) 在简化后的博弈在简化后的博弈 中,局中人中,局中人1 1的收益矩阵为的收益矩阵为 其其混合策略纳什均衡点点 ,分别为,分别为 博弈博弈 的的值 。 原博弈原博弈G G的的混合策略纳什均衡点点 : , 。博弈。博弈 的的值 。 148纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1492.4.4.2 图解法 2.4.4.2.1 A2.4.4.
120、2.1 A为为2n2n矩阵矩阵 2.4.4.2.2 A2.4.4.2.2 A为为m2m2矩阵矩阵 2.4.4.2.3 A2.4.4.2.3 A为为2222矩阵矩阵149纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1502.4.4.2.1 A为2n矩阵以局中人以局中人1 1的收益矩阵的收益矩阵A A为为2323矩阵为例矩阵为例 设局中人设局中人1 1采用混合策略采用混合策略 ,这里,这里 。根。根据定理据定理2.4.52.4.5中(中(2.4.172.4.17)式有:)式有: (2.4.25) 其中其
121、中 (2.4.26) 150纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1512.4.4.2.1 A为2n矩阵(续) 可在平面上作三条直线(见下图),分别代表局中可在平面上作三条直线(见下图),分别代表局中人人2 2在采用三个纯策略在采用三个纯策略 时,局中人时,局中人1 1采用混合采用混合策略策略 时的收益。由(时的收益。由(2.4.262.4.26)式图中的粗的折)式图中的粗的折线,则是线,则是 的图像。的图像。 151纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤
122、裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1522.4.4.2.1 A为2n矩阵(续) 由(由(2.4.252.4.25)式,可在图中找出当)式,可在图中找出当 在在S S点,达到最大值点,达到最大值KSKS。则则S S点坐标点坐标 为局中人为局中人1 1的混合策略纳什均衡点的混合策略纳什均衡点 。而而K K点的纵坐标即为博弈的值点的纵坐标即为博弈的值 。由于局中人。由于局中人1 1的纳什均衡的纳什均衡点与局中人点与局中人2 2的策略的策略 无关这是因为无关这是因为K K点为策略点为策略 和策略和策略 决定的两条直线的交点,因此只要求解下面由和所在列组成的决定的两条直线的
123、交点,因此只要求解下面由和所在列组成的化简的矩阵博弈化简的矩阵博弈 : 就能得出局中人就能得出局中人2 2的混合策略纳什均衡点。的混合策略纳什均衡点。152纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1532.4.4.2.2 A为m2矩阵以局中人以局中人1 1的收益矩阵的收益矩阵A A为为3232的矩阵为例。的矩阵为例。 设局中人设局中人2 2采用混合策略采用混合策略 , 这里这里 ,根据定理,根据定理2.4.52.4.5中(中(2.4.182.4.18)式有:)式有: (2.4.27) 其中:其中
124、: (2.4.28)153纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1542.4.4.2.2 A为m2矩阵(续) 按上面类似方法,按上面类似方法,可作的图像为下图中粗的折线。可作的图像为下图中粗的折线。 图图2.4.2 322.4.2 32矩阵博弈的图解法矩阵博弈的图解法 由由(2.4.27)式,可在图中找出当式,可在图中找出当 在在S S点,点, 达到最小值达到最小值KSKS。则则S S点坐标点坐标 决定局中人决定局中人2 2的混合策略纳什均衡点的混合策略纳什均衡点 。而。而K K点的纵坐标即为
125、博弈的值点的纵坐标即为博弈的值 。对局中人。对局中人1 1的纳什均衡点的寻求,的纳什均衡点的寻求,类同类同A A为为2n2n的矩阵的方法。的矩阵的方法。 154纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1552.4.4.2.3 A为22矩阵 设矩阵博弈设矩阵博弈G G中,局中人中,局中人1 1的收益矩阵的收益矩阵A A为:为: 当不存在优超和弱优超时,通过当不存在优超和弱优超时,通过A A的两行或两列互换,也就是对的两行或两列互换,也就是对通过局中通过局中1 1或或2 2的两个策略的编号互换,我们
126、不难发现,只需考虑的两个策略的编号互换,我们不难发现,只需考虑以下情况:以下情况: 这时,矩阵博弈这时,矩阵博弈G G只有混合策略下的纳什均衡。只有混合策略下的纳什均衡。 设设 和和 分别为局中人分别为局中人1 1和和2 2的混合策略,其中,的混合策略,其中, 由图解法,可作图由图解法,可作图2.4.32.4.3,见下页。,见下页。155纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1562.4.4.2.3 A为22矩阵(续) 用图解法的求解过程,我们有:用图解法的求解过程,我们有: (2.4.29)
127、 (2.4.30) (2.4.31) 相应的博弈相应的博弈G G的的纳什均衡纳什均衡点点为:为: ,博弈的值博弈的值为为 156纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)1572.4.4.3 线性规划法 矩阵博弈可用线性规划法求解矩阵博弈可用线性规划法求解 例例2.4.4 2.4.4 157纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)158矩阵博弈可用线性规划法求解 若矩阵博弈若矩阵博弈G G中,局中人
128、中,局中人1 1的收益矩阵为的收益矩阵为 设局中人设局中人1 1的混合策略为的混合策略为 。由定理。由定理2.4.52.4.5的结论的结论得得 (2.4.32) 令令 ,则(,则(2.4.322.4.32)式可记为下列)式可记为下列数学规划问题 s.t. s.t. (2.4.33) 158纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)159矩阵博弈可用线性规划法求解(续)若若 ,令,令 ,则(,则(2.4.332.4.33)中的约束方程为:)中的约束方程为: 令令 ,于是数学规划(,于是数学规划(2.
129、4.332.4.33)可以写成下列线性规划)可以写成下列线性规划 s.t. s.t. (2.4.34) 159纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)160矩阵博弈可用线性规划法求解(续) 对线性规划(对线性规划(2.4.342.4.34)式求得最优解和最优值,可)式求得最优解和最优值,可推算出推算出纳什均衡点和博弈的值纳什均衡点和博弈的值 : (2.4.35)160纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)
130、(汪贤裕)161矩阵博弈可用线性规划法求解(续)对局中人对局中人2 2的纳什均衡策略讨论。的纳什均衡策略讨论。 局中人局中人2 2的混合策略为的混合策略为 用定理用定理2.4.5的结论,的结论, 同样可推导等价的线性规划为同样可推导等价的线性规划为 (2.4.36) 设设(2.4.36)的最优解为的最优解为 最优解最优解 则原博弈中局中人则原博弈中局中人2 2的的 纳什均衡点和博弈的值纳什均衡点和博弈的值 分别为:分别为:显然显然,(2.4.34)和和(2.4.37)是两个互为是两个互为对偶的线性规划对偶的线性规划,因此,因此 。即她们求得博弈的值是相同的。即她们求得博弈的值是相同的 161纳
131、什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)162例2.4.4 有一农户在大春生产时,有三种水稻品种有一农户在大春生产时,有三种水稻品种A,B,CA,B,C供选用。供选用。 三种品种对气候的要求各不同。三种品种对气候的要求各不同。 该农户也可以将土地出租,该农户也可以将土地出租, 而直接获得一笔稳定收入。而直接获得一笔稳定收入。 当年的气象预报非常不清楚,当年的气象预报非常不清楚, 可能是:多雨水,正常,干旱三种情况。可能是:多雨水,正常,干旱三种情况。 不同情况下,农户一亩地的收益如表不同情况下,农
132、户一亩地的收益如表 (单位百元)。(单位百元)。 若农户采用安全思想出发,应如何安排生产,最低保障收益是多少?若农户采用安全思想出发,应如何安排生产,最低保障收益是多少? 例例2.442.44求解过程求解过程162纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)博弈论及其应用博弈论及其应用 (汪贤裕)(汪贤裕)163例2.4.4的求解 该问题是农户与该问题是农户与“气候气候”进行二人零和博弈。农户为局中人进行二人零和博弈。农户为局中人1 1,而而“气候气候”为局中人为局中人2 2。 上表列出数值是局中人上表列出数值是局中人1 1的收益矩阵。的收益矩阵。
133、 该博弈该博弈G G中,局中人中,局中人1 1的收益矩阵的收益矩阵A A为为 使用上述线性规划方法可求得使用上述线性规划方法可求得 矩阵博弈的矩阵博弈的纳什均衡点纳什均衡点 博弈的值博弈的值 。 农户的安全策略即为局中人农户的安全策略即为局中人1 1的纳什均衡点。农户将对土地用的纳什均衡点。农户将对土地用 用于品种用于品种A,A,对土地的对土地的 用于品种用于品种B, B, 对土地的对土地的 用于品种用于品种C,C,不出租土地。不出租土地。 此策略保障每亩土地的最低收益为此策略保障每亩土地的最低收益为4.064.06百元。百元。163纳什均衡四川大学课件博弈论及其纳什均衡四川大学课件博弈论及其应用应用 (汪贤裕)(汪贤裕)