博弈论-混合策略纳什均衡

1、., 第三章 混合策略纳什均衡,混合策略与期望支付 计算混合策略纳什均衡的三种方法 支付最大值法 支付等值法 反应函数法 多重纳什均衡及其甄别 混合博弈在现实经济中的运用案例,.,剪刀、石头、布的游戏,每个同学跟后面一排对应的同学玩剪刀、石头、布的游戏. 玩二十次,将结果记下来 赢了十次以上同学举起手来 告诉我你有什么秘决 怎么样才能赢得多？,.,剪刀、石头、布的游戏,我们知道 如果博弈只进行一次，我们无法明确预测博弈的结果，不管是哪个博弈方，也不管他们的选择是哪个策略，都不能保证得到较好的结果。根据我们上一章所学的方法，这个博弈没有纳什均衡。 那么是不是意味着这样的博弈中，你可以随意选择，结

2、果都一样呢？,.,剪刀、石头、布的游戏,答案是否定的。 事实上，局中人的选择仍然是很有讲究的，策略选择的好坏对局中人的利益仍然有很大的影响。 在这个零和博弈里，无论双方采用哪种策略组合，结果都是一方输一方赢，而输的一方又总是可以通过单独改变策略而反输为赢。如果哪个局中人能找到对手方的规律或者偏好，他就能猜测到对手的策略而采用针对性策略从而保证赢。,.,剪刀、石头、布的游戏,因此，秘决在于 自己的策略选择不能预先被对手方知道或猜测到，在该博弈的多次重复中，博弈方一定要避免自己的选择具有规律性； 观察对手方策略选择是否具有规律或者偏好，预先猜测对手策略，从而采用针对性策略赢得这个博弈。,., 第三

3、章 混合策略纳什均衡,纯策略(pure strategies)：如果一个策略规定参与人在一个给定的信息情况下只选择一种特定的行动。 混合策略(mixed strategies)：如果一个策略规定参与人在给定的信息情况下，以某种概率分布随机地选择不同的行动。 在静态博弈里，纯策略等价于特定的行动，混合策略是不同行动之间的随机选择。,., 期望支付,与混合策略(mixed strategies)相伴随的一个问题,是局中人支付的不确定性(uncertainty).可用期望支付(expected payoff)来描述有个n可能的取值X1,X2,Xn ，并且这些取值发生的概率分别为p1,p2,pn，那么

4、我们可以将这个数量指标的期望值定义为发生概率作为权重的所有可能取值的加权平均，也就是,.,政府和流浪汉的博弈,政府想帮助流浪汉，但前提是后者必须试图寻找工作，否则，不予帮助；而流浪汉若知道政府采用救济策略的话，他就不会寻找工作。他们只有在得不到政府救济时才会寻找工作。他们获得的支付如图所示：,流浪汉 寻找工作 游闲,政府,救济,不救济,.,思考：政府会采用纯策略吗？流浪汉呢？这个博弈有没有纯策略的纳什均衡？ 跟你玩剪子石头布游戏一样，你会一直采用纯策略吗？ 那么政府和流浪汉最有可能采用什么策略？ 使自己的预期支付最大化。 若能够猜的对方的策略，就可以采用针对性的策略，使自己的支付增加。,政府和

5、流浪汉的博弈,.,求解混合策略纳什均衡,1、假定政府采用混合策略：,2、流浪汉的混合策略为：,.,对上述效用函数求微分，得到政府最优化的一阶条件为：,就是说，从政府的最优化条件找到流浪汉混合策略流浪汉以0.2的概率选择寻找工作，0 .8的概率选择游闲。,解一:支付最大化 那么，政府的期望效用函数为：,.,流浪汉的期望效用函数为：,解一:支付最大化,.,解二:支付等值法,政府选择救济策略,政府选择不救济策略,如果一个混合策略是流浪汉的最优选择，那一定意味着政府在救济与不救济之间是无差异的，即：,.,解二:支付等值法,如果一个混合策略是政府的最优选择，那一定意味着流浪汉在寻找工作与游闲之间是无差异

6、的，即：,.,如果政府救济的概率小于0.5； 则流浪汉的最优选择是寻找工作； 如果政府救济的概率大于0.5； 则流浪汉的最优选择是游闲等待救济。 如果政府救济的概率正好等于0.5； 流浪汉的选择无差异。,政府和流浪汉的博弈,.,讨 论,上面的均衡要求每个参与人以特定的概率选择纯策略。也就是说，一个参与人选择不同策略的概率不是由他自己的支付决定的，而是由他的对手的支付决定的。 正是由于这个原因，许多人认为混合策略纳什均衡是一个难以令人满意的概念。 事实上，正是因为它在几个（或全部）策略之间是无差异的，他的行为才难以预测，混合策略纳什均衡才会存在。,.,讨 论,尽管混合策略不像纯策略那样直观，但它

7、确实是一些博弈中参与人的合理行为方式。扑克比赛、垒球比赛、划拳就是这样的例子，在这一类博弈中，参与比赛的总是随机行动以使自己的行为不被对方所预测。 经济学上的监督博弈也是这样一个例子。如税收检查、质量检查、惩治犯罪、雇主监督雇员等都可以看成猜谜博弈。,.,纳什均衡的存在性,纳什定理：在一个由n个博弈方的博弈 中，如果n是有限的，且 都是有限集(对 )，则该博弈至少存在一个纳什均衡，但可能包含混合策略。 证明过程省略，主要根据是布鲁威尔和角谷的不动点定理。 纳什均衡的普遍存在性正是纳什均衡成为非合作博弈分析核心概念的根本原因之一。,.,扑克牌对色游戏,甲乙玩扑克牌对色游戏，每人都有红黑两张扑克牌

8、，约定如果出牌颜色一样，甲输乙赢，如果出牌颜色不一样，则甲赢乙输。 找到这个博弈的纳什均衡。,., 反应函数法,假设甲、乙均采用混和策略,随机地以p的概率出红牌和以(1-p)的概率出黑牌,而乙则随机地以q的概率出红牌和以(1-q)的概率出黑牌。,., 反应函数,A的目标是期望支付越大越好。我们之所以把A的期望支付整理成不含p的一项和含p的一项这个样子，是因为A只能选择p而不能q，因此，A能通过选择p来影响第一项，而不能直接影响第二项。（1-2q）0即q1/2时，A把p选择等于0最好；当（1-2q）=0即q=1/2时，A可以在0，1之间随便选择一个p。这样我们可以得到A的反应函数是，同样道理我们

9、可以得到B的反应函数。 0， 如果q1/2 1， 如果p1/2 p 0,1, 如果q=1/2 q 0,1, 如果p=1/2 1, 如果q1/2 0, 如果p1/2,., 反应函数曲线相应方法,p,q,1/2,1,纳什均衡是A和B都出红牌或者黑牌的概率是 一半对一半,1/2,1,.,练习：税收检查（监督博弈）,设定a是应纳税款；C是检查成本；F是罚款，假定是Ca+F。看看是否存在纯策略纳什均衡？混合策略纳什均衡在哪里？,.,字母说明,此博弈不存在纯策略纳什均衡。 我们用p代表税收机关检查的概率；q代表纳税人逃税的概率。,.,求解：混合战略纳什均衡之一,假定纳税人采用混合策略达到最优选择时，则税收

10、机关在检查和不检查两种策略的期望收益相等： (a-C+F) q+(a-C)(1- q)=a(1- q) q*=C/（a+F）,.,说明,如果纳税人逃税的概率小于q*, 则qC/a+F ，税收机关的最优选择是检查； 如果纳税人逃税的概率等于q*, 则q=C/a+F ，税收机关随机地选择检查或不检查。,.,之二,假设采用混合策略是税务机关的最优选择那么给定p ,纳税人选择逃税和不逃税的期望收益相等： -(a+F) p +0(1- p)= -a 得p *=a/(a+F),.,说 明,如果税收机关检查概率小于p*, 即p1时，A将增加r,如果3c2/3时，B增加c将增加收益；当r1/3，行参与人的最优

11、反应是r=1。,0,c,1/3,r,1,1,A的反应曲线,2/3,B的反应曲线,三个红色的点 为纳什均衡， 两个为纯策略 均衡。,., 多重纳什均衡及其甄别,帕累托优势标准 风险优势标准 帕累托优势标准和风险优势标准 聚点均衡 相关均衡 抗共谋均衡,.,看看这个博弈有几个纯策略纳什均衡?,帕累托优势标准,.,帕累托优势标准,这个博弈中有两个纯策略 纳什均衡，（战争，战争） 和（和平，和平），显然 后者帕累托优于前者，所 以，（和平，和平）是本 博弈的一个按帕累托优势 标准筛选出来的纳什均衡。,.,风险优势标准,若考虑到或者说是顾忌到其他博弈方可能发生错误的原因，帕累托上策均衡并不一定是最优选择

12、，还需要比较风险优势。下面就是两个例子。,.,风险优势标准,从风险优势标准衡量，帕累托上策均衡（鹿，鹿）并是最优选择，因为一旦对手方犯了错误，晕了头，选择了鹿的策略时，你的支付就会由5变成0！你会选择这么高风险的策略吗？而（兔，兔）的策略组合，当对手方犯了错误，晕了头，选择了鹿的策略时，你的支付还是3，并没有损失！,.,聚点均衡,聚点均衡是利用博弈设定以外的信息和依据选择的均衡。文化、习惯、心理或者其他各种特征都可能是聚点均衡的依据。 城市博弈（城市分组相同）、时间博弈（报出相同的时间）是聚点均衡的典型例子。,.,城市博弈：聚点均衡的例子,游戏：请两个同学上来将四个城市进行分组，分成两组，每组

13、两个城市。如果分组方法相同，则每人平时分加5分。,.,城市博弈：聚点均衡的例子,这四个城市是： 上海、长春、哈尔滨、南京,.,相 关 均 衡,三个纳什均衡：无论是纯策略的纳什均衡（U，L）、（D，R）；混合策略的纳什均衡（1/2，1/2），结果都不理想，不如（U，L）、（D，R）、（D，L）。,利用聚点均衡（天气，抛硬币），但仍不理想。,.,相 关 均 衡,相关装置： 1、各1/3概率A、B、C 2、博弈方1看到是否A，博弈方2看到是否C 3、博弈方1见A采用U，否则D；博弈方2见C采用R，否则L。,相关均衡要点： 1、构成纳什均衡 2、有人忽略不会造成问题,.,一、多人博弈中的共谋问题 这个

14、博弈纯策略的纳什均衡是什么？,共谋和抗共谋均衡,.,本博弈的纯策略纳什均衡：（U，L，A）、（D，R，B） 前者帕累托优于后者。博弈的结果会是什么呢？ （U，L，A）有共谋 (Coalition)问题：博弈方1和2同时偏离。,共谋和抗共谋均衡,.,博弈的结果会是什么呢？ （U，L，A）有共谋 (Coalition)问题：博弈方1和2同时偏离。 （D，R，B） 是防共谋均衡！,共谋和抗共谋均衡,.,防共谋均衡,如果一个博弈的某个策略组合满足下列要求，称为“防共谋均衡” ： （1）没有任何单个博弈方的“串通”会改变博弈的结果，即单独改变策略无利可图； （2）给定选择偏离的博弈方有再次偏离的自由时，

15、没有任何两个博弈方的串通会改变博弈的结果； （3）依此类推，直到所有博弈方都参加的串通也不会改变博弈的结果。 前面例子中：（D，R，B） 是防共谋均衡 （U，L，A）不是防共谋均衡,.,一点说明,存在博弈的纳什均衡，并意味参与者一定不拒绝这种纳什均衡。,.,练习: 竞争博弈,竞争博弈是一种零和博弈，即博弈一方的收益等于另一方的损失。多数体育竞技项目都是零和博弈：一个组的1分等价于另一个组失去一分。参与人之间的利益是完全相反的。 例如，在一个足球比赛中，前锋主罚点球，守门员防守。如果守门员扑错了方向，前锋得分的可能性大一些。同时，前锋可能善于踢向某一个方向，而守门员可能善于扑向某一个方向。但双方

16、都有朝两个方向的可能。,.,假定如果前锋踢向球门的左方，当守门员扑向右方时，前锋将是得分的把握80% ，当守门员扑向左方时，前锋得分的把握50%。 如果前锋踢向球门的右方，当守门员扑向左方时，前锋得分的把握90%，当守门员扑向右方时，前锋得分的把握是20%。注：前锋的得分,就为守门员的失分。 画出这个竞争博弈的支付矩阵,并求纳什均衡.,.,这个博弈的纳什均衡有两种写法,前锋,守门员,左p,右1-p,左q,右1-q,50，-50,80，-80,90，-90,20，-20,.,这个博弈的支付矩阵有两种写法,前锋,守门员,左p,右1-p,左q,右1-q,50，50,80，20,90，10,20，80

17、,.,纳什均衡,计算得前锋应该按概率0.7踢向左方，而守门员应该按概率0.6扑向左方。 这些概率使得无论对方采取什么策略，双方都得到相等的收益。即当前锋选择p=0.7时，守门员扑向左方和右方无差异，即不会影响前锋的收益，但他会乐意以0.6的概率扑向左方。同样，当守门员选择q=0.6时，前锋踢向左方和右方无差异，但他会乐意以0.7的概率踢向左方。 这就形成了纳什均衡。给定对方的选择，每一个参与人的选择都是最优的。,.,前锋和守门员的最优反应曲线,当p0.7时，守门员将扑向右方。类似的，当q0.6时，前锋将踢向右方。,0,q,0.6,p,1,1,守门员的反映曲线,0.7,前锋的反映曲线,.,激励的悖论,一小偷欲偷有守卫看守的仓库，若小偷去偷时守卫睡觉（不负责），则小偷偷窃成功（令其价值是V），若守卫没有睡觉（尽职尽责），则小偷会被抓住坐牢（设其效用为-A）；再假设守卫睡觉而未被偷的效用为S，守卫睡觉而被偷则被解雇，其效用为-D。写出得益矩阵，并分析如果想减少小偷偷东西的现象发生,如何做效果更好?,.,小偷与守卫博弈,小偷,守卫,偷p,不偷1-p,睡q,小睡1-q,V，-D,-A，0,0，S,0，0