纳什均衡的存在性 纳什均衡的存在性是博弈论中被广泛考察的一个重要议题。在上一章，我们已经 看到，对于伴随有限策略集的两人零和博弈，最小最大定理保证了它存在着至少一个 博奔论与机制设计 混合策略均衡。约翰·纳什在他的伟大著作[1,2]中将均衡概念推广到三人或三人以上 博弈，而且证明了每个有限策略型博弈都存在着至少一个混合策略纳什均衡。可以证 明，纳什均衡是适当定义的映射的不动点。事实上，博弈均衡的存在性与不动点 （fixedpoints）定理紧密相伴，这样的不动点定理有布劳威尔（Brouwer）不动点定 理[3]、角谷（Kakutani）不动点定理等[4]。本章将学习这些重要结果。我们还给 出了组合理论中的一个著名结果，即施佩纳（Sperner）引理。这个引理可被用于证 明不动点定理和纳什定理。第33章（数学附录）给出了理解本章内容所要求的数 学知识。 本章结构如下。我们首先定义对应和不动点，然后给出布劳威尔不动点定理和角谷 不动点定理。接下来，我们证明纯策略纳什均衡和混合策略纳什均衡都是适当定义的对 应的不动点。* 其次，我们考察策略型博弈中纯策略纳什均衡的存在性，给出并证明了保证这种均 衡存在的充分条件。这一点的证明关键依赖角谷不动点定理。接下来，我们再次使用角 谷不动点定理证明纳什定理。 再次，我们提供了纳什定理的另外一种证明方法，即使用施佩纳引理证明它。在这 一部分，我们首先给出并证明了施佩纳引理。然后，我们说明如何使用布劳威尔不动点 “对应于”区别开，我们会把后面这样的表达写全，尽管根据上下文也能知道这一点。一译者注

定理证明纳什定理。 最后，我们简要回顾了无限博弈的纳什均衡的存在性问题。 10.1对应以及不动点定理 假设n和k都是正整数。给定集合XCR”以及另外一个集合YCR，一个从X映到 Y的对应（correspondence）或称集函数（setfunction），对每个xEX都指定了Y的一个子 集（包括Y本身），即对于每个xEX，f（x）二Y。我们将这个对应记为：f：X二Y。这样 的函数也称为集值函数（set-valuedfunction）。 注意，当对于每个x，f（x）恰好含有一个元素时，f就变成了普通函数。 对应的图 令XCR”，令YCR是一个闭集。f：X=Y这个对应的图（graph）是集合{（x，y）： xEX,yEf(x)}。 闭图对应 给定XCR”以及闭集YCR，对于对应f：X=Y，若对于任何两个序列x"→xE X以及y"→yEY（其中对于每个m，x"∈X且y"∈f（x"）），我们都有y∈f（x），则 称f：X二Y有一个闭图（closedgraph）。 第 上半连续 章 给定XCR”以及闭集YCR，若f：X二Y这个对应有闭图，而且在f这个对应 纳什均 下，紧集的像是有界的，则称f是上半连续的（upperhemicontinuous）。 上面这个定义也意味着在f这个对应下，紧集的像事实上也是紧的。对应的上半连 衡 续性是函数的连续性这个概念的自然推广。 的 存在性 口不动点定理 不动点定理为证明均衡方程组的解的存在性提供了非常有用的结果。这里涉及的思 想是，将问题视为寻找适当构造的函数或对应的不动点。 函数的不动点 令XCR”，令f：X→X是一个映射。给定点xEX，若f（x）=x，则称点x是映射 f的一个不动点（fixedpoint）。 我们立即给出一个例子，假设f：[0，1]→[0，1]并且f（x）=x²。f有两个不动点 即0和1，因为f（0)=0，f（1)=1。 布劳威尔不动点定理 这个著名的定理可以追溯到1912年（BrouwerL3]），我们可用它证明每个两人零和 博弈存在着至少一个混合策略纳什均衡。这个定理的内容如下。 定理10.1[布劳威尔（Brouwer）不动点定理]令XCR”非空、紧且凸。若f：X→ X连续，则f有不动点。

对应的不动点 令XCR”，令f：X=X是一个对应。给定点xEX，若xEf（x），则称x是f的 一个不动点。 角谷不动点定理 这个著名的定理来自Kakutani4]，它广泛用于博弈论范畴。事实上，约翰·纳什 在他的博士论文中使用这个定理证明了有限策略型博弈存在着混合策略纳什均衡。这个 定理也被用于证明有限博弈存在纯策略纳什均衡的充分条件。 定理10.2[角谷（Kakutani）不动点定理]假设XCR”是R”的一个非空、紧且 凸的子集。令f：X二X是一个满足下列条件的对应： （a）f是上半连续的， (b）f（x)CX，VxEX为非空且凸的， 则f在X中有不动点。 10.2纳什均衡是不动点 在本节，我们证明策略型博弈的纯策略纳什均衡和混合策略纳什均衡，是适当定义 的对应的不动点。 口纯策略纳什均衡是不动点 考虑策略型博弈T=<N，（S），（u;）>。我们已经知道，策略组（s，，s）是 一个纯策略纳什均衡当且仅当 sEb;（s)iEN 其中b：是最优反应对应[对于每个s-：ES-i，最优反应对应b都给出了参与人i（针对 s-i）的所有最优策略]： b;（s-i)={s;∈Si:u(sis-i)≥u;(si，s-i）Vs∈S;} 令复合对应（compositecorrespondence）b：SS的定义如下： b（s1,·".,Sn)=b（s-1)X·..Xbn（s-n) 我们知道s*=（s，，s）是一个纳什均衡当且仅当s∈b（s;），Vi∈N。这等 价于 （s²，··.,s）∈b（s=1)X··Xbn（sn) 这又意味着 （s，·…·,S)∈b（s，·…·,S) 这等价于说s*是对应b（·）的一个不动点。 例10.1考虑囚徒困境博弈，它的收益矩阵如下

NC C NC -2，-2 -10，-1 C -1，-10 -5，-5 注意，S=S2={C，NC)，以及b（C)=b（NC)=b2（C)=b2（NC)={C}。下面我们给 出不同策略组的最优反应对应： b（NC,NC)=b（C)Xb(C)={（C,C)} b（NC,C)=b（C)×b（NC)={(C,C)} b（C,NC)=b(NC)Xb（C)={（C,C)} b（C,C)=b（NC)xb(NC)={（C,C)} 显然，最后一个等式意味着（C，C）是一个纳什均衡。口 口混合策略纳什均衡是一个不动点 现在考虑混合策略。我们已经知道，混合策略组（o，"，o）是一个纳什均衡 当且仅当 oEb;(oi)ViEN, 其中b;是最优反应对应，b：的定义如下 b;(o-i)={o;∈△（S;）:u;(oio-i)≥u;(oo-i)Vo∈△（S;）}。 纳什均衡的存在性 类似纯策略情形下的复合对应，我们将混合策略情形下的复合对应 b:△（S)X·X△（S)△（S)X·X△(S) 定义为 b（o1,.,0n)=b(o-1)×·..×bn(o-n)。 显然，混合策略组。=（o，，o）是一个纳什均衡当且仅当。∈b（o*），即当且仅 当。*是最优反应对应6的一个不动点。 10.3 纯策略纳什均衡存在性的充分条件 策略纳什均衡的存在性提供了充分条件。我们首先给出并证明一个重要引理。 引理10.1假设集合S，S2，，S都是某个欧几里得空间的非空、紧且凸的子 集。再假设u：SX·…·XS→R关于（s，，sn）是连续的，而且u（s，s-）关于s 是拟凹的（quasi-concave）。将参与人i的最优反应对应定义为

b;（s-i)={s∈Si:u;(siS-i)≥u;（sis-)Vs∈S;} 则： （a）对于每个s-;ES-i，b;（s-;）是非空的； （b）对于每个s-∈S-i，b;（s-i）是凸值的； （c）b;（s-：）是上半连续的。 证明：我们首先证明b;（s-）非空。根据定义，b：（s-：）是紧集S上的连续函数ui 的最大化算子集（注意，集合S=S×…·×S是紧的，这是因为S，S2，，S都是 紧的）。因此，根据魏尔斯特拉斯（Weierstrass）定理，函数u;达到最大值，因此 b;（s-;）非空。 接下来，我们证明b（s-）是凸值的。根据题设，u关于s拟凹。这表示u（·，s-） 在S上是拟凹的。固定s-并且记u（x，s-：）=u（x）。根据拟凹的定义可知，对于Va∈ R，每个集合U（a)={xES：u（x）≥a）都是凸的（其中U（a）是u在a点的上轮廓 集，参见第33章数学附录）。令 a=maxu;（x) rES; （根据魏尔斯特拉斯定理可知，maxu;（x）一定存在，所以我们可以令α=maxu;（x）。） rES 于是，根据定义可知，由一个拟凹函数的所有最大化算子组成的集合是一个凸集。因 此，b;（s-：）是一个凸集。 博奔论与机制设计 现在，我们证明b：是上半连续的。为此，我们必须证明： （1）b;有闭图。也就是说，对于任何满足s∈b;（s;），Vn的序列（s，s;）→（si， s-），我们都有s∈b;（s-i）。 （2）b;将紧集映人有界集。容易看到，集合U=b：（s-：）是有界的。 为了证明（1），注意给定（s，s：）→（s，s-），其中s∈b;（s），Vn。这意味着 u;（s，s）≥u;（s，s;），Vs∈S，Vn。由于u;是连续的，我们有 u;(s²s²i)-u;(siS-i) u;(si,s;)→u;（sis-i) 这意味着 u;(si,s-i)≥u;(sis-i),Vs∈Si 这又意味着s;∈b;（s-：）。这说明b:有闭图。 定理10.3给定策略型博弈T=（N，（S），（u）>，如果对于Vi∈N， （1）S：是（某个欧几里得空间的）非空、凸且紧的子集； （2）u;（s1，，Sn）关于（s1，，Sn）是连续的； （3）u;（s，s-i）关于s为拟凹的。 那么这个博弈有纯策略纳什均衡。 证明：我们已经知道，纯策略纳什均衡是最优反应b：S二S的不动点，其中b： SS的定义为

b（s1,.,sn)=b（s-1）×·.Xbn（s-n) 注意，S=S×·×S为非空、紧且凸的，这是因为每个S；都是非空、紧且凸的。另 外，注意，根据引理10.1可知，6（·）是一个非空、凸值且上半连续的对应。由于 b（·）满足角谷不动点定理的所有条件，因此根据这个定理我们断言：6这个对应有 不动点，这个不动点正好是一个纯策略纳什均衡。这样，我们就完成了该定理的证 明。■ 现在，我们做出以下观察： ·对于伴随有限策略集（每个策略集含有两个或两个以上元素，即不是单点集）的 博弈而言，由于这些策略集不是凸的，因此不适用上面的结果。 ·上面的结果仅提供了充分条件。我们已经看到很多有限博弈有纯策略纳什均衡。 这些例子说明这些条件不是必要条件。 ·这个结果没有说明纳什均衡何时是唯一的。 ·在上面的定理中，拟凹条件不可放松，下面的例子说明了这一点。 例10.2在某个博弈中：N={1，2}；两个参与人同时在边长为1的正方形中各选 一点；收益矩阵为 u（s1，S2）=d（s1，S2）Vs，S2∈[1,2]×[1,2] u2（s1，S2）=-d（s1，S2）Vs1，S2∈[1,2]×[1,2] 其中d（si，S2）是si点到s2点的欧几里得距离。在这个博弈中，如果两个参与人选择 第 了同一个点，那么参与人1有激励偏离这一点。另一方面，如果他们选择了不同的点， 章 那么参与人2有激励偏离自已选择的点。因此，这个博弈不存在任何纯策略纳什均 纳什均衡的存在性 衡。口 10.4纳什定理 现在，我们终于做好证明纳什定理的准备了。 定理10.4（纳什定理）每个有限策略型博弈T=（N，（S;），（u））存在至少一个 混合策略纳什均衡。 证明：我们分若干步骤证明这个定理。令S;={sa，，Sm}。注意， m; △（S;)={（x1,,xm）∈Rm:0≤xj≤1,Vj=1,,mi； 因此，△（S）CR。实际上，△（S)C[0，1]”，这意味着 （S)X··X△（S)C[0,1]mX··x[0,1]” （1）证明△（S）非空。 注意，△（S）是由S：上的所有概率分布组成的集合，因此对于Vi=1，"，n，

△（S）是非空的。 （2）证明△（S）为凸。 令入∈（0，1）为任意数。考虑△（S）的任意两个元素x=（x1，，m）与y= （y1，，ym）的凸组合： 入x+（1-x）y=入（x1，…,xm;)+（1-A)（y1，，ym;) =（ax+（1-x）yi,,入xm+（1-入）ym) 显然，0≤入x+（1-x）y;≤1，Vj=1，，m，V入∈（0，1）。考虑 m; ∑[ax+(1-x)y;]=∑x;+∑（1-)y;=>+(1-)=1 j=1 因此，入x十（1一入)y∈△（S）；因此，△（S）是凸的。 （3）证明对于i=1，，n，△（S）是紧的。 由于△（S）CR"，因此证明△（S）是紧的，等价于证明它是闭且有界的。注意， △（S）C[0，1”，因此立即可知△（S）是有界的。至于证明△（S）是闭的，我们将其 作为习题。 （4）证明u;（o1，，on）关于（o1，"，on）是连续的。 我们已经知道 博 弈论与机制设计 u;(o,··,on）=∑（IIo;(s;))u;(s,….,sn) （s）∈Sj=1 使用上面的式子，可以证明u（o1，“，o）是连续的。我们将其作为习题。 （5）证明u（o1，，o）关于o是拟凹的。我们将其留作习题。 （1）到（5）使得角谷不动点定理的条件得以满足，因此，对应6有不动点，这样 我们就证明了纳什定理。■ 注意，上面的定理仅为均衡的存在性提供了充分条件。它们不是必要条件，这意味 着即使这些条件未得以满足，纳什均衡仍可能存在。作为一个直接例子，注意，我们在 第5章讨论维克瑞拍卖（即第二价格密封拍卖）这个有着无限策略集的博弈时，已经证 明策略型博弈存在着纳什均衡（实际上为弱优势策略均衡）。 10.5施佩纳引1理 纽尔·施佩纳（EmanuelSperner）。对于不动点理论和博弈论中的重要定理的证明，这 个引理非常有用。特别地，我们可以使用这个引理证明布劳威尔不动点定理、角谷不动 点定理以及纳什定理。为了阐述施佩纳引理，我们需要下面的构造。本节的内容基于 VohraL6]在这个主题上的讨论。

口施佩纳引理需要的构造 考虑顶点为A、B和C的三角形，然后将其分成更小的三角形（称为三角化）， 分法如下。分别找到AC、BC以及AB的中点X、Y、Z。然后连接这三个中点。这 样，我们就得到了4个更小的三角形。如果我们再按上面的方法继续细分这4个三角 形，我们就得到了16个三角形，如图10一1所示（我们将每个更小的三角形都称为 子三角形）。这样的分法可以一直持续下去，从而得到64个、256个、…子三 角形。 X 第 章 B Z 纳什均衡的存在性 图10一1将三角形ABC三角化成16个子三角形 假设我们按照下列规则，对所有子三角形的顶点做标示（labeling）或染色（colo- ring): （1）AB边上的顶点只能标示为A或B，不能标示为C。 （2）AC边上的顶点只能标示为A或C，不能标示为B。 （3）BC边上的顶点只能标示为B或C，不能标示为A。 （4）完全位于原来大三角形内的顶点可以标示为A、B或C。 我们重点关注的子三角形是顶点分别为A、B和C的三角形（也就是说我们不关注 AAB、AAC、AAA这类具有相同标示的三角形），我们就把这样的子三角形全部找出 来，并且加上阴影。这些阴影子三角形可以分为两类：一是顶点A、B和C呈顺时针方 向；二是顶点A、B和C呈逆时针方向。为了区分这两类子三角形，我们给它们加上不 同阴影。 例如，我们对图10一1按照上述法则进行标记。图10一2给出了其中一种情 形。对于顶点A、B和C按照顺时针方向排列的子三角形，我们用斜线来加阴影 （称为浅阴影）；对于顶点A、B和C按照逆时针方向排列的子三角形，我们把它们 涂黑（称为深阴影）。注意，顺时针方向的子三角形（已加上浅阴影）有2个，逆

时针方向的子三角形（已加上深阴影即涂黑）有3个。令Nc表示顺时针方向子三 角形的个数，NAc表示逆时针方向子三角形的个数，那么在图10一2中，Nc=2， NAc=3。 B 图10—2含有Nc=2以及Nc=3的三角化 图10—3和图10—4分别给出了三角化的另外两种情形。图10—3只含有一个阴影 博奔论与机制设计 子三角形（其中顺时针0个，逆时针1个）；图10一4含有3个阴影子三角形（其中顺 时针1个，逆时针2个）。 B B B 图10-3含有16个子三角形以及 Nc=0且Nc=1的三角化

B C B 图10—4含有16个子三角形以及 Nc=1且NAc=2的三角化 口施佩纳引理及其证明 施佩纳引理说明按照上述规则标示的子三角形ABC的个数（等于Nc十NAc）总是 奇数。事实上，该引理断言NAc=Nc十1。这个著名结论的证明方法如下。这个证明依 赖于我们按照下列方法对边和三角形进行标示： ·如果一条边上的两个顶点有相同的标示（比如AA），那么我们将这条边标记 纳什均衡的存在性 为0。 ·如果一条边上的两个顶点有不同的标示（比如BA），而且这些标示按逆时针方向 排列（与原来的大三角形顶点排列方向相同），那么我们将这条边标记为1。 ·如果一条边上的两个顶点有不同的标示（比如AB），而且这些标示按顺时针方向 排列，那么我们将这条边标记为一1。 ·对于每个子三角形，将它的每条边标记的数字加起来，把这个加和写在这个子三 角形的内部并用小圆圈将这个数圈起来。将这个和称为该子三角形的施佩纳数（Sper- nernumber)。 对于图10一2中的三角化，我们可以计算每个子三角形的施佩纳数，并且将这个数 记在每个子三角形内。一般来说，施佩纳数有四种情形： （1）三个顶点不同且为逆时针（施佩纳数=3）； （2）三个顶点不同且为顺时针（施佩纳数=一3）； （3）三个顶点有相同的标示比如都为A（施佩纳数=0）； （4）三个顶点中有且仅有两个顶点的标示相同比如AAB（施佩纳数=0）。 我们分析这个大三角形的一条边。假设我们关注AB边。在这条边上，有更短的边 （这是子三角形的边）。注意， ·短边上的数字1，表示从A变化到B；

·短边上的数字一1，表示从B变化到A； ●短边上的数字0，表示没有变化。 图10—5画出了上面这些情形。 B 图10—5（对图10一2的三角化）计算每个子三角形的施佩纳数 在大三角形的AB边上，整体变化是从A变为B。因此，AB边上的各条短边的数 字之和等于1。类似地，BC边上的各条短边上的数字之和为1，AC边上的也为1。因 此，在大三角形三条边上的各条短边的数字之和等于3。 现在我们分析大三角形内部各条短边上的数字。注意，每条短边都是两个子三角形 的一条公共边，而且在这两个子三角形中，这条公共边上的数字要么都是0，要么在一 个子三角形中为1且在另外一个子三角形中为一1。因此，所有这些内部短边上的数字 之和等于零。因此，所有子三角形的所有边上的所有数字之和等于3。 注意，标示在所有子三角形内部的施佩纳数（即圆圈里的数）之和必定等于它们所 有边上的数字之和，因此等于3。显然，每个阴影子三角形的施佩纳数要么为3（逆时 针情形），要么为一3（顺时针情形），而且每个其他子三角形（即未加阴影的三角形） 的施佩纳数为0。这意味着NAc=1十Nc，因此（Nc十NAc）必定是一个奇数。 10.6·从施佩纳引理到布劳威尔不动点定理 口布劳威尔不动点定理 我们回忆一下布劳威尔不动点定理3]。这个定理的内容为：若XCR”是R”的一 个紧且凸的子集，而且函数f：X→X是一个连续函数，则f有不动点，也就是说，存 在x∈X使得f（x）=x。为了证明布劳威尔不动点定理，我们首先给出并证明它的一个

支撑引理。这里的证明源自文献[6]。我们首先定义n单纯形。 定义10.1（n单纯形）n单纯形（n-simplex）是集合 ”={x∈R”:xi≥0,i=1,2,，n； x=1} i=1 可以立即注意到，△”就是由所有概率分布（x1，C2，，r）组成的集合。可以证明， 这个集合是凸且紧的（我们将这个事实的证明留作习题）。 引理10.2若f：△"→△”是一个连续函数，则f有不动点。也就是说，存在着x∈ ”使得f（x）=x。 证明：当n=1和n=2时，这个引理的证明比较容易。n=2时的证明可参考文 献[6]。在这里，我们使用施佩纳引理证明n=3的情形。这个证明可以自然地推广到 n>3的情形。 下面我们证明：若函数f：△”→△是连续的，则它有不动点。假设f没有不动点。 令f(x）=（f（x），f2（x)，f3（x））。集合△3是一个平面三角形，这样我们可以按照标 准方法将其分成更小的子三角形。第一次细分，我们得到了4个三角形；第二次细分， 我们得到了16个三角形，以此类推。我们重点关注第m次细分。假设我们按照下列规 则对顶点（1，2或3）进行标示（或染色）：· c（x）=min{i:f（x）<xi} 如果f没有不动点，那么上述规则是一个明确定义的规则。为了证明这一点，假设它不 第 是一个明确定义的规则。这意味着 f:（x）≥xi，i=1,2，3，对于某个（x1，x2x）∈△3 章 由于x，f（x）∈△²，我们有x1十x2十x3=1以及f（x）+f2（x）+f（x）=1，这意味着 纳 什均 f（x）=x，i=1，2,3 衡 这与我们的假设（f没有不动点）矛盾。 的 存在性 上面的标示（或说染色）规则满足施佩纳引理要求的构造。原因如下： ●注意，c（1，0，0)=1；c（0，1，0)=2；c（0，0，1)=3。也就是说，大三角形 的三个顶点的标示都不相同（或说大三角形的三个角有三种颜色）。 ●假设x点位于三角形”的一条边上。例如，假设x位于（1，0，0）和（0，1，0） 之间的边上。注意，对于某个合适的入值（其中入E[0，1]），x=入（1，0，0)十（1一入)（0， 1，0）=（入，（1一入），0）。使用我们的标示（染色）规则可知，c（入，（1一入），0）=1或 2。这意味着”边界上的点有着施佩纳引理要求的标示（染色）。 将施佩纳引理运用到当前情形，我们断言，在”的第㎡次细分中，必定存在着一 个下面这样的子三角形：它的三个角（v，v2，）的颜色各不相同。参见图10一6。 不失一般性，我们有 c（²）=1;c（2）=2;c（）=3 令m→oo，考虑无穷序列 {}m≥1

图10一6在大三角形的第m次细分中，存在着一个子三角形，它的三个角 的颜色都不同（或者说它的三个顶点的标示不同） 这个序列可能没有极限，但由于3是一个紧集，因此该序列有收敛的子序列。因此， 对于适当的子序列}≥1，我们有 →x∈△对于某个x 类似地，我们可以证明→x以及→x。由于函数f：△²→△是一个连续函数，我 们有 f(u)→f(x) f(u)→f(x) f(u)→f(x) 由于c（）=1，因此f（）严格小于的第一个元素。由于c（）=2，因此f2（） 小于的第二个元素。由于c（）=3，因此f3（）严格小于的第三个元素。这意 味着 （x):（x)f:（x) 上面这些式子意味着 ≥() 然而，由于f：△3→△3，我们有 =()

这个式子成立当且仅当 f:（x）=xi对于i=1，2，3 这与我们最初的假设（f没有不动点）矛盾。这样，我们就证明了这个引理。■ 根据这个引理，我们现在可以证明布劳威尔不动点定理。 口布劳威尔不动点的证明 这个证明主要使用了紧且凸的集合在拓扑上的等价性，即如果X是紧且凸的集合， 其中X是（n一1）维的，那么X和△”在下列意义上是拓扑等价的：存在着映射g：X→ ”与g-：△"→X使得g与g-都是连续的。现在我们如下定义h：△"→△”。 h（x)=g(f(g-(x))) 由于f与g都是连续的，因此h也是连续的；根据引理10.2可知，h有不动点，不妨 称其为x。也就是说， h（x*）=g（f（g-（x*）))=x 这立即意味着 f(g-²（x*）)=g-²（x*) 这意味着g（x*）是f：X→X的不动点。这样，我们就证明了布劳威尔不动点定理。 第 10.7.使用布劳威尔不动点定理证明纳什定理 章 纳什均衡的 考虑有限策略型博弈T=<N，（S;），（u;）>，其中N={1，2，，n}。我们使用下 列符号 的 存在性 S={s：j=1,2,·，m}，其中m=｜S｜；i=1,…，n 我们现在利用布劳威尔不动点定理，证明上面这样的有限策略型博弈存在至少一个混合 策略均衡（纳什定理）。与以前一样，令△（S：）表示由S：上的所有概率分布组成的集 合，并且定义 M=△（S)X···X△（S) 每个o∈M都是向量，o含有IS丨个分量。假设s是参与人i的某个特定纯策略， iEN 令o是。中对应于s的分量。定义映射f：M→M，它将M中的向量映入自身。给定 分量。回忆一下，我们可以将o记为o=（o，o-：）。考虑 f（o)= ok+max（0,u;(Sk0-i）-u;（oi0-i）) ∑[o;+max(O,u;(S，o-i)-u;(oio-i))] ’s!s

注意，上式中的分母必定大于或等于1，这是因为 ∑=1 ’s>!s 另外，我们有 IS, 1 ∑f（o)=1,i=1,2,,n 显然，f：M→M是一个明确定义的映射。可以证明f是一个连续函数，因此，根据布 劳威尔不动点定理，f有不动点。也就是说，存在。∈M使得f（o）=o”。这意味着， ViEN，VsES，我们有 o+max（0,u;(soi）-u;（o，o）) =f（o）= ∑[o+max（0,u;(so）-u;(oo））] ES; 我们现在考虑两种情形。在第一种情形下， ∑[max（0,u;(so²)-u;（o²，o））]=0,Vi∈N ES; 在第二种情形下，对于至少某个证N，上式大于零。 在第一种情形下，我们有 ui（Sjo=;)-u;（oo;)<0,Vs∈S，Vi∈N 这立即意味着（o，o：）是一个纳什均衡。 在第二种情形下，至少存在着一个参与人i和策略sES，使得 max（0,u;（so=;)-u;(o0)）>0 这意味着 max(0,u;(so）-u;(o0）) ∑[max（0,u;（sjo;)-u;(o²，o²))] ’s>!s 这又意味着o≠0，由此可知o>0。基于以上事实，我们可以证明 ui（so:）>u;（o，o;）当且仅当o>0，Vsx∈S 这样，我们就得到了一个矛盾，这是因为u（o，o-：）是u（sk，o-：）的一个凸组合， 其中s∈S，>0。注意： （）²n=（o）²n<（o#s）²n=（o0）²n E8（0) ∈（) 因此，只有第一种情形能够发生；因此，（o，o-：）是一个纳什均衡。

10.8无限博弈的纳什均衡的存在性 考虑策略型博弈，但现在策略集为无限的。在这种背景下，混合策略以及均衡的定 义需要更具技术性的处理。特别地，我们要求策略集为紧的度量空间，目的在于便于数 学分析。Myerson7]描述了这里涉及的技术议题。Glicksbergl8]证明了该背景下存在着 混合策略纳什均衡。在给出这个结果之前，我们先定义一些概念。 口连续博弈 给定策略型博弈T=<N，（S），（u）>，其中参与人个数N为有限的，若ViEN， 策略集S是一个非空且紧的度量空间，而且u是一个连续函数，则T是一个连续博弈 (continuous game)。 ε纳什均衡 给定策略型博弈（N，（S），（u;））及其一个策略组（o，"，o），给定实数 E>O，若ViEN， ui（o，o-i)≥ui(oio-;)-eVoE△（S) 则（o，“，o）称为该博弈的一个e纳什均衡（e-Nashequilibrium）。 口格里克斯伯格的结果 纳什均衡的存在性 我们现在给出源于Glicksberg8的两个结果。 （1）每个连续博弈都有纳什均衡。 （2）对于所有ε>0，每个连续博弈都有纳什均衡。注意，（2）是（1）的直接 推论。 下面我们提供两个例子来说明连续性和紧性对于上面的结果是必要的。 例10.3（效用函数必须是连续的）考虑下面这个博弈：N={1}；S=[0，1]（这 是一个紧集）。将效用函数定义为下列非连续映射： u（s1）=s1对于0≤s1<1 =0对于si=1 可以证明，这个博弈没有混合策略纳什均衡。口 例10.4（策略集必须是紧的）考虑下面这个博弈：N={1}；S=[0，1）（这不是 紧集）。将效用函数定义为下列连续映射： u（s）=sVs∈[0,1) 可以证明，这个博弈没有混合策略纳什均衡。口

一些重要结果 Dasgupta andMaskinL9,10]为非连续博弈存在纳什均衡提供了充分条件。Si- mon[11]，Renny[12]，Carmona[13]进一步考察了非连续博弈的存在性。Myerson[7]详 细说明了连续博弈涉及的技术性议题。Moon[14]提供了综述。 10.9小结与参考文献 在本章，我们讨论了纯策略纳什均衡（PSNE）和混合策略纳什均衡（MSNE）。我 们依次讨论了下列结果： ·策略型博弈的PSNE和MSNE是适当定义的最优反应对应的不动点。 ·策略型博弈未必有纯策略纳什均衡。我们已经给出了保证PSNE存在的充分 条件。 ·纳什均衡存在性定理：每个有限策略型博弈有至少一个混合策略纳什均衡。这个 定理的证明主要使用了角谷不动点定理。 ·我们给出和证明了组合学中的一个著名结果，即施佩纳引理。这个引理可用于证 明布劳威尔不动点定理和纳什均衡存在性定理。 ·对于参与人为有限但策略集为无限的博弈，我们讨论了一些纳什均衡存在性 博 结果。 奔论与机制 纳什均衡的存在性这个经典结果最早出现于文献[1，2]。本章材料基于Myer- son[7]，Mas-Colell，Whinston，and Green[15]，以及Vohra[6]。另外，以下书籍也提 制 供了纳什定理的完美证明：Shoham andLeyton-Brown[16]，Maschler，Solan，and 设计 Zamir[17] 。 口参考文献 [1]John F.Nash Jr.“Equilibrium points in n-person games”.In:Proceedingsof theNationalAcademyofSciences36(1950),pp.48-49. [2]John F.Nash Jr.“Non-cooperative games".In:Annals of Mathematics 54 (1951),pp.286-295. [3]L.E.J.Brouwer.“Uber abbildung von mannig-faltigkeiten".In:Mathematishche Annalen71(1912),pp.97-115. [4]ShizuoKakutani.“A generalization of Brouwers fixed point theorem".In: DukeMathematicalJournal8(3)(1941)，pp.457-459. [5]GerardDebreu.“Asocialequilibriumexistence theorem”.In:Proceedingsof theNationalAcademyofSciences38(10)(1952)，pp.886-893. [6]Rakesh Vohra.Aduanced Mathematical Economics.CambridgeUniversity Press, 2009. [7]Roger B.Myerson.Game Theory:Analysis of Conflict.Harvard University

Press,Cambridge,Massachusetts,USA,1997. [8]I.Glicksberg.“A further generalization of theKakutani fixed point theorem with applications toNash equilibrium points".In:ProceedingsoftheNationalAcade- myofSciences 3（1952)，pp.170-174. [9]P.Dasgupta andE.Maskin.“The existence of equilibrium in discontinuous eco- nomicgames,I:Theory".In:TheReview of Economic Studies 53(1)（1986), pp.1-26. [10]P.Dasgupta and E.Maskin.“The existence of equilibrium in discontinuous e- conomic games,II:Applications".In:The Review of Economic Studies 53(1) (1986),pp.27-42. [11]L.K.Simon.“Gameswith discontinuous payoffs”.In:TheReview of Eco- nomicStudies54(4)(1987)，pp.569-597. [12]P.J.Reny.“On the existence of pure and mixed strategy Nash equilibria in discontinuous games".In:Econometrica67(5)(1999)，pp.1029-1056. [13] Guilherme Carmona.“An existence result for discontinuous games”.In: JournalofEconomicTheory144(3)(2009)，pp.1333-1340. [14]Moon Chetry.A surveyon computationalmethodsfor Nashequilibrium. Tech.rep.2010. [15]Andreu Mas-Colell,Michael D.Whinston,and Jerry R.Green.Microeco- 第 nomicTheory.OxfordUniversityPress,1995. [16]YoamShoham andKevinLeyton-Brown.MultiagentSystems:Algorithmic, 章 GameTheoretic,andLogicalFoundations.CambridgeUniversityPress,NewYork, 纳什均饰 USA,2009. [17]Michael Maschler,Eilon Solan,and Shmuel Zamir.Game Theory.Cam- 衡的存在性 bridgeUniversityPress,2013. 10.10习题 （1）回忆一下n单纯形的定义 u.=？0<x}= i=1 注意，△”是由所有概率分布（x1，x2，“，x）组成的集合。证明这个集合是凸且 紧的。 （2）证明10.5节纳什定理中的下列结果：对于每个iEN，△（S）是闭的。 （3）根据题目（1）中关于△”的定义，证明若f：△→△是一个连续函数，则f有不 动点。类似地，若f：△²→△²是一个连续函数，则f有不动点。 （4）考虑下列策略型博弈：

N={1,2} u（s1,s2）=d（s1,S2）Vs1，S2∈[1,2]×[1,2] u2（s1,s2）=-d（s1,S2）Vs1,S2∈[1,2]×[1,2] 其中d（si，S2）是s点和s2点之间的欧几里得距离。我们已经证明，这个博弈没有纯 策略纳什均衡。那么，这个博弈有混合策略纳什均衡吗？ （5）考虑下面这个博弈：N={1}；S=[0，1]。将效用函数定义为下列非连续 映射： u1（s）=s1对于0≤s1<1 =0对于s1=1 证明这个博弈没有混合策略纳什均衡。 （6）考虑下面这个博弈：N={1）；S=[0，1]。将效用函数定义为下列连续映射： u（s）=s1Vs∈[0,1] 证明这个博弈没有混合策略纳什均衡。