第3章混合战略Nash均衡.ppt
《第3章混合战略Nash均衡.ppt》由会员分享,可在线阅读,更多相关《第3章混合战略Nash均衡.ppt(102页珍藏版)》请在三一办公上搜索。
1、第一部分:完全信息静态博弈,第三章混合战略Nash均衡,主要内容:一、混合战略;二、混合战略Nash均衡;三、混合战略Nash均衡的求解。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,主要内容:一、混合战略;二、混合战略Nash均衡;三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,一、混合战略,“猜硬币”博弈 两个参与人各握有一枚硬
2、币,双方同时选择是正面向上(记作O)还是背面向上(记作R),即他们的战略空间都是O,R。若两枚硬币是一致的(即全部背面向上或者全部正面向上),参与人2赢得参与人1的硬币;若两枚硬币不一致,则参与人1赢得参与人2的硬币。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,猜硬币博弈的特征:每位参与人都想猜透对方的战略,而每位参与人又都不能让对方猜透自己的
3、战略。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,在“猜硬币”游戏中,我们会以50%的概率选择正面(O),以50%的概率选择反面(R)。像这种以一定的概率分布来选择自己战略的行为,在博弈论中称之为混合战略(mixed strategy)。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,纯战略:参与人在给定信息下只选择一种特定战略(或行动)。,Control Science and Engi
4、neering,HUST All Rights Reserved,2007,Luo Yunfeng,混合战略:参与人给定信息下以某种概率分布随机地选择不同的行动。它可以定义为战略空间(集)上概率分布。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定义1:混合战略,在博弈 中,对任一参与人i,设,则参与人i的一个混合战略为定义在战略集 上的一个概率分布 其中 表示参与人i选择战略 的概率,即 满足:,Control Science and Engineering,HUST All Rights
5、 Reserved,2007,Luo Yunfeng,混合战略解释了一个参与人对其他参与人所采取的行动的不确定性,它描述了参与人在给定信息下以某种概率分布随机地选择不同的行动或战略。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,200
6、7,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,支付,1)纯战略时,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,2)混合战略时:其中,为参与人j采取中 的概率,表示 发生的概率。,Control Science and
7、Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,其中,,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and
8、Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,看下面的例子:,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,参与人1 的混合战略 参与人2 的混合战略;在混合战略组合 下,战略组合、和 出现的概率就分别为。,Control Science and Engineering,HUST All
9、 Rights Reserved,2007,Luo Yunfeng,参与人1采用纯战略a1和a2的期望效用分别为参与人1在混合战略组合=(1,2)下的期望效用为,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,参与人2采用纯战略b1和b2的期望效用分别为参与人2在混合战略组合=(1,2)下的期望效用为,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,主要内容:一、混合战略;二、混合战略Nash均衡
10、;三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,二、混合战略Nash均衡,提一个问题:在“猜硬币”游戏中,我们往往会以50%的概率选择正面(O),以50%的概率选择反面(R),即选择混合战略=(0.5,0.5)。那么有没有参与人会偏离混合战略i=(0.5,0.5)呢?,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,在“猜硬币”博弈中
11、,当双方都选择混合战略 i=(0.5,0.5)时,双方的期望收益都为0。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,如果参与人1保持混合战略1=(0.5,0.5),那么无论参与人2选择其它什么样的混合战略,只要参与人1保持混合战略1=(0.5,0.5)不变,参与人2的期望收益都为0,不会增大。也就是说,偏离并不能给参与人2带来好处。同理,偏离也不能给参与人1带来好处。,Control Science and Engineering,HUST All Rights Reserved,2007
12、,Luo Yunfeng,因此,在“猜硬币”博弈中,双方都不会偏离混合战略组合=(0.5,0.5),(0.5,0.5)。像这样的混合战略组合我们称之为混合战略Nash均衡。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定义2:混合战略Nash均衡,在博弈 中,混合战略组合 为一个Nash均衡,当且仅当。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and E
13、ngineering,HUST All Rights Reserved,2007,Luo Yunfeng,对简单的博弈问题,容易根据定义判断出Nash均衡。但对于一些复杂的博弈问题,要找到Nash均衡尤其是混合战略Nash均衡是非常不容易的。为了求解混合战略Nash均衡,必须了解在选择混合战略的情况下,参与人如何剔除劣战略以及参与人最优混合战略的特性。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,参与人i的最优混合战略的构成:给定其他参与人的选择-i,假设 为参与人i的最优混合战略,那么 有
14、,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,命题1,在参与人的最优混合战略 中,对,有,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,无论参与人1的选择1=(p,1-p)如何,参与人2选择2=(0.5,0.5,0)的所得为2.5,大于选择的所得2。所以,2=(0.5,0.5,0)相对于b3占优,也就是说,在参与人可以选择混合战略的情况下,b3成为劣战略。,Control Science a
15、nd Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,在“猜硬币”游戏中,设参与人1的战略 为,参与人2的战略为 参与人1选择正面(O)的期望收益为参与人1选择反面(R)的期望收益为,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,由于当且仅当 时,因此,当 时,参与人l的最优纯战略为选择正面(O);当 时选择反面(R)。而当 时,参与人1无论选择正面(O)还是反面(R)都是无差异的。不仅如此,参与人1此时无论以什么样的概率分布选择正面
16、(O)和反面(R)都是无差异的。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,给定参与人2的战略 的情况下,参与人1的最优反应 参与人1的期望收益在2-4q0时随p递增;在2-4q0时随p递减,因此,当 时,参与人1的最优反应(即选择正面);当,参与人1的最优反应(即选择反面)。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,Control Science and Engineering,H
17、UST All Rights Reserved,2007,Luo Yunfeng,可得参与人1的最优反应 为:为参与人1的最优反应响应(best correspondence),而不是最优反应函数。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,支集:对于给定的参与人的混合战略i,称i中所有大于0的分量所对应的纯战略的集合为i的支集(记为),即,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,定
18、理1:最优反应的引理,在有限n人战略式博弈 中,混合战略组合 为一个Nash均衡,当且仅当,的支集 中每一个纯战略都是给定 下的最优反应。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,可以根据最优反应引理求解两人两战略的战略式博弈的Nash均衡等值法。例如:,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,根据最优战略的性质,有即,Control Science and Engineering
19、,HUST All Rights Reserved,2007,Luo Yunfeng,求解上式可得其中,。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,通过划线法可知下图所示博弈不存在纯战略Nash均衡。假设参与人1的混合战略为(p,1-p)参与人2的混合战略为(q,1-q)。利用式(1)可得利用等值法同样可以得到 的结果,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,根据等值法得,即,求解
20、上式可得,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,通过划线法可知下图所示博弈存在纯战略Nash均衡(U,L),(D,R)。假设参与人1的混合战略为(p,1-p)参与人2的混合战略为(q,1-q)。利用式(1)可得利用等值法同样可以得到 的结果,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,根据等值法得,即,求解上式可得,Control Science and Engineering,HU
21、ST All Rights Reserved,2007,Luo Yunfeng,Wilson奇数定理(oddness theorem),Wilson奇数定理:几乎所有的有限战略式博弈都有有限奇数个Nash均衡。注意,Wilson奇数定理并没有肯定在任何情况下都有有限奇数个Nash均衡,在某些情况下仍有可能存在偶数个Nash均衡。,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,主要内容:一、混合战略;二、混合战略Nash均衡;三、混合战略Nash均衡的求解。,第三章混合战略Nash均衡,Cont
22、rol Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,三、混合战略Nash均衡的求解,支撑求解法;规划求解法;,Control Science and Engineering,HUST All Rights Reserved,2007,Luo Yunfeng,1.支撑求解法,对于给定的有限n人战略式博弈 假设混合战略组合 为Nash均衡,考察 的支撑,对,设,不失一般性,设,则参与人关于混合战略组合 的支集,Control Science and Engineering,HUST All Rights Res
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 混合 战略 Nash 均衡
链接地址:https://www.31ppt.com/p-6358637.html