第三讲混合策略纳什均衡

第三讲混合策略纳什均衡主讲人：李美娟引言◆有些博弈不存在纳什均衡，或者纳什均衡不唯一，如猜硬币博弈，前述纳什均衡分析就无法对博弈方的选择和博弈结果作明确的预测。◆这部分对不存在纳什均衡和存在多个纳什均衡的博弈作一些讨论。混合策略的引进一、扑克牌对色游戏-1，11，-11，-1-1，1红黑乙甲红黑不存在前面定义的纳什均衡策略组合。这类博弈很多，引出混合策略纳什均衡概念。混合策略的相关概念◆混合策略是一种按照什么概率选择这个纯策略、按照什么概率选择那种纯策略的策略选择指示。◆混合策略表明：参与人可以按照一定的概率，随机地从纯策略集合中选择一种纯策略的实际行动。◆期望值：假定存在个可能的取值，并且这些取值发生的概率分别为：，则期望值为：n12,,,nXXX12,,,nppp1122nnpXpXpX小孩玩的游戏“石头，剪子，布”，也是一种博弈。但是，这个博弈有一种有趣的特征，即给定一方的任何选择，另一方都有制胜对方的战略，因而这个战略不是最优的。任何“纯战略”都不是最优的，纯战略是“石头，剪子，布”中的任何一个。混合策略博弈石头、剪刀、布0，01，-1-1，1-1，11，-10，01，-1-1，10，0石头剪子布博弈方2石头剪子布博弈方1但是，我们知道，玩这个游戏总是以对方不易猜出的随机方式出招。事实上，可以通过数学证明，当双方都以每个战略按1/3的概率出招时，达成一种双方都不愿改变这种概率分布的局面。这被称为“混合战略纳什均衡”，而这种以随机方式选择纯战略的博弈被称为“混合战略博弈”。以混合战略博弈我们来看下面几个例子。例子1为什么一般人总是小错不断，大错不犯；偷税漏税的一般是中小企业，大企业会老老实实地交税？税务部门不会对所有企业的交税情况每一次都去检查，因为这样做的成本太高，得不偿失。所以，税务部门总是随机地对企业的交税情况进行检查。企业也是随机地在交税与偷漏税之间进行选择。税收部门与企业间进行的是混合战略博弈。因为如果企业总是交税，税务部门就最好不检查；但给定不检查，企业就会偷漏税。所以，两者只有在随机地检查与不检查，企业随机地在偷漏税与交税之间选择，才会达成均衡。对于大企业，因一旦偷税数额就巨大，所以，税务部门在随机检查时放在大企业上的可能性就大一些；而给定税务部门检查大企业的可能性较大，大企业偷漏税的行为就较少，否则就容易被逮个正着。所以，偷漏税较多的就是一些中小企业，大企业纳税的积极性较高。同样的道理，在犯罪或对错误的监督惩罚博弈中，也是混合博弈，人们可能总是大错不犯小错不断。例子2田忌赛马新编春秋战国时期，齐威王常与旗下大将田忌赛马。规则是：每次赛三局，每一局齐威王与田忌各出一匹马比赛奔跑速度。每一局中的胜者赢败方一千斤铜。田忌有上、中、下三匹马，而齐威王也有上、中、下三匹马。每次比赛，第一局田忌出上马，齐威王也出上马；第二局田忌出中马，齐威王也出中马；第三局，田忌出下马，齐威王也出下马。齐威王的上马比田忌的上马好，齐威王的中马也比田忌的中马好，齐威王的下马还是比田忌的下马好。于是，每次比赛的结果都是田忌连输三局。田忌的谋士孙膑了解了田忌的困境后，就打听到这样一个消息：尽管齐威王的上、中、下三匹马都要比田忌的对应上、中、下三匹马好，但碰巧的是田忌的上马可胜齐威王的中马，田忌的中马可胜齐威王的下马。于是，孙膑为田忌献计：下一次比赛中第一局时田忌出下马对齐威王的上马输一局，第二局田忌出上马对齐威王的中马，第三局田忌出中马对齐威王的下马，这样可连赢两局，最后净胜一千斤铜。田忌依计而行，果真赢回一千斤铜。这个故事曾经被很多人当作博弈论的例子来演绎，但实际上这个故事与博弈论无关。博弈论会假定所有局中人都是理性的，不能假定一些局中人聪明而另一些局中人却是傻子。当田忌出下马时，齐威王最好的选择是出下马而不是上马。孙膑的计谋中假定齐威王是傻子，当田忌出下、上、中马时，他仍然按上、中、下马出，当然要输了。事实上，当田忌出下马时，齐威王应出下马，但齐威王出下马时，田忌不应出下马而是出中马，但此时齐威王又应出中马而不是下马了，……。这样，博弈不会有纯战略的均衡。两人只能玩混合战略博弈，齐威王分别以1/6随机的概率选择出上、中、下马的任一排列，田忌也如此。由于齐威王存在绝对优势，他平均看来仍然会赢田忌一千斤铜。混合策略均衡◆纯策略与纯策略纳什均衡纯策略：肯定会被选择——以100%的概率——被选择的策略。◆混合策略混合策略：以一定的概率分布选择某几个行动的策略。◆混合策略定义：在n人博弈的策略式表述中，假定参与人有K个纯策略：，那么，概率分布称为的一个混合策略，这里是选择的概率，对于所有的。nnuuSSG,,;,,11i1,,iiiKSSS1,,iiiKpppi)(ikiksppiiks1,10,,,11KikikppKk◆显然，纯策略可以理解为混合策略的特例，比如说，纯策略等价于混合策略，即选择纯策略的概率为1，选择任何其他纯策略的概率为0。'is0,,0,1ip'is◆混合策略纳什均衡：包含混合策略的策略组合，构成纳什均衡。混合策略混合策略均衡设是n人策略式博弈的一个混合策略组合。如果对于所有的，对于每一个都成立，则称混合策略组合是这个博弈的一个纳什均衡。1(,,,,)inppppnnuuSSG,,;,,111,,in(,)(,)iiiiiiVppVppip1(,,,,)inpppp期望支付例：◆参与人1的混合策略：（p,1-p)参与人2的混合策略：(q,1-q)◆参与人1的期望支付：如果参与人1选择S11：如果参与人1选择S12：EV1（p,q)=◆参与人2的期望支付：EV2（p,q)=u1，u2u3，u4u5，u6u7，u8参与人2S11pS121-pS21S22参与人2q1-q13(1)ququ57(1)ququ1357[(1)](1)[(1)]pququpququ2468[(1)](1)[(1)]qpupuqpupu混合策略均衡例：监督博弈给定工人偷懒，老板的最优选择是监督；给定老板监督，工人的最优选择是不偷懒；给定工人不偷懒，老板的最优选择是不监督；给定老板不监督，工人的最优选择是偷懒；如此循环。1，-1-1，2-2，32，2老板监督不监督偷懒不偷懒工人混合策略均衡监督不监督偷懒不偷懒工人老板假定老板选择混合战略（0.5，0.5)工人选择“偷懒”期望支付为(-1)×0.5+3×0.5=1工人选择“不偷懒”期望支付为2×0.5+2×0.5=2工人应选择“不偷懒”老板选择“不监督”工人选择“偷懒’……0.50.5假定老板选择混合战略（0.2，0.8)工人选择“偷懒”期望支付为(-1)×0.2+3×0.8=2.2工人选择“不偷懒”（期望）支付为2×0.2+2×0.8=2工人应选择“偷懒”老板选择“监督”工人选择“不偷懒’……1，-1-1，2-2，32，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)成为其最优混合战略的条件是老板在选择监督与选择不监督之间无差异，即1×p+(-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的混合策略组合构成均衡的必要条件：11(,)(,)VpqVpq22(,)(,)VpqVpq(,)pq混合战略均衡的求解方法◆方法1：支付最大化法给定其他参与人的混合战略，自己选择行动的概率分布要使自己期望支付最大化。q1-q1-pp工人的期望支付函数为(-1)pq+2(1-p)q+3p(1-q)+2(1-p)(1-q)=-4pq+p-2q+2最优化一阶条件为：-4q+1=0q*=1/4给定工人的混合战略为(p,1-p)，老板的混合战略为(q,1-q)支付最大化法求混合战略纳什均衡1，-1-1，2-2，32，2老板监督不监督偷懒不偷懒工人混合战略均衡的求解方法◆方法2：支付等值法自己选择策略概率分布使对方不会偏好于任何行动，即选择每一个策略都会得到相同的收益。例子例：博弈方1的混合策略（p,1-p)博弈方2的混合策略（q,1-q）博弈方1：由可得：q=0.8博弈方2：由可得：p=0.82，35，23，11，5CDAB博弈方2博弈方1=25(1)AVqq=3(1)BVqq=ABVV=3(1)CVpp=25(1)DVpp=CDVV得双方的策略及相应得益：其中，博弈方1的期望得益为：博弈方2的期望得益为：策略期望得益博弈方1（0.8，0.2）2.6博弈方2（0.8，0.2）2.611111,(1),(1),(1)(1),0.80.820.80.250.20.830.20.212.6eupquACpquADpquBCpquBD12222,(1),(1),(1)(1),0.80.830.80.210.20.820.20.252.6eupquACpquADpquBCpquBD多重均衡博弈和混合策略一、夫妻之争的混合策略纳什均衡◆首先，该博弈有两个纳什均衡，本博弈的两个博弈方不会害怕对方猜到自己的选择，他们主观上并不想隐藏自己的选择。因此，该博弈中两博弈方的决策思路和原则应该与没有纳什均衡的严格竞争博弈有所不同。2，10，00，01，3时装足球时装足球丈夫妻子夫妻之争◆但显然，双方的偏好不同，妻子喜欢前一个，丈夫喜欢后一个。故在纯策略的范围内，该博弈也是无法对两博弈方的选择提出确定性建议，因此也需要考虑博弈方采用混合策略的可能性。◆设p和1-p分别为妻子选择时装表演和足球的概率；◆如果妻子不想让丈夫利用自己的选择倾向占上风，则自己的概率选择应使丈夫选择两种策略的期望得益相同：3-100-11）（）（pppp得：p=3/4◆设q和1-q分别为丈夫选择时装表演和足球的概率。同样，如果丈夫不想让妻子利用自己的选择倾向占上风，则自己的概率选择应使妻子选择两种策略的期望得益相同：1)1(00)1(2qqqq得：q=1/3夫妻之争博弈的混合策略纳什均衡策略得益妻子（0.75，0.25）0.67丈夫（1/3，2/3）0.75◆可见，这个结果明显不如夫妻双方能交流协商时，任何一方迁就另一方的得益好。这是因为缺乏沟通时可能出现最差的结果造成的。◆也就是说，如果不强行设定双方不能交流串通的博弈规则，双方决策时没有被客观或人为的原因隔离开来，也没有因为赌气而采取不理性的态度，那么这种夫妻之间的决策问题一般不应该用上述博弈方式解决。二、制式问题◆电器和电子设备往往有不同的原理或相关技术标准，称之为不同的制式。◆如果生产相关电器或电子设备的厂商采用相同的制式，那么产品之间就能相互匹配，零配件也可能相互通用，这对于推广各自的产品和在生产经营中进行合作很有帮助。◆设有两个厂商同时计划引进彩电生产线，而彩电有A、B两