混合策略纳什均衡.ppt

第三讲 混合策略纳什均衡,主讲人：李美娟,引言,有些博弈不存在纳什均衡，或者纳什均衡不唯一，如猜硬币博弈，前述纳什均衡分析就无法对博弈方的选择和博弈结果作明确的预测。 这部分对不存在纳什均衡和存在多个纳什均衡的博弈作一些讨论。,混合策略的引进,一、扑克牌对色游戏,（1）不存在前面定义的纳什均衡策略组合。 （2）关键是不能让对方猜到自己将选择的策略。 这类博弈很多，引出混合策略纳什均衡概念。,混合策略的相关概念,混合策略是一种按照什么概率选择这个纯策略、按照什么概率选择那种纯策略的策略选择指示。 混合策略表明：参与人可以按照一定的概率，随机地从纯策略集合中选择一种纯策略的实际行动。 期望值：假定存在 个可能的取值 ， 并且这些取值发生的概率分别为： ，则期望值为：,小孩玩的游戏“石头，剪子，布”，也是一种博弈。但是，这个博弈有一种有趣的特征，即给定一方的任何选择，另一方都有制胜对方的战略，所以，给定一方任何一个战略，对方都有制胜这个战略的战略，因而这个战略不是最优的。任何“纯战略”都不是最优的，纯战略是“石头，剪子，布”中的任何一个。,混合策略博弈,石头、剪刀、布,0， 0,1， -1,-1， 1,-1， 1,1， -1,0， 0,1， -1,-1， 1,0， 0,石 头,剪 子,布,博弈方2,石 头,剪 子,布,博 弈 方 1,但是，我们知道，玩这个游戏是总是以对方不易猜出的随机方式出招。事实上，可以通过数学证明，当双方都以每个战略按1/3的概率出招时，达成一种双方都不愿改变这种概率分布的局面。这被称为“混合战略纳什均衡”，而这种以随机方式选择纯战略的博弈被称为“混合战略博弈”。 以混合战略博弈我们来看下面几个例子。,例子1 为什么一般人总是小错不断，大错不犯；偷税漏税的一般是中小企业，大企业会老老实实地交税？ 税务部门不会对所有企业的交税情况每一次都去检查，因为这样做的成本太高，得不偿失。所以，税务部门总是随机地对企业的交税情况进行检查。,企业也是随机地在交税与偷漏税之间进行选择。税收部门与企业间进行的是混合战略博弈。因为如果企业总是交税，税务部门就最好不检查；但给定不检查，企业就会偷漏税。所以，两者只有在随机地检查与不检查，企业随机地在偷漏税与交税之间选择，才会达成均衡。,对于大企业，因一旦偷税就数目巨大，所以，税务部门在随机检查时放在大企业上的可能性就大一些；而给定税务部门检查大企业的可能性较大，大企业偷漏税的行为就较少，否则就容易被逮个正着。所以，偷漏税较多的就是一些中小企业，大企业纳税的积极性较高。同样的道理，在犯罪或对错误的监督惩罚博弈中，也是混合博弈，人们可能总是大错不犯小错不断。,例子2 田忌赛马新编 春秋战国时期，齐威王常与旗下大将田忌赛马。规则是：每次赛三局，每一局齐威王与田忌各出一匹马比赛奔跑速度。每一局中的胜者赢败方一千斤铜。田忌有上、中、下三匹马，而齐威王也有上、中、下三匹马。每次比赛，第一局田忌出上马，齐威王也出上马；第二局田忌出中马，齐威王也出中马；第三局，田忌出下马，齐威王也出下马。齐威王的上马比田忌的上马好，齐威王的中马也比田忌的中马好，齐威王的下马还是比田忌的下马好。于是，每次比赛的结果都是田忌连输三局。,田忌的谋士孙膑了解了田忌的困境后，就打听到这样一个消息：尽管齐威王的上、中、下三匹马都要比田忌的对应上、中、下三匹马好，但碰巧的是田忌的上马可胜齐威王的中马，田忌的中马可胜齐威王的下马。于是，孙膑为田忌献计：下一次比赛中第一局时田忌出下马对齐威王的上马输一局，第二局田忌出上马对齐威王的中马，第三局田忌出中马对齐威王的下马，这样可连赢两局，最后净胜一千斤铜。田忌依计而行，果真赢回一千斤铜。,这个故事曾经被很多人当作博弈论的例子来演绎，但实际上这个故事与博弈论无关。博弈论会假定所有局中人都是理性的，不能假定一些局中人聪明而另一些局中人却是傻子。当田忌出下马时，齐威王最好的选择是出下马而不是上马。孙膑的计谋中假定齐威王是傻子，当田忌出下、上、中马时，他仍然按上、中、下马出，当然要输了。事实上，当田忌出下马时，齐威王应出下马，但齐威王出下马时，田忌不应出下马而是出中马，但此时齐威王又应出中马而不是下马了，。这样，博弈不会有纯战略的均衡。,两人只能玩混合战略博弈，齐威王分别以1/6随机的概率选择出上、中、下马的任一排列，田忌也如此。由于齐威王存在绝对优势，他平均看来仍然会赢田忌一千斤铜。,混合策略均衡,纯策略与纯策略纳什均衡 纯策略：肯定会被选择以100%的概率被选择的策略。 纯策略纳什均衡：各个参与人都选择纯策略的纳什均衡。 混合策略与混合策略纳什均衡 混合策略：以一定的概率分布选择某几个行动的策略。 混合策略纳什均衡：由参与人的混合策略构成的纳什均衡。,混合策略定义：在n人博弈的策略式表述 中，假定参与人 有K个纯策略： ，那么，概率分布 称为参与人 的一个混合策略，这里 是参与人 选择 的概率，对于所有的 。, 显然，纯策略可以理解为混合策略的特例，比如说，纯策略 等价于混合策略 ，即选择纯策略 的概率为1，选择任何其他纯策略的概率为0。,混合策略纳什均衡：包含混合策略的策略组合，构成纳什均衡。,混合策略均衡,期望支付函数,例：,参与人1的混合策略：（p,1-p) 参与人2的混合策略：(q,1-q) 参与人1的期望支付： 如果参与人1选择S11： 如果参与人1选择S12： EV1（p,q)= 参与人2的期望支付： EV2（p,q)=,参与人2,S11 p,S12 1-p,S21,S22,参与人2,q,1-q,混合策略均衡,例：监督博弈,给定工人偷懒，老板的最优 选择是监督；给定老板监督， 工人的最优选择是不偷懒； 给定工人不偷懒，老板的最 优选择是不监督；给定老板 不监督，工人的最优选择是 偷懒；如此循环。,老板,监督,不监督,偷懒,不偷懒,工人,混合策略均衡,监督,不监督,偷懒,不偷懒,工人,老板,假定老板选择混合战略（0.5，0.5) 工人选择“偷懒”期望支付为 (-1)0.5+30.5=1 工人选择“不偷懒”期望支付为20.5+20.5=2 工人应选择“不偷懒” 老板选择“不监督” 工人选择“偷懒,0.5,0.5,假定老板选择混合战略（0.2，0.8) 工人选择“偷懒”期望支付为(-1)0.2+30.8=2.2 工人选择“不偷懒”（期望）支付为20.2+20.8=2 工人应选择“偷懒” 老板选择“监督” 工人选择“不偷懒,混合策略均衡,什么情况下达到纳什均衡状态？ 假定存在一个概率q，老板选择混合策略（q，1-q） 工人选择“偷懒”期望收益为(-1)q+3(1-q)=3-4q 工人选择“不偷懒”收益为2 如果老板真的以概率q选择监督，1-q选择不监督，那么意 味着他不会始终重复地选择某个纯策略，而他不重复选择的 条件必须是工人也不会重复地选择策略。 因此，老板 以概率q选择监督必然意味着在这种情况下工人没有合适的纯 策略选择。=老板的选择必须使工人在两个纯策略之间随机选择。 工人什么情况下随机选择？,混合策略均衡,当工人选择任何一个策略的期望支付相等时，即3-4q=2 ，q*=1/4,1- q*=3/4。这样，当老板选择（1/4，3/4）的混合战略时，可以使工人在两个纯战略之间无差异。 同理，假设工人选择(p,1-p)，(p,1-p)成为其最优混合战略 的条件是老板在选择监督与选择不监督之间无差异，即 1p+(-1)(1-p)=(-2)p+2(1-p)，即p*=1/2,1- p*=1/2。 当老板选择（1/4，3/4），工人选择（1/2，1/2）时，刚 好互为彼此的最优反应，达到纳什均衡状态,称为混合战略 纳什均衡。,混合策略均衡,参与人1和参与人2的混合策略组合 构成均衡的必要条件：,混合战略均衡的求解方法,方法1：支付最大化法 给定其他参与人的混合战略，自己选择行动的概率分布要使自己期望支付最大化。,q,1-q,1-p,p,工人的期望支付函数为 (-1)pq+2(1-p)q+3p(1-q)+2(1-p)(1-q)=-4pq+p-2q+2 最优化一阶条件为：-4q+1=0 q*=1/4,给定工人的混合战略为(p,1-p)，老板的混合战略为(q,1-q),支付最大化法求混合战略纳什均衡,老板,监督,不监督,偷懒,不偷懒,工人,混合战略均衡的求解方法,方法2：支付等值法 自己选择策略概率分布使对方不会偏好于任何行动，即选择每一个策略都会得到相同的收益。,例子,例：博弈方1的混合策略（p,1-p) 博弈方2的混合策略（q,1-q） 博弈方1： 由 可得 ：q=0.8 博弈方2： 由 可得 ：p=0.8,得双方的策略及相应得益： 其中，博弈方1的期望得益为： 博弈方2的期望得益为：,多重均衡博弈和混合策略,一、夫妻之争的混合策略纳什均衡 首先，该博弈有两个纳什均衡，本博弈的两个博弈方不会害怕对方猜到自己的选择，他们主观上并不想隐藏自己的选择。因此，该博弈中两博弈方的决策思路和原则应该与没有纳什均衡的严格竞争博弈有所不同。,但显然，双方的偏好不同，妻子喜欢前一个，丈夫喜欢后一个。故在纯策略的范围内，该博弈也是无法对两博弈方的选择提出确定性建议，因此也需要考虑博弈方采用混合策略的可能性。 设p和1-p分别为妻子选择时装表演和足球的概率； 如果妻子不想让丈夫利用自己的选择倾向占上风，则自己的概率选择应使丈夫选择两种策略的期望得益相同：,得：p=3/4,设q和1-q分别为丈夫选择时装表演和足球的概率。同样，如果丈夫不想让妻子利用自己的选择倾向占上风，则自己的概率选择应使妻子选择两种策略的期望得益相同：,得：q=1/3,夫妻之争博弈的混合策略纳什均衡 策略 得益 妻子 （0.75，0.25） 0.67 丈夫 （1/3，2/3） 0.75,可见，这个结果明显不如夫妻双方能交流协商时，任何一方迁就另一方的得益好。这是因为缺乏沟通时可能出现最差的结果造成的。 也就是说，如果不强行设定双方不能交流串通的博弈规则，双方决策时没有被客观或人为的原因隔离开来，也没有因为赌气而采取不理性的态度，那么这种夫妻之间的决策问题一般不应该用上述博弈方式解决。,二、制式问题,电器和电子设备往往有不同的原理或相关技术标准，称之为不同的制式。 如果生产相关电器或电子设备的厂商采用相同的制式，那么产品之间就能相互匹配，零配件也可能相互通用，这对于推广各自的产品和在生产经营中进行合作很有帮助。 设有两个厂商同时计划引进彩电生产线，而彩电有A、B两种不同的制式，那么这时候两个厂商之间就有一个选择制式的博弈问题。,二、制式问题,制式问题混合策略纳什均衡 A B 得益 厂商1： 0.4 0.6 0.664 厂商2： 0.67 0.33 1.296,假定两厂商采用不同的制式所能获取的各自好处如下图所示：,三、市场机会博弈,进 不进 得益 厂商1： 2/3 1/3 0 厂商2： 2/3 1/3 0,两厂商同时发现一个市场机会，但这个市场的容量并不大，两个厂商该如何选择呢？ 厂商1的混合策略必须使厂商2选择进与不进的期望得益相同，厂商2 的情形类似。,混合策略反应函数,反应函数：一博弈方对另一博弈方每种可能的决策内容的最佳反应决策构成的函数。 在纯策略的范畴内，反应函数是各博弈方选择的纯策略对其他博弈方纯策略的反应； 在混合策略的范畴内，博弈方的决策内容为选择概率分布，反应函数就是一方对另一方的概率分布的反应，也是一定的概率分布。 由于纯策略可理解为混合策略，因此实际上反应函数的概念，可以在混合策略概率分布之间反应的意义上统一起来。,法三：混合策略反应函数,猜硬币博弈,(r,1-r)：盖硬币方选择正反面的混合策略概率分布 (q,1-q)：猜硬币方选择正反面的混合策略概率分布,当q0.5时，取r为0,当r0.5时，取q为1,夫妻之争博弈,(r,1-r)：妻子的混合策略概率分布 (q,1-q)：丈夫的混合策略概率分布,当q1/3时，取r为1,当r3/4时，取q为1,混合战略均衡, 混合战略要求人们以随机的方式选择自己的行动，由于随机性行为无法准确预期，因此很多人认为混合战略并非一个令人满意的均衡概念。现实生活中人们真会这样采取行动吗？ 如何解释混合战略？ 参与人试图通过选择混合战略给对手造成一种不确定性，使对手不能预测自己的行动。如，猜硬币、划拳。,混合战略均衡,对参与人类型的一种推断。如监督博弈，老板不知道工人的类型，只知道“勤奋”、“懒惰”型工人各占50%。老板在选择自己 战略时仿佛面临的是一个选择混合战略的 工人。,纳什定理：在一个由n个博弈方的博弈 中，如果n是有限的，且Si都是有限集(对 i=1,n)，则该博弈至少存在一个纳什均衡，但可能包含混合策略。 奇数定理（Wilson,1971）：几乎所有有限博弈都有有限奇数个纳什均衡。,纳什均衡的存在性,纳什均衡的存在性,占优均衡 重复剔除的占优均衡 纯战略NE 混合战略NE 前一个均衡是后一 个均衡的特例，后一个 均衡是前一个的扩展。 上述四个均衡概念统称 为纳什均衡。,多重均衡与协调, 多重均衡的概念 很多博弈具有多个纳什均衡，比如以上讲到的麦琪的礼物、性别战等，称为多重均衡。 多重均衡降低博弈的解释力一方面无法知道哪个均衡会出现，另一方面会发生真正出现的结果与均衡结果不一致。 在某些具有多重均衡的博弈中，各个博弈方偏好于不同的均衡结果，如麦琪的礼物和性别博弈。 那么，博弈方如何使自己偏好的均衡成为实际的均衡结果呢？这就是多重均衡的协调问题。,多重均衡的筛选,帕累托上策均衡 风险上策均衡 聚点均衡 相关均衡,一、帕累托上策均衡,有些博弈，虽然存在多个纳什均衡，但这些纳什均衡可能有明显的优劣差异，所有博弈方都偏好其中同一个纳什均衡。换句话说，可能有这些纳什均衡中的某一个，给所有博弈方带来的利益，都大于其他所有纳什均衡会带来的利益，此时，博弈方的选择倾向性就会是一致的，各个博弈方不仅自己会选择该纳什均衡的策略，而且可以预料其他博弈方也会选择该纳什均衡的策略，因此不会有选择困难。 用这种方法选择出来的纳什均衡，也称为“帕累托上策均衡”。,一、帕累托上策均衡,这个博弈中有两个纯策略纳什均衡，（战争，战争）和（和平，和平），显然后者帕累托优于前者，所以，（和平，和平）是本博弈的一个帕累托上策均衡。,为什么理性的国家之间不会选择战争，但历史上会有那么多战争呢？ 决策者考虑短期利益、个人或小集团利益； 决策者确实缺乏理性和理智； 局部地区或特定时期的利益比上述博弈中所假设的要大等；,二、风险上策均衡