纯策略纳什均衡 优势策略均衡（强优势、弱优势、极弱优势策略均衡），若存在，当然好，然而， 它们很难存在，原因在于它们要求的条件比较严格。优势策略均衡要求每个参与人的策 略对于其他参与人的所有可能策略都是一个最优反应。如果我们仅要求每个参与人的策 略对其他参与人的纳什均衡策略构成最优反应，我们就能得到博弈论中的一个核心概 念，即纳什均衡（Nashequilibrium）。这个解概念是以约翰·纳什的名字命名的，他是 当代最著名的博弈论学家之一。我们用几个例子来说明这个概念。我们将证明纯策略纳 纯策略纳什均衡 什均衡（pure strategyNashequilibrium）未必总存在。如果存在，也通常存在多个纳 什均衡。我们还将证明，在纳什均衡中，参与人的效用之和可能不是最大的。我们对纳 什均衡提供了几种可能的解释。我们还介绍了策略型博弈中的最大最小值（maxmin value）、最小最大值（minmaxvalue）、最大最小策略（maxmin strategy）、最小最大策 略（minmaxstrategy），以及它们与纯策略纳什均衡的关系。另外，我们还介绍了展开 型博弈的子博弈完美均衡（subgameperfectequilibrium）概念。 6.1纳什均衡概念 定义6.1（纯策略纳什均衡）给定策略型博弈T=（N，（S），（u））及其策略组 s=（s，S2，，S），若 u;（s²s=）≥u（sis=;）对于所有s∈S，i=1,2，…，n 那么我们说s*是T的一个纯策略纳什均衡（简记为PSNE)。 上述条件的另外一种表达方式为 u;（s²，s=）=maxu；（s，s=：）对于i=1,2,,n

也就是说，每个参与人的纳什均衡策略是其他参与人纳什均衡策略的最优反应。 注释在上面的定义中，我们隐含地假设参与人的效用代表利益或利润，因此，参 与人总是追求效用最大化。然而，在个别情形下，使用成本或惩罚来表达效用更为自 然。在这种情形下，参与人追求效用最小化。对此，上述定义中的不等式符号将变为 ≤，而不再是≥。在本书中，除非特别指明，效用总代表着利润或利益。当使用成本表 示效用更为自然时，我们总是在成本前面加个负号来定义效用。 我们现在提供纯策略纳什均衡（PSNE）的另外一种描述方法。 定义6.2（最优反应对应）给定策略型博弈T=（N，（S），（u;）），参与人i的最 优反应对应（bestresponsecorrespondence）是映射b:：S-；→2S:，它的定义为 b;（s-）={s;∈S：u;（siS-i）≥u;（ss-i）对于所有s∈S} 也就是说，给定所有其他参与人的策略组s-i，b（s-：）给出了由参与人i的所有最 优反应策略组成的集合。 可以看出，策略组（s，S，，s）是一个纯策略纳什均衡当且仅当 s∈b；（s=;）对于所有i=1，……，n 例6.1（BOS博弈）回忆一下两个参与人的BOS博弈，它的收益矩阵如下： A B A 2，1 0，0 B 0，0 1，2 这里有两个纳什均衡，即（A，A）和（B，B)。策略组（A，A）是一个纳什均衡，因为 u(A,A)>u(B,A) u2(A,A)>u(A,B) 策略组（B，B）也是一个纳什均衡，因为 u(B,B)>u(A，B) u2(B，B)>u2(B,A) 最优反应集为 b(A)={A};b（B)={B}；b(A)={A};b2(B)={B} 由于AEb（A）而且AEb2（A)，因此（A，A）是一个纳什均衡。类似地，由于 BEb（B）而且BEb2（B)，因此（B，B）也是一个纳什均衡。策略组（A，B）不是一 个纳什均衡，这是因为Ab（B)；BEb2（A)。口 例6.2（囚徒困境）我们考虑囚徒困境问题，它的收益矩阵如下 NC C NC -2，-2 -10,-1 C -1，-10 -5，-5

注意到（C，C）是这个博弈唯一的纳什均衡。为了看清这一点，我们只需要看看最优 反应集即可： b（C)={C};b(NC)={C};b（C)={C}；b2（NC)={C} 由于（s，s）是一个纯策略纳什均衡当且仅当sE6（s2）而且s∈b2（s*），因此， 这个博弈的唯一可能纯策略纳什均衡就是（C，C）。事实上，正如我们看到的，这是一 个强优势策略均衡。 对于有着下列收益矩阵的公司两难问题，类似的分析也成立。 A B A 6，6 0，8 B 8，0 3，3 在下面的注释中，我们把结论推广。口 注释给定策略型博弈T=（N，（S），（u;）），强（弱、极弱）优势策略均衡 （s，s，"，s）也是一个纳什均衡。这个证明比较直观（参见习题中的问题1）。它 的直觉解释如下。在优势策略均衡中，每个参与人的均衡策略都是最优反应，不管其他 参与人选择什么策略。在纯策略纳什均衡中，每个参与人的均衡策略都是针对所有其他 参与人的纳什均衡策略的最优反应。因此，纳什均衡是一个比优势策略均衡弱得多的均 衡概念。 第6 注释纳什均衡未必是优势策略均衡。例如例6.1。策略组（A，A）和（B，B） 章 都是纯策略纳什均衡，然而，它们都不是优势策略均衡。读者可以轻松验证此事。 纯 策略 约翰·纳什（JohnF.Nash，Jr.）是20世纪最有原创 纳什均 力的数学家之一。他于1928年出生于美国西弗吉尼亚州布 鲁菲尔德。他于1948年获得卡内基梅隆大学理学本科学位， 衡 同年获得该校理学硕士学位，专业都为数学。随后，纳什到 普林斯顿大学跟随阿尔伯特·塔克（AlbertTucker）教授学 习，并于1950年获得数学博士学位。他的博士论文（全文 仅28页）提出了纳什均衡这个著名概念，从而使得博弈论 范围不再局限于两人零和博弈。 纳什的博士论文的核心在于它解决了有限策略型博弈的 混合策略均衡解的存在性问题。在他攻读博士学位期间，纳 什也写过一篇关于两人议价问题的杰出论文。他使用虚拟原子方法证明了两人议价问题 存在着唯一解。 纳什在麻省理工学院担任数学系教授期间，在代数几何领域取得了突破性的进展。 他还以纳什嵌入定理而闻名，该定理证明了任何抽象黎曼流形都可等距嵌入欧几里得空 间。另外，他对非线性抛物线偏微分方程也有重大贡献。 纳什的生活和成就生动地体现在他的传记《美丽心灵》（ABeautifulMind）之中，

作者为纳萨（SylviaNasar）。这后来被拍摄成为同名电影。纳什教授现在任职于普林斯 顿大学。* 1994年，约翰·纳什（JohnNash）与约翰·海萨尼（JohnHarsanyi）以及莱茵哈 德·泽尔腾（ReinhardSelten）因在非合作博弈的均衡分析上做出的突破性工作共同获 得了诺贝尔经济学奖。 6.2纯策略纳什均衡的例子 有些博弈存在纯策略纳什均衡，有些博弈不存在。在本节，我们各举一些例子来说明。 例6.3（双寡头定价博弈）回忆一下第4章的双寡头定价博弈。两个公司1和2希 望通过分别选择价格p和p2使得各自利润最大。这两个公司的效用分别为： u1(p1，p2)=（p1-c)x1(p1，p2) u2（p1，p2)=（p2-c）x2(p1，p2) 其中x（p1，P2）和c2（P1，p2）分别代表公司1和2选择价格p和p2时的销量（参 见4.9节）。注意，u（c，c)=0，u2（c，c)=0。另外，容易看出 u（c,c）≥u（p，c）对于所有p∈S 博奔论与机制设计 u2（c，c)≥u2（c，p2）对于所有p2ES2 因此，策略组（c，c）是纯策略纳什均衡。这意味着均衡时，每个公司的定价都等于边 际成本。这个结论的背后直觉比较简单，设想一下，如果两个公司的定价都高于边际成 本将会出现什么结果。在这种情形下，每个公司都以高于边际成本的价格得到一半市场 份额。然而，只要其中一个公司稍微把价格降低一点，它就将占领整个市场，因此，两 个公司都尽可能降价。当然，价格不能降低到小于边际成本，因为这样公司会亏损。因 此，两个公司会不停降价直到达到边际成本水平为止。口 例6.4（公地悲剧）我们已经知道，在公地悲剧问题中，N={1，2，，n）是一 组农民，策略集为S=S2==S={0，1)，其中1代表养一只羊，0代表不养羊。养 一只羊的收益为1。然而，一只羊对环境的破坏为5。这个代价由所有农民平摊。注意 （i=1，2，…,n） 在上一章我们已证明，当n<5时，（0，0，“，0）是一个强优势策略均衡。也就 是说，每个农民都没有激励去养羊；当n>5时，（1，1，“，1）是一个强优势策略均 衡。也就是说，养一只羊是每个农民的强优势策略。下面我们考察n=5的情形。这里， u;（0,s-i）=- nj≠i *2015年5月23日，约翰·纳什夫妇遭遇车祸，一同逝世。—译者注

u;(1,s-;）=- 因此， u;（O，s-;）=u;（1,s-:）对于所有s-∈S-i，i∈N 这意味着 b;（s-:)={0,1}对于所有s-ES-i，i∈N 可以看到，在这里，所有策略组都是纳什均衡。另外，注意，它们不是弱优势策略均 衡，也不是强优势策略均衡。 如果政府决定对每只羊征收5单位污染税，我们有 u;（s1，·.，sn）=s-5si n 在这里，注意 u;（0,s-;）= n u;(1,s-;)=-4-5 n n 这意味着 b;（s-i）={0}对于所有i∈N 这表示不管n的值为多大，策略组（0，0，…，0）都是一个强优势策略均衡。口 例6.5（带宽共享博弈）考虑文献[1]讨论的带宽共享博弈（也可参见第4章）。我 纯策略纳什均衡 们按照下列方法计算纳什均衡。令x：为参与人i想传递的流量，这里i=1，，n； 假设 Mxi<1 iEN 回忆一下， u;(x1,xn)=x;(1-∑x;) 对于所有iEN jEN 考虑参与人i并且定义 x= j#i 参与人i的收益为 c;（1-ti-xi) 为了使上述收益最大化，我们必须选择 1-t Ci argmaxx;（1—t;-x;）=

如果这必须对所有i证N成立，那么我们得到一个方程组，它由下列n个方程组成 1-∑x x= 法 i=1，..，n 我们知道策略组（x，，x）是一个纳什均衡当且仅当 u;（x，x;）=maxu；（x，x=;）对于所有i=1，……,n 可以证明上面的方程组有唯一解： ，i=1,.…,n 收益等于 因此，所有参与人的总收益为 n (n+1)2 下面我们将说明，这不是一个让人高兴的情形。考虑下列策略组 1.1 (2n2n2n 容易证明，上面的策略组不是均衡组合，该策略组带给每个参与人的收益为 (1一） 因此，所有参与人的总收益 n 4(n+1)2 )提供的收益大于纳什均衡收益。一般来说，正 如囚徒困境问题的情形一样，对于个人或整体来说，均衡收益未必是最好的可能结果。 这是纳什均衡收益通常伴随的局限。口 例6.6（庇古交通网络博弈）回顾第4章的庇古交通网络博弈。首先考察两个参 与人的情形，他们的收益矩阵为 A B ，-1 A -1,-1 1,-2 B -1,-1

容易看到，策略组（A，A）、（A，B）和（B，A）都是纯策略纳什均衡。剩下的那个 策略组即（B，B），不是纯策略纳什均衡，因为每个参与人只要单方面偏离该策略组， 即用策略A替换策略B，那么他将获益。纳什均衡（A，A）带给两个参与人的收益之 和（总效用）为一2，而另外两个均衡带给两个参与人的总效用为一3/2。 现在考察n>2的情形。在这种情形下，策略组（A，A，""，A）是一个纯策略纳 什均衡，它带来的总效用为一n。如果n是偶数，那么带来最高总效用的策略组是任何 下面这样的策略组一一一半参与人选择策略A，另一半参与人选择策略B。这个总效用 略B这样的策略组，不是均衡组合。然而，它带来的总效用大于纳什均衡组合带来的 总效用。这种糟糕表现的原因在于参与人的理性，算法博弈论用无政府主义的代价 （priceofanarchy）这个术语讨论了该问题。这个主题方面的进一步讨论可参见Nisan， Roughgarden,Tardos, and Vazirani[2]。 例6.7（布雷斯悖论博弈）现在我们讨论第4章和第5章介绍过的布雷斯论。首 先考虑不打通AB路（见图4一2）的情形。假设（si，"，Sn）是任何一个使得 nA（S1,."，Sn）=nB（S1，.，Sn)=500 的策略组。 也就是说，给定1000辆车，恰有500辆选择经过A点的路线，另外500辆选择经 过B点的路线。显然，对于这样的策略组，对于每辆车iEN，u;（s1，"，Sn）都等于 第 一35。假设车辆i偏离策略s：但所有其他车辆都仍选择原来的策略。现在车辆i的效用 章 纯 间增加了。）事实上，由于车辆i单方面偏离原来的策略，比如它从策略A偏离到B， 策 略 那么选择策略A的那499辆车的状况变好了，而车辆i和选择策略B的另外500辆车的 纳 状况变差了。因此，所有满足上面条件的策略组都是纯策略纳什均衡。 什 均 现在考虑打通AB路后的情形（见图4一3）。我们已在第5章证明策略组（AB， 衡 AB，·，AB）是一个强优势策略均衡。在这里，它也是一个纯策略纳什均衡。注意， 另一方面，考虑500辆车使用策略A而另外500辆车使用策略B的策略组。这样 的策略组不是优势策略均衡，也不是纳什均衡，但每辆车的交通时间只有35分钟。正 如我们在第5章看到的，这里出现论的原因在于，打通AB路的做法使得策略AB强 加在每辆车上（对于每辆车来说，策略AB都是强优势策略），从而导致了均衡策略组 情形的交通时间比非均衡策略组情形的交通时间长。口 6.3不存在纯策略纳什均衡的博弈 给定策略型博弈，我们无法保证它一定存在纯策略纳什均衡。下面提供一些例子。 例6.8（硬币配对博弈）回顾第3章讨论的硬币配对博弈，它的收益矩阵为

A B A 1，-1 -1，1 B -1,1 1，-1 容易看到，这个博弈不存在纯策略纳什均衡。这说明我们无法保证纯策略纳什均衡总是存 在。在第10章，我们将证明策略型博弈存在纯策略纳什均衡解的充分条件。在下一章 （第7章），我们将引人混合策略纳什均衡，并且证明这个博弈有混合策略纳什均衡。口 例6.9考察石头剪刀布博弈，它的收益矩阵如下： 石头 布 剪刀 石头 0，0 -1，1 1,-1 布 1，-1 0，0 -1,1 剪刀 -1，1 1,-1 0，0 显然，这个博弈也不存在纯策略纳什均衡。 接下来，我们考察非对称公司（指两公司地位不对称）的两难问题，它的收益矩阵 如下： 博奔论与机制 A B A 4，1 0，4 B 1,5 1,1 制设计 这个博弈也不存在纯策略纳什均衡。口 下面我们提供一个无限博弈，它也不存在纯策略纳什均衡。 例6.10（采购博弈）这个博弈改编自Tardos andVazirani[1]。给定某种特定商 品，买者向卖者采购，买者和卖者都可为多个，这里卖者为博弈参与人。为具体起见， 假设有两个卖者1和2，三个买者A、B和C。由于存在着诸如物流的约束，再假设 ·A只能向1采购。 ·C只能向2采购。 ·B可向1采购，也可向2采购。 ·每个买者的最大支付意愿为1，而且都只想买1单位。 ·每个卖者的供货都很充足。 ●每个卖者都在区间[0，1]内报价。 令卖者1和2的报价分别为s和s2。容易看出，A以价格s向1采购，C以价格s2 向2采购。如果s1<s2，那么B将向1采购；如果s>s2，那么B将向2采购。假设当 s1=s2时，B将向1采购。现在，我们可将这个博弈定义如下： N={1,2}; S=S2=[0,1];

u（s1，S2）=2s若s＜s2 =S1若s>S2 u2（s1，S2）=2s2若s1>s2 =S2若s1≤s2 容易看出，当0≤s2≤1时，u2（1，s2）的值为2s2。因此，当s2从0开始增加时， u2（1，S2）变大；当s2逐渐增至1时，u2（1，S2）突然降为1。显然，对于任何 s2∈[0，1]，（1，S2）这样的策略组都不可能是一个纳什均衡。类似地，对于si∈[0， 1]，任何（s1，1）这样的策略组也不可能是纳什均衡。 我们现在考察这个博弈是否存在纳什均衡（s，s），其中s，s∈[0，1）（注 意，这是一个左闭右开的区间，它意味着价格1不在报价区间）。这里有两种情形。 情形1：如果s*≤，那么卖者2的最优报价为s=1，因为这能带给它最大收益。 然而，报价s2=1不可行，因为s2的取值区间为[0，1）。 首先，假设s≤s2。于是， u（s，s）=2s u2（ss）=s2 <s2<s。于是， u2（s，S2）=2s2 纯策略纳什均衡

s因为2s2>1且s<1 =u2（s²，s) 因此，参与人可改进（s，s），这意味着（s，s）不是一个纳什均衡。 现在，假设s>s。于是， u（s²，s²）=s² u2（s，s2）=2s 现在假设我们选择s使得1>s>s。于是， u（s1S）=s1>s=u1（s²s²) 因此，参与人总是可以改进（s，s）。这意味着（s，S）不是一个纳什均衡。 综上可知，这个博弈不存在纯策略纳什均衡。口 6.4纳什均衡的解释 在博弈论中，纳什均衡是一个被广泛讨论的主题。对于纳什均衡，博弈论学家已提

供了很多解释。注意，纳什均衡是指n个参与人的一个策略组，使得每个参与人的选择 对所有其他参与人的纳什均衡策略来说都是最优反应。任一参与人单方面偏离纳什均衡 策略，都不能使他自己的状况变好，这里的单方面是指除了他之外其他所有参与人都不 偏离纳什均衡策略。下面是博弈论学家对纳什均衡提供的几种解释。 第一种常见的解释将纳什均衡视为一种处方（prescription）或指示。假设这n个参 与人有一个咨询师。咨询师将纳什均衡策略组作为处方提供给他们。如果这个策略组不 是一个纳什均衡，那么至少有一个参与人将发现不遵守处方能让自己状况变好。如果这 个策略组的确是一个纳什均衡，那么每个参与人都会很高兴，因为给定其他所有参与人 都选择处方提供的策略，那么他选择处方提供的策略的这种做法是最优的。因此，富有 逻辑且理性的咨询师会开出纳什均衡策略组这种处方。然而，需要注意：纳什均衡保证 的是参与人不会单方面偏离纳什均衡（单方面偏离是指在给定的时点上只有一个参与人 偏离）。如果两个或更多参与人偏离纳什均衡，那么他们的状况可能变好。例如，在因 徒困境的问题中，（C，C）是一个纳什均衡。如果两人都决定偏离，策略组将变为 （NC，NC），这使得这两人的状况都变好。注意，（NC，NC）不是一个纳什均衡。 纳什均衡的第二种常见解释是预测（prediction）。如果参与人都是理性且智能的， 那么纳什均衡为博弈提供了一种可能的科学预测。例如，参与人系统地删去强劣势策略 之后，就得到了简化型博弈，它存在纳什均衡（参见第7章）。通常，一次又一次地删 去强劣势策略的做法，能得到唯一预测结果，该结果是一个纳什均衡。 纳什均衡的另外一种合意解释，是将其视为一种自我实施的协议（self-enforcinga- 博 greement)。这种协议可以是参与人之间的一种默契，也可以是明确的合约。在合作博 奔 论 奔中，一旦协议达成，不需要外力保证协议的履行，因为每个参与人遵守协议对自己有 利，当然前提是其他所有参与人也遵守协议。在非合作博弈中，参与人无法实施协议， 机 制 所以在仅允许参与人单方面偏离均衡策略这个假设条件下，这种解释也能讲得通，·因为 设 在这个假设下，纳什均衡是稳健的。 计 纳什均衡的一种自然且易于理解的解释涉及演化（evolution）与稳态（steady state）。纳什均衡是动态调整过程的可能收敛点，这里的动态调整过程是指每个参与人 根据其他参与人的策略选择而调整自己的策略选择的互动过程，这个过程一直持续下去 直至达到稳态。这种说法已被用于解释生物进化。在这个解释下，纳什均衡是重复博弈 在长期得到的结果。这样，纳什均衡类似历史悠久的社会惯例，而且人们愿意维持 下去。 上面的说法对纳什均衡提供了广为人们接受的解释。对于纳什均衡的概念，已有一 些学者提出了更有洞察力的观点，参见HoltandRoth[3]。 注释对于寻找纳什均衡，共同知识（commonknowledge）通常是一个标准假设。 然而，共同知识的要求太强，可以稍微放松。假设每个参与人都是理性的，知道他自己 的收益函数，而且知道其他人的策略选择。这个条件比共同知识弱，它被称为相互知识 （mutualknowledge）。对于寻找纳什均衡，相互知识的假设已足够。这些概念的详细讨 论，可参见Aumann[4]。这个主题方面的更广泛的讨论和例子可参见Maschler，Solan， andZamir[5]。

托马斯·谢林（ThomasSchelling），与罗伯特·奥曼 （RobertAumann）一起，获得了2005年诺贝尔经济学奖， 因为他们通过博弈论分析，对冲突和合作提供了明确解释。 谢林对博弈论的贡献主要体现在他的著作上。他于1960年 写的书《冲突的策略》（TheStrategyofConflict）是一个 经典之作，它引发了人们研究议价和策略行为的浪潮。此书 曾入选1945年以来最有影响的100本书。谢林在这本书中 引入了焦点（focalpoint）概念，用来解释博弈存在多个均 衡时参与人是如何互动的，现在博弈论中的焦点已被称为谢 林点（Schellingpoint）。 谢林的另外一本书《武器与影响》（ArmsandInflu- ence）也被广泛引用。谢林的最大特点是他能用简单博弈模型，以富有想象力的方法， 深入说明一些全球问题，例如冷战、核武器竞赛、战争与和平等。 谢林出生于1921年4月14日。1951年，他获得了哈佛大学经济学博士学位。 1950一1953年间，谢林为美国总统政策顾问团成员。从那时起，他在公共服务领域担 任了很多职位。他在全球变暖辩论中也扮演了重要角色。1958一1990年，他任职于哈 佛大学。自1990年起，他在马里兰大学经济系和公共政策学院担任教授，成绩卓著。 6.5存在多个纳什均衡的情形 纯策略纳什均衡 在前面，我们已经看到，一些博弈存在多个纳什均衡。如果一个博弈有多个纳什均 衡，那么一个基本问题出现了一一哪个均衡将得以实施？这个问题已被很多博弈论学家 尤其是谢林解决。谢林提出了焦点效应（focalpointeffect）。谢林认为，任何能让参与 人聚焦到某个均衡的事情，都能使他们预期这个均衡将发生，从而实施这个均衡，这类 似自我实现的预言。这样的均衡有着区别于其他所有均衡的性质，它有自己的名称，叫 做焦点均衡（focalequilibrium）或谢林点（Schellingpoint）。 例6.11考察BOS博弈，它的收益矩阵如下： A B A 2,1 0，0 B 0，0 1，2 这里，（A，A）和（B，B）都是纳什均衡。如果参与人因为某事对产品A感兴趣，那 么（A，A）可能变为焦点均衡。另一方面，如果参与人对产品B展开营销闪电战，那 么（B，B）可能变为焦点均衡。口

6.6最大最小值和最小最大值 给定一个纳什均衡，我们已看到每个参与人的均衡策略为他提供了最优反应策 略，当然前提是他乐观地假设其他参与人不会偏离他们的均衡策略。如果参与人担心 其他参与人的任何非理性行为，那么他必须做好最坏打算。这样的情形导致了最大最 小策略。 口最大最小值和最大最小策略 参与人的最大最小策略（maxminstrategy）是指当其他参与人自由选择任何策略 这种最坏情形出现时，能使他的收益最大的策略。我们用例子说明这个概念。 例6.12（最大最小值）考虑4.8节的非对称公司的两难问题，该博弈的收益矩阵 如下： A B A 4，1 0，4 B 1，5 1,1 这个博弈没有纯策略纳什均衡。如果参与人1选择策略A，那么他能得到的最小收 益为0（当参与人2选择策略B时）。另一方面，如果参与人1选择B，那么他能得到的 最小收益为1（当参与人2选择A或B时）。因此，参与人1将决定选择策略B，不管 参与人2选择什么策略，因为这样参与人1能保证自己的最小收益为1。这个收益称为 最大最小值（maxminvalue）或安全值（securityvalue），能带给他这个收益的策略B 称为最大最小策略（maxminstrategy）或安全策略（securitystrategy）。 类似地，如果参与人2选择策略A，那么他能得到的最小收益为1（当参与人1选 择策略A时）。另一方面，如果参与人2选择策略B，那么他能得到的最小收益仍为1 （当参与人1选择策略B时）。因此，不管参与人2选择策略A还是B，他总能得到最小 收益1，不管参与人1选择什么策略。在这里，收益1称为参与人2的最大最小值或安 全值，策略A或B称为参与人2的最大最小策略或安全策略。口 假设T=（N，（S：），（u;））是任何策略型博弈。如果参与人i选择策略s:，那么他 的最小收益为 minu;(si,S-i) s-ES-i 参与人i可以在S：中选择策略使得上述最小收益最大化，从而不管其他参与人选择什么 策略，他都能保证自已得到这个可能的最大收益。由此，我们得到了下面的定义。 定义6.3（最大最小值和最大最小策略）给定策略型博弈T=（N，（S：），（u:））， 参与人i（i=1，"，n）的最大最小值或称安全值为

U=maxmin u;（s;S-i) 任何能保证参与人i得到该收益的策略都称为他的最大最小策略或称安全策略。 例6.13对于非对称公司两难博弈，参与人1的最大最小值为1，策略B是参与人 1的最大最小策略，但策略A不是。参与人2的最大最小值也为1，策略A和B都是参 与人2的最大最小策略。这说明参与人可能有多个最大最小策略。口 注释如果参与人i选择最大最小策略，而且其他所有参与人任意选择策略，那么 参与人i得到的收益不会小于ui。因此，最大最小策略也被称为不后悔策略（no-regret strategy）。注意，对于给定的参与人，纳什均衡策略未必是一个不后悔策略；其他参与 人偏离均衡策略的行为能导致参与人i的收益小于他在均衡时的收益。 下面的命题说明参与人i在纳什均衡策略组（若该均衡策略组存在）中的收益至少 为他的最大最小值。 命题6.1假设策略型博弈T=（N，（S），（u））有纯策略纳什均衡（s，"，S）。 那么 ui（s，，S）≥U对于所有i∈N 证明：首先，注意到，对于所有i证N， u;（s，··,s）=maxu（sis) 然后，注意到对于所有证N， 第 u;(sisi）≥min u;(sis-i) 章 sES-i 纯策略纳什均衡 综合上面两个不等式，显然可知，对于所有i∈N，u（s，，s）≥。 注释给定策略型博弈，最大最小策略组可以视为该博弈的另外一个解概念。这样 的策略组可能有多个。显然，这些策略组一般不同于纳什均衡策略组。在第9章，我们 将看到，在两人零和博弈这种特定环境下，每个纯策略纳什均衡策略组（若存在），也 是最大最小策略组。 口最小最大值 大致地说，参与人i的最小最大值（minmaxvalue）是指当其他参与人选择的策略 对参与人i最不利时，参与人i被迫得到的最小收益。它的正式定义如下。 定义6.4（最小最大值和最小最大策略）给定策略型博弈T=（N，（S：），（u）>， 参与人i（i=1，，n）的最小最大值（minmaxvalue）为 =min maxu;(SiS-i) s-ES-isES 能把强加给参与人1的任何策略组s；∈S-都是其他参与人针对参与人i的最小最大 策略组（minmaxstrategyprofile）。 例6.14，在非对称公司两难博弈中，假设我们想计算参与人1的最小最大值。如果 参与人2选择策略A，那么参与人1能得到的最大收益为4（当参与人1选择策略A时）。

如果参与人2选择策略B，那么参与人1能得到的最大收益为1（当参与人1选择策略A 或B时）。因此，如果参与人2选择策略B，那么参与人1被迫得到的最大收益为1，因 此，参与人1的最小最大值为1。参与人2针对参与人1的最小最大策略显然为B。类似 地，参与人2的最小最大值为4，参与人1针对参与人2的最小最大策略为A。口 注意，参与人i的最小最大值：意味着其他参与人迫使参与人i得到的收益不会超 过：。或者说，最小最大值衡量当其他参与人选择对参与人i最不利的策略时，参与人 i的最大反抗程度。注意，最小最大值：与最大最小值：的区别。参与人i的最大最小 值是他能保证自已得到的最小收益。在直觉上，参与人的最小最大值必定大于或等 于他的最大最小值。下列命题正式说明了这个事实。 命题6.2给定策略型博弈T=（N，（S：），（u）>，总有 ≥u对于所有iN 证明：假设s；是其他参与人针对参与人i的一个最小最大策略组。这意味着 =maxu;（si，s;）对于所有i∈N 注意，对于所有证N， u;(si，s=;）≥ minu;（s;S-i）对于所有si∈S s-,ES-i 使用上面的两个不等式，可得 ;=maxu;（si，s;）≥maxminu;（s，s-i）=u对于所有i∈N 因此，任何参与人的最小最大值都不会小于他的最大最小值。■ 下面的命题说明，参与人在纳什均衡策略组（若这样的策略组存在）中的收益至少 等于他的最小最大值。 命题6.3假设策略型博弈T=<N，（S），（u））有纯策略纳什均衡（s，，s）。 那么 ui（s，，s）≥U；对于所有i∈N 证明：首先，注意，对于所有i证N， u（s²,··,s）=maxu;（ss) 然后，注意 maxu;（Si，s;）≥minmaxu;（si，S-i）对于所有i∈N 由上面的两个不等式可知， ui（s，"，S）≥U;对于所有i∈N 注释上面的讨论表明参与人在纯策略纳什均衡（若这样的均衡存在）中的收益大 于或等于他的最小最大值，而又大于或等于他的最大最小值。

6.7展开型博弈的均衡 我们已在第3章简要研究了展开型博弈。现在我们再次考察这种重要的博弈类型， 并且引人所谓子博弈完美均衡这个解概念。我们仅讨论完美信息展开型博弈。 定义6.5（子博弈）给定展开型博弈T以及它的一个非终止历史（non-terminal history）h，h之后的子博弈（thesubgamefollowingh）是指历史h发生后仍存在的那 部分博弈。 例6.15考虑图6—1（a）中的进人市场博弈。图6—1（b）画出了该博弈唯一的 真子博弈（propersubgame）。图6—2（a）画出了另外一个展开型博弈。图6—2（b) 和图6一2（c）分别画出了这个博弈的两个真子博弈。 挑战者 进入 不进入 在位者 在位者 接受 斗争 1,2 接受 斗争 0,0 0,0 纯策略纳什均衡 2，1 2，1 (a) (b) 图6一1进入博弈及其对应于历史（进入）的子博弈 （2，0） (1，2) (0，0) (1,2) (0，0) (1，2) (0，0) (a) (b) (c) 图6一2另外一个博弈及其他两个子博弈，图（b）中的子博弈对应历史（C）， 图（c）中的子博弈对应历史（C，E） 口展开型博奔的纯策略纳什均衡 展开型博弈的纳什均衡概念类似于策略型博弈的纳什均衡。它的正式定义如下。

定义6.6给定展开型博弈T=（N，（A），H，P，（I;），（u）>及其一个策略组 s*=（s，·"，s），若对于所有i∈N， u;（O（s，s=;））≥u;（O（si，s=;））对于所有s∈S 则s*是该博弈的一个纯策略纳什均衡。其中：S是参与人i（i=1，2，"，n）的所有 策略组成的集合；O（·）表示对应于策略组的结果。 例6.16考虑进人博弈（见图6一1（a））。等价于该博弈的策略型博弈的收益矩阵为 接受 斗争 进人 2，1 0，0 不进人 1，2 1，2 显然，（进人，接受）和（不进入，斗争）都是纯策略纳什均衡。注意，参与人1偏好 （进人，接受）这个均衡，因为它带给参与人1的效用更大；参与人2偏好（不进人， 斗争）这个均衡，因为它带给参与人2的效用更大。 另外，注意，纳什均衡（进人，接受）符合直觉，这是因为策略“接受”是参与人 2在他的决策节点上的有效和最优反应。均衡（不进入，斗争）多少不符合直觉，因为 参与人1选择“不进入”策略将使参与人1停留在博弈树的枝叶上，因此参与人2不需 要选择任何策略。然而，我们可以将均衡（不进人，斗争）解释为参与人2对参与人1 的下列威胁：“如果你进人，我将斗争。”这样的威胁未必是可信威胁（credible 博奔论与机制设计 threat)，但它的确描述了当博弈参与人偏离理性行为时出现的最差情形。子博弈完美均 衡（稍后讨论）以符合逻辑的方法解决了这个问题。 展开型博弈的纯策略纳什均衡概念没有考虑参与人在展开型博弈中的行动顺序。纳 什均衡仅将策略视为参与人在博弈进行之前做出的一劳永逸的选择。口 例6.17回忆一下，在图6一2（a）中的展开型博弈中，参与人1和2的策略集分 别为： S={CG,CH,DG,DH} S={E,F} 等价策略型博弈的收益矩阵为 E F CG 1，2 3,1 CH 0，0 3，1 DG 2，0 2，0 DH 2，0 2，0 它有三个纯策略纳什均衡，即（DH，E)，（DG，E）以及（CH，F）。口 口子博弈完美均衡 子博弈完美纳什均衡（subgameperfectequilibrium，SGPE）考虑到了博弈的每个可能

历史，并且保证在给定其他参与人策略的情形下每个参与人的策略都是最优的，这里的最 优是指不仅从博弈一开始就是最优，每个可能历史之后仍为最优。下面给出正式定义。 定义6.7（子博弈完美均衡）给定展开型博弈T=（N，（A），H，P，（I：），（u）> 及其一个策略组s*=（s，"，s），若对于所有iN， ui（Oh（s，s-i））≥ui（Oh（si，s=;)）对于所有h∈{x∈sH：P（x）=i}； 对于所有s:ES 则s*是一个子博弈完美均衡（subgameperfectequilibrium，SGPE），其中O（s，s;） 表示对应于历史h的结果，这里的h是策略组（s，s-：）中的历史。 例6.18在进入市场博弈（见图6一1（a））中，我们已经看到（进入，接受）和 （不进入，斗争）都是纳什均衡。然而，策略组（不进入，斗争）不是一个子博弈完美 均衡，因为在对应于历史（进人）的子博弈中，“斗争”不是参与人2的最优策略。它 背后的道理在于，如果挑战者偏离（不进入，斗争）而选择了“进入”策略，那么参与 人2将处于不利地位，因为“斗争”不是他的最优反应。 在图6一2（a）所示的展开型博弈中，我们已经看到（DH，E）、（DG，E）和 （CH、F）这三个策略组都是纳什均衡。然而，只有（DG，E）是一个子博弈完美均衡。口 口纳什均衡与子博奔完美均衡 由子博弈完美均衡的定义可知，子博弈完美均衡是一个能在每个子博弈中都诱导出 纳什均衡的策略组。因此，子博弈完美均衡总是纳什均衡，但纳什均衡未必是子博弈完 第 美均衡，前面的例子已说明了这一点。 章 在展开型博弈的纳什均衡中，给定其他参与人的策略，每个参与人的策略对于整个 纯 博弈来说都是最优的。它未必对于每个子博弈都是最优的。然而，如果参与人使用纳什 策 均衡策略，那么对于它所到达的任何子博弈来说，它都是最优的。另一方面，每个参与 略 纳 人的子博弈完美均衡策略对于每个可能的历史（只要参与人使用子博弈完美均衡策略， 无论这些历史发生与否）都是最优的。 均 衡 在纳什均衡中，每个参与人都有着与其他参与人博弈的长期经验，他对其他参与人 的行动有正确的信念。他相信其他参与人不会偏离他们的行动。给定这些信念，纳什均 衡策略是最优的。 子博弈完美均衡对其他参与人的行动没有做出这样的假设要求。子博弈完美均衡概 念考虑了每个参与人偏离子博弈完美均衡行为的可能性，即使是很少出现的可能性。每 个参与人对其他参与人的策略有着正确的信念，并且知道与纳什均衡相比，子博弈完美 均衡对其他参与人的偏离行为提供了更强的保障，也就是说，其他参与人更不愿意偏离 均衡策略。 6.8小结与参考文献 在本章，我们引I人了纯策略纳什均衡（PSNE）这个核心概念。一个纯策略纳什均

衡就是一个策略组（s，"，s），它使得任何参与人单方面偏离自己的均衡策略都无 利可图（单方面偏离是指仅有某个参与人偏离而其他参与人不偏离他们的均衡策略）。 我们也可将纯策略纳什均衡定义为一个策略组（s，，s），它使得每个参与人的策 略s都是对其他参与人均衡策略s；的最优反应。下列要点值得特别注意。 ·纯策略纳什均衡可能不能向参与人保证其他参与人不会单方面偏离。例如，在囚 徒困境博弈中，（C，C）是一个纯策略纳什均衡。如果参与人1坚持使用策略C，但参 与人2偏离C而改为使用策略NC，那么参与人1的效用从一5增加到一1。 ·纯策略纳什均衡不能保证参与人的多边偏离（或说共同偏离）。例如，在囚徒困 境博弈中，如果两个参与人都偏离（C，C）而改用（NC，NC），那么他们的状况都 变好。 ·纯策略纳什均衡可能不对应着社会最优结果。再次以囚徒困境为例，均衡策略 （C，C）带来的总效用为一10，而非均衡策略（NC，NC）的总效用为一4。 ·策略型博弈未必有纯策略纳什均衡（例如，硬币配对博弈，或者采购博弈）。 ·策略型博弈可能有多个纯策略纳什均衡，而且既定参与人在不同纯策略纳什均衡 中的收益可能不同。 ·每个优势策略均衡也是一个纯策略纳什均衡。 纯策略纳什均衡有多种解释方法：（a）作为咨询师提供的每个参与人都愿意接受的 指示；（b）作为重复博弈的自然而然的预测结果；（c）作为参与人达成的自我实施协 博 议；（d）作为演化过程的稳态结果。在使用这些解释时，读者要根据具体模拟环境，选 奔 论 择合适的那种。 与 我们介绍了参与人的最大最小值或称安全值概念，它描述了当其他参与人自由选择 机 制 任何策略而导致的最差情形出现时，他能保证自已得到的最小收益。我们还介绍了参与 设 人的最小最大值概念，这是其他参与人能强加给他的最小收益。如果纯策略纳什均衡存 计 在，那么任何参与人在该均衡下的收益大于或等于他的最小最大值，他的最小最大值又 大于或等于他的最大最小值。 我们还考察了展开型博弈的纳什均衡概念和子博弈完美均衡概念。在本书中，我们 主要关注策略型博弈。因此，对于展开型博弈和子博弈完美均衡，我们不再进一步 研究。 本章讨论的材料主要来自MyersonL6]以及Osborne andRubinstein[7]。由Tardos andVaziraniL1所写的论文，很好地介绍了博弈论中的概念。事实上，我们从该论文中 摘取了很多例子。 关于纳什均衡的有趣讨论，可参见Osborne[8]，Straffin[9]，Maschler，Solan， andZamir[5]，以及Binmore[10]。 众所周知，纳什均衡的概念是由约翰·纳什在其博士论文中提出的，它发表于参考 文献[11，12]。关于纳什均衡的深层洞见可参考Holt andRoth[3]。 本章关于子博弈完美均衡的大多数材料，要归功于Osbornel8]。关于子博弈完美均 衡的更多细节，读者可参考此文献。关于展开型博弈的详细讨论，读者可参考Myer- son[6]以及Maschler，Solan，and Zamir[5]。

口参考文献 [1]E.Tardos and V.Vazirani.“Introduction to game theory:Basic solution con- cepts and computational issues".In:Algorithmic Game Theory.Ed.by Noam Nisan, Tim Roughgarden,Eva Tardos,and Vijay Vazirani.Cambridge University Press, 2007，pp.3-28. [2]Noam Nisan, Tim Roughgarden, Eva Tardos,and Vijay Vazirani (Editors). AlgorithmicGameTheory.CambridgeUniversityPress,2007. [3] Charles A. Holt and Alvin E. Roth.“The Nash equilibrium: A perspective”. In:Proceedingsof theNational Academy of Sciences 101(2004),pp.3999-4002. [4]Robert J.Aumann.“Agreeing to disagree”.In:The Annals of Statistics 4(6) (1976)，pp.1236-1239. [5]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam- bridgeUniversityPress,2013. [6]Roger B.Myerson.Game Theory:Analysis of Conflict.Harvard University Press,Cambridge,Massachusetts,USA,1997. [7]Martin J.Osborne and Ariel Rubinstein.A Coursein GameTheory.Oxford UniversityPress,1994. [8]Martin J.Osborne.AnIntroduction to GameTheory.TheMIT Press,2003. 第 [9]Philip D.Straffin Jr.Game Theory and Strategy.The Mathematical Associa- 6章 tion ofAmerica,1993. [10]Ken Binmore.Fun and Games:A Text On Game Theory.D.C.Heath & 纯策 Company,1992. 略纳什均饰 [11]John F.Nash Jr.“Equilibrium points in n-person games”.In:Proceedings oftheNationalAcademyofSciences36(1950)，pp.48-49. [12]John F.Nash Jr.“Non-cooperative games”.In:Annals ofMathematics 54 衡 (1951)，pp.286-295. 6.9习题 （1）证明在策略型博弈中，任何强（弱）（极弱）优势策略均衡也是纯策略纳什 均衡。 （2）我们已经看到两人对称策略型博弈的形式为S=S2，u1（s1，s2）=u2（s2，si）， 对于所有siES以及s2ES2。证明在这样的博弈中，策略组（s，S）是纯策略纳什 均衡当且仅当策略组（s2，s*）也是纯策略纳什均衡。 （3）找出下列博弈的纳什均衡、最大最小值、最小最大值、最大最小策略以及最小 最大策略。

A B A 0，1 1,1 B 1,1 1，0 （4）对于第4章讨论但未在本章讨论的那些博弈，分别找出它们的纯策略纳什均 衡、最大最小值、最小最大值、最大最小策略以及最小最大策略。 （5）找到下列博弈的纯策略纳什均衡、最大最小值、最小最大值、最大最小策略以 及最小最大策略。： X Y Z A 6，6 8,20 0，8 B 10，0 5，5 2，8 C 8，0 20，0 4，4 （6）找到下列两人博弈的纯策略纳什均衡、最大最小值、最小最大值、最大最小策 略以及最小最大策略。 A B C D A 5，2 2，6 1，4 0，4 B 0，0 3，2 2，1 1,1 博奔论与机制设计 C 7，0 2，2 1，5 5，1 D 9，5 1，3 0，2 4,8 （7）证明在策略型博弈中，参与人的强优势策略也是他的最大最小策略。类似的结 论对弱优势策略成立吗，对极弱优势策略成立吗？ （8）对于布雷斯悖论博弈（其中，AB路未打通），我们已得到了纳什均衡（即满 足500辆车走路线A，另外500辆车走路线B的那些策略组）。除此之外，还有没有其 他纳什均衡？在AB路打通的情形下，除了对应于所有车辆都走路线AB这样的均衡之 外，还有其他均衡吗？ （9）对于下列情形，分别举出两人纯策略博弈的例子。 （a）这个博弈有唯一的纳什均衡，但它不是弱优势策略均衡。 （b）这个博弈有唯一的纳什均衡，它是一个弱优势策略均衡但不是一个强优势策略 均衡。 （c）这个博弈有两个均衡，其中一个为强优势策略均衡或弱优势策略均衡，但另外 一个均衡仅是纳什均衡。 （10）（关于第一价格密封拍卖）假设两个参与人1和2对拍卖物的估价分别为v 和v2。他们的报价是某个单位的整数倍（即为离散的）。谁报价高谁中标，并按照自己 的报价付款。如果两人报价相同，则每人以1/2的概率得到拍卖物。计算这个博弈的纯 策略纳什均衡。 （11）计算下列两人博弈的纳什均衡。在这个博弈中，

S={0，1}，S2={3，4} u（x，y）=-u2（x，y)=｜x-y1对于所有（x，y)∈{0，1}×{3，4} （12）考虑策略型博弈：N={1，2}；S=S2=[a，b]×[a，b]，其中a和6都是 正实数且a<b。也就是说，每个参与人同时在矩形[a，6]×[a，6]中选择一点。将受 益函数定义为： u1（s1,S2）=-u2（s1，S2）=d（s1，S2) 其中d（si，S2）是点s和s2之间的欧几里得距离。请计算这个博弈的所有纯策略纳什 均衡。 （13）考虑博弈（N，（S），（u）>，其中N={1，"，n}，s=N，对于所有iEN。 u;（s1，.，sn）=a>0若s1=·.·=sn=k =0其他 计算这个博弈的所有纯策略纳什均衡。 （14）在庇古网络博弈中，计算当n=3和n=4时的所有纯策略纳什均衡。将你的 发现推广，写出对于一般n值的所有纯策略纳什均衡。 （15）在庇古网络博弈中，当n为偶数时，证明任何满足下列条件的策略组都能使 社会福利最大，即选择策略A的参与人个数等于选择B的参与人个数。考察当n为奇 数时的情形。 （16）在庇古网络博弈中，假设路线A的成本函数为，对于所有xE[0，1]，c（r）= 第 x，其中p>0是一个实常数。确定这个博弈的纳什均衡。 章 （17）考虑下列策略型博弈（网络构型博弈）。网络的节点为参与人：N={1， 2，"，n}。参与人i的策略集S：是由N{i}的所有子集组成的集合。节点的策略是 纯 策 确定它想与哪些节点链接。一个策略组对应着一个特定的网络或图。假设。（0«1） 略 纳 是一条链接上的每个节点得到的收益，而c>0是每个节点为维持该链接而承担的成本。 仕 另外，假设o是k跳（k-hop）关系带来的收益，其中k是两个相关节点之间的最短路 均 衡 径的长度。一个链接只有相互都同意时才能建立，但可以单方面终止。给定由策略组形 成的图g，令节点i的效用u;（g）为 u;(g)=∑o(e）-c.d;(g) 法i 其中L（g）是i和j之间的最短路径上的链接个数，d：（g）是节点的阶（degree）。给定 一个网络，若它能使所有可能网络上的所有节点的效用之和最大，那么我们说该网络是 有效率的。给定一个网络，如果任何一对未链接的节点都没有激励建立彼此间的链接， 而且任何节点都没有激励终止现有链接，那么称这个网络为成对稳定的（pairwisesta ble）。对于这个博弈，证明下列两个结果。 ·若c<o一，则唯一有效率的网络是完全网络（completenetwork）。 ·若c<一，则唯一成对稳定网络是完全网络。 （18）考虑所谓的最后通博弈。在这个博弈中，有两个参与人1和2。参与人1 向2提供数额为0≤x≤c的钱，其中c是一个常数。参与人2要么接受，要么拒绝。如

果参与人2接受，那么参与人2得到的钱数为x，而参与人1得到c一x。如果参与人2 拒绝，那么这两人的收益都为零。画出博弈树，计算所有纳什均衡，计算所有子博弈完 美均衡。 （19）对于可观察的硬币配对博弈，计算所有纳什均衡以及所有子博弈完美均衡。 （20）考虑因徒困境博弈的序贯版本，其中参与人1先行动，参与人2后行动。计 算这个博弈的所有纳什均衡和所有子博弈完美均衡。 （21）找出下列博弈的所有纳什均衡和所有子博弈完美均衡。 2,1 3，0 0，2 1，3 （22）（编程题）给定一个有限的n人策略型博弈，编程使之能产生： ·所有强优势策略； 博奔论与机制设计 ·所有弱优势策略； ·所有极弱优势策略； ●强优势策略均衡（若存在）； ·所有弱优势策略均衡（若存在）； ·所有极弱优势策略均衡（若存在）； ·所有纯策略纳什均衡（若存在）； ·每个参与人的最大最小值及其所有最大最小策略； ·每个参与人的最小最大值以及针对每个参与人的所有最小最大策略组。