《《博弈论：原理、模型与教程》第02章 Nash 均衡 第03节 Nash均衡》由会员分享，可在线阅读，更多相关《《博弈论：原理、模型与教程》第02章 Nash 均衡 第03节 Nash均衡（11页珍藏版）》请在金锄头文库上搜索。
1、博弈论：原理、模型与教程第一部分 完全信息静态博弈第2 章 Nash 均衡:第2.1节占优行为I:第2.2节重复剔除劣战略行为:第2.3节Nash均衡2.3 Nash 均衡（已精细订正！）；1、定义 2-5! 2、一定理，及其证明丨I1I 3、简单博弈问题Nash均衡的求解：划线法；箭头法 II1前面两小节分析了理性参与人在博弈中的战略选择行为 占优行为与剔除劣战略行为。但是，在大多数博弈问题中，参与人的占优战略是不存在的，而 且所有参与人同时存在占优战略的情形更是少见；剔除劣战略虽然可 以在一定程度上简化博弈问题的求解，但在相当多的博弈中是无法使 用重复剔除劣战略的方法求解博弈问题的（如图
2、2-4和图2-6所示的 战略式博弈）。4404*为了完全解决完全信息博弈的求解问题，需要选找新的方法和定 义新的博弈解。探寻博弈问题的解，必须明确：博弈分析是在博弈问题的结构和 参与人完全理性为共同知识的假设下进行的，而在该假设下，人们（或 博弈论专家）对博弈问题的求解就等同于完全理性的参与人对博弈问 题的求解。因此，可以采用内省式思维分析博弈问题的解。考察战略式博弈的解。假设参与人i （i二1,2, ,n）在博弈开始之前对博弈的结果进行预 测，并且预测战略组合（s *, s J将成为博弈的结果。i i现在的问题是：参与人i的这种预测是否一定就是博弈的真正结果？或者说参与人i 的预测在什么情况
3、下才是正确的？参与人i的预测战略组合3,sQ将成为博弈结果，也就意味着参与人ii I预测其他参与人的选择为s*。在预测其他参与人的选择为s*情况下，ii参与人i自己的选择s*怎样才是合理的呢？或者说参与人i选择s*应 ii该满足什么样的条件呢？显然，对于理性的参与人i来讲，其选择s*必须满足这样的条件:i在其他参与人的选择为s*的情况下，选择s*的所得必须不小于选择ii其他任何战略的所得，或者说s*必须是使自己的所得最大化的选择i即，对 Vs G S ， u (s *, s * .) u (s , s * .)，或者iii iii iis*G argMaxu(s，s *.)。反之，如果s*不能
4、使参与人i的所得最大化is G S i i iiii他就会偏离s;而选择其他的战略，除非参与人i不是理性的。4*由以上分析可以推知，一个战略组合s *=(s；叮sn) 要成为博弈的结果，就必须满足： 对于所有的参与人，当其他参与人 选择战略组合s*中给定的战略时，选择s*中相应的战略得到的支付 不小于选择其他战略所得到的。即，Vi er , Vs G S ,iiu (s*,s *i) u (ss *i)，或者 Vi e r, s * g arg Maxu (s , s *)。满i ii iii i is eSii足这样条件的战略组合s*，称之为Nash均衡(Nash equilibrium)定
5、义2-5在一个给定的n人战略式博弈G = T; S，,Su中，1n 1n 战略组合s*=(s：，s*，s*)是一个 Nash均衡，当且仅当1 inVi eT, Vs g S 时，有iiu (s *, s*_.) u (s , s*_.)i ili i l或者 Vi e r, s* e argMaxu (s , s* )i厂ii- is e SiiNash 均衡是 1994年诺贝尔经济学奖获得者 John Nash 在20世 纪50年代作为n人战略式博弈的解而提出来的，也是目前得到比较 致认可的博弈的解。在传统的博弈论中，一般都将Nash均衡作为 博弈的解。事实上，亦可反证地理解：一个战略组合s
6、=(si，s；，sn)如 果不是Nash均衡，则意味着一定存在某个参与人i，当其他参与人选 择战略组合s给定的战略时，参与人i选择s并不能使自己的支付最 大化。这就意味着：在参与人i的战略集中，一定存在战略S ，当其i他参与人选择战略组合s给定的战略时，参与人i选择S“所得到的支i付大于选择s的支付，即u (s：s )u (s ,s)。在这种情况下，理ii i -ii i -i性的参与人i就会偏离s，从而使得战略组合s不能成为博弈的结i果。因此，一个战略组合s如果不是Nash均衡，就不能成为博弈的 解。重点！）4*440显然，前面定义的博弈的解占优战略均衡一定是 Nash 均衡。证明：由定义2
7、-1,即“在n人博弈中，如果对于所有的其他参 与人的选择s , s*都是参与人i的最优选择，则称S*为参与人i的占优i ii战略”，这说明占优战略是参与人在任何情况下的最优选择，无论其 他参与人如何选择，理性的参与人只会选择占优战略，再由定义2-5 ， 知道 Nash 均衡系由参与人的最优战略组合而成，故占优战略均衡满 足Nash均衡的定义，占优战略均衡是Nash均衡。重点！）同样，重复剔除的占优均衡也是 Nash 均衡。事实上，如果战略组合s *=（si，,叮，,sn）是重复剔除的 占优均衡，那么对于任有参与人i,可以证明：s；定是参与人i在 其他参与人选择s*情况下的最优选择。面给出证明(
8、重点！)：假设s*不是参与人i在其他参与人选择s*.情况下的最优选择，则ii一定存在ss e S (sy s*)，使得ii iiu (sf, s* )u (s*, s* )(2-1)i i ii i i由于ss不是重复剔除的占优均衡s*中战略，因此ss 一定在重复剔除ii过程中被剔除掉。考察重复剔除劣战略过程中剔除战略s的情形。由Si于ss在重复剔除过程中被剔除掉，因此，存在se S，使得s相对于iiiii占优(弱占优)。此时，有u (s, s* ) u (s,s* )(2-2)i i ii i i若s = s*,则式(2-1)与式(2-2)矛盾，假设不成立。所以，卩就是参i ii与人i在其他
9、参与人选择s*情况下的最优选择。i若s*，则s定在重复剔除过程中被剔除掉。因此，存在iiis e S，使得s S相对于s占优(弱占优)。此时，有iiiiu (s , s* ) u (s , s* )(2-3)i i ii i i由式(2-2)和(2-3)，可得u (s , s* ) u (s , s* )(2-4)i i ii i i若s sss = s*，则式(2-1)与式(2-4)矛盾，假设不成立。所以，s*就是i ii参与人i在其他参与人选择S*的情况下的最优选择。i若s丰s* e S，则s同样在重复剔除过程中被剔除掉。iiii由于s；是重复剔除过程中保留下来的战略，而且参与人i的战略
10、数有限，因此重复上述证明过程，可得u （s*, s* ） u （sf, s* ）（2-5）ii ii i i由于式（2-1）与式（2-5）矛盾，假设不成立。所以，s*就是参i与人i在其他参与人选择s*的情况下的最优选择。证毕i（重点！）4404*440关于Nash均衡，还可以这样理解：设想n个参与人在博弈之前 就博弈的结果进行协商并达成一个协议，规定每个参与人选择一个特 定战略s*, s*=（s；，s*）代表这个协议。现在的问题是：在没有 in外在强制的情况下，什么样的协议 s* 才能够得到执行。可以设想。如果s*不是Nash均衡，那么至少有一个参与人就会偏离协议s*所 规定的战略，使得协议
11、s* 无法实施。 因此，要使协议能够自动得到 实施，就必须使协议为 Nash 均衡。推而广之，一个制度或者机制， 要在实际中能够自动发生效力，就必须使这种制度或者机制所带来的 结果是一种Nash均衡；否则，这种制度或者机制在实际中就无法自 动实施。对于一个战略式博弈，可以根据定义 2-5来判断一个战略组合是否Nash均衡，从而得到博弈的解。例如，“囚徒困境”中的战略组合（坦白，坦白）就是 Nash 均衡。4*440Nash 均衡的求解1、方法 1：由定义直接判断（注：定义，可导出一切） 显然，根据定义2-5很容易判断一个战略式博弈的战略组合是否 构成 Nash 均衡。2、其它方法 当博弈问题中
12、的参与人人数很多并且参与人的战略空间很大时，根据定义2-5逐一判断每个战略组合是否为Nash均衡，并不是一件 很容易的事。除了根据定义判断Nash均衡以外，目前人们尚未找到一种对所 有博弈问题都适用的方便简捷的求解Nash均衡的方法。但是，对于两人有限博弈，可以采用比较简单的“划线法”和“箭头法”。下面给合具体的例子对这两种方法进行说明。（1）“划线法”“划线法”就是利用Nash均衡这样的性质：在两人博弈中，相 互构成最优战略的战略组合就是 Nash 均衡。其具体步骤如下： 找出参与人 1的最优战略。对于参与人 2的每个战略，找出参与人 1的最优战略，并在其对 应的支付下划一横线。在图2-15
13、中，对于参与人2的三个战略b、b和b，参与人1123相对应的最优战略分别为a，a和a，相对应的支付分别为4、4和3223（图 2-15 中划了横线的为参与人1 的支付）。参与人13, 21, 32, 52, 44, 53, 44, 23, 12, 3b 2b 1a 1a2参与人2b3图2-15“划线法”寻找Nash均衡 用上述方法找出参与人 2的最优战略。在图2-25中，对于参与人1的三个战略a，a和a，参与人2 123相对应的最优战略分别为b、b和b，相对应的支付分别为5、5和3 323图2-15中划了横线的为参与人 2的支付)。 找出最优战略组合。支付表中，如果某个方格中的两个支付值都划了
14、横线，那么这个 方格所对应的战略组合就是最优战略组合，也就是所要找的 Nash 均 衡。在图 2-15 中，战略组合 (a ,b ) 所对应的支付值都划有横线，22(a , b )即为所寻找的Nash均衡。22(2)“箭头法”“箭头法”则是利用了 Nash均衡这样的性质：在两人博弈中， 一个战略组合只有在两个参与人都不愿意偏离的情况下才能构成 Nash 均衡。其具体步骤如下：对于每个战略组合，检查是否有参与人会偏离这个战略组合。如果 有人会偏离，则用一个箭头指向他所要偏离的战略组合。例如，在图2-16中，对于战略组合(a ,b)，在参与人2选择b的1 1 1情况下，参与人1会偏离a而选择a，在参与人1选择a的情况下，1 3 1参与人2会偏离b而选择b ；13又如，对于战略组合(a ,b )，在参与人2选择b的情况下，参与2 3 3人1不会偏离a，但在参与人1选择a的情况下，参与人2会偏离b2 2 3而选择b2以次类推找出没有参与人会偏离的战略组合。支付表中，如果某个方格中没 有箭头指向其他方格，那么这个方格所对应的战略组合即使没有参与 人会偏离的战略组合，也就是要找的 Nash 均衡。在图2-16中，战略组合(a , b )所对应的方格没有
