《博弈论：原理、模型与教程》第04章 Nash均衡解的特性 第02节 Nash均衡的存在性

《《博弈论：原理、模型与教程》第04章 Nash均衡解的特性 第02节 Nash均衡的存在性》由会员分享，可在线阅读，更多相关《《博弈论：原理、模型与教程》第04章 Nash均衡解的特性 第02节 Nash均衡的存在性（35页珍藏版）》请在装配图网上搜索。

1、博弈论：原理、模型与教程第一部分完全信息静态博弈第4章Nash均衡解的特性4.2 Nash均衡解的存在性（已精细订正！）本节推荐参考文献：（01 ）张石生不动点理论及应用（M）.重庆：重庆出版社，1984 年8月第1版.（注：有趣的是，该书的责任编辑尹明善，就是后来从摩配起步创业 成功的力帆老总）（02 ）张奠宙，顾鹤荣不动点定理（M）.沈阳：辽宁教育出版社，1989年4月第1版.（03）王则轲，左再思，李志强.经济学拓扑方法（M）.北京：北 京大学出版社，2002年1月第1版.将Nash均衡作为博弈的解，会面临这样的问题：Nash 均衡是 否存在，或者说对于所关心的博弈问题，是否一定存在Na

2、sh均 衡？非常庆幸的是，我们能够得到一个肯定的答案。下面将对本书所涉及的博弈论中一些经典的存在性结论进行介 绍。定理4-1（Nash均衡的存在性定理1, 1950）每一个有限的战略式博弈至少存在一个Nash均衡（包括纯战略和混合战略Nash均衡）。定理4-1是博弈论中关于Nash均衡存在性的最基本定理。1950 年，John Nash 在文章 Equi librium points in n-person games中首次提出Nash均衡的概念，并给出该存在性定理。无论怎样强调该 定理对于博弈论以后的发展的意义都不过分，因为Nash均衡之后的 博弈论的发展(尤其是非合作博弈论的发展)基本上都

3、是以该定理为 基石的。定理4-1的条件简单，但得出的结论却十分肯定。下面给出的定理的详细证明。供有兴趣的读者参考。为证明该定理，先给出如下必要的基本概念定义4-1从集合X到集合Y的一个规则f，若满足：Vx e X，都弗中 的一个集合f (x)与之对应，则称f为由X到Y的对应，记为f : X Y。简单地说，对应是函数概念的扩展，函数将集合X中的点映到Y 中的点，而对应将集合X中的点映到丫中的子集。对应f : X f Y的图像是指X X Y中的集合农,y) I x e X, y e f (x).对应f : X Y为上半连续的，是指Vx e X和Y中任意包含f (x )的 .开集v，在X中都存在x的

4、一个邻域U (x )，只要 x e U (x ), 就有 f (x) u V。显然对应的上半连续性为函数连续性概念的扩展，对应一 个函数它的上半连续性就等于它的连续性。对应f : X Y的图像为闭图，是指任意给定 xm e X, ym e f (xm), 若(xm, ym) (x, y),就有 y e f (x)。闭图将闭集的概念推广到集合的直积中。若对应f的值域Y为紧集 则f有闭图就意味着f为上半连续的。有了这些基本概念，下面证明 基本定理4-1.证明的基本思想是将Kakutani不动点定理应用于参与人的反应对应上。参与人面反应对应r为对手选择b时，r将每一个战略组合bi-ii映射到i的一个

5、混合战略集。给定对手选择b，给混合战略集中的每 -i个战略最大化参与人,的支付。这里虽然r只依赖于b，而不依赖于i-ib ,，仍将r写作b的对应，因为稍后会在战略组合空间之中寻找一个不动点。定义反应对应r: 为r的Cartesian直积，即 ir(b) = (r (b),., r (b)，则r的不动点为满足b e r(b)的战略组合b，S此对每个参与人，b. e r(b)，所以r的不动点即为一个Nash均衡。因此，对定理4-1的证明转化为证明参与人的反应对应具有不动点。由Kakutani不动点定理，r:ZZ,存在不动点的充分条件为: Z为有限维欧氏空间的紧的凸子集； Vb, r (b) 非空；

6、 Vb, r (b) 为凸;r (b )有闭在这里，若成立，即Z为紧集，且成立，则对应r为上半连 续的。下面分别证明这些条件满足：首先，因为Z,为维数为I 5 I-1的单纯形，所以满足。其次，因为每一个参与人的支付函数在自己的混合战略上是线性 的，因此也是连续的。连续函数在紧集上取得最大值，所以r(b )非空，满足。再次，为了证明，采用反证法若r(c)非凸，则存在b g r(Q)及b g r (b), 且存在/ (0,1)，使得Mb + (1 -人)b ” W r (b)，但对每一个，有u (Mb + (1 - M)b ”，b ) = Mu (b ,b ) + (1 - M)u (b “ b

7、)i11 - ii 1- ii 1， - i因此若b ，b ，是相对于。，的最优反应，那么它们的加权平均也是。而这与r(b)非凸矛盾，所以r(b)凸。最后，仍用反证法证明。假设不满足，则存在序列(b n , Cf n ) T (b , = ), Ct n G r (b n ),但b W r(b)，所以存在i , b W (b)。因此存在e0和b ，使得u (b,b ) u (b ,b ) + 3e。又因为 u 为连续的且(b n,b n) t (b ,b)，因i ii i, ii此对足够大的n，有u (b，.，b n ) u (b，.，b ) - 8 u (GT , b ) + 2 8 u (

8、GT n , b n ) + i 11i 1, - ii i - ii i - i所以对于b n , b产格优于 n，这与b n G r (b n )矛盾。所以满足。-iiii i至此，也就完成了有限博弈中Nash均衡的存在性的证明。在经济学和现实生活中也有很多无限博弈，即参与人的战略有无 限多个或参与人的战略能在一个集合中连续取值，如厂商之间的价格 或产量竞争。对应于这些情况有如下的存在性定理。定理4-2 （Nash均衡的存在性定理 2, Debru 1952,Glicksberg 1952,Fan 1952）对于战略式博弈g =（七） ），若S为欧氏空间的非空紧凸子集，支付函数关于战略组合

9、s连续，关于七拟凹， 则该博弈存在纯战略的Nash均衡。该定理的证明与Nash均衡的存在性定理4-1类似，支付函数关 于所有参与人战略组合的连续性意味着反应对应具有闭图。另外，支 付函数关于自己战略的拟凹性意味着反应对应为凸值的。同样运用 Kakutani不动点定理便可以证明该定理。注意:在上述定理中关于参与人战略组合的连续性条件是非常重 要的，它类似于有限博弈中期望支付关于混合战略是连续的，因此 Nash均衡的存在性定理4-1可以看作是该定理的特例。但同时在参 与人的支付函数上该定理的条件较Nash均衡的存在性条件强，但正 是因为较强的条件从而导致了较强的结果一一纯战略Nash均衡的存 在性

10、！在很多博弈中不存在纯战略的Nash均衡，但却存在混合战略 Nash均衡，因此将上述条件放松便得到相关条件下关于混合战略的 存在性结论。定理4-3（Nash均衡的存在性定理3, Glicksberg 1952） 对于战略 式博弈g * r；（ *）；（气），若战略空间s.为距离空间中的非空紧子集， 支付函数.关于战略组合,连续，则该博弈存在混合战略的Nash均衡（将纯战略Nash均衡作为混合战略Nash均衡的特例）。在上述关于Nash均衡的存在性定理4-2和定理4-3中，都要求 参与人的支付关于所有参与人战略组合的连续性，在经济学的一些理 论或应用中，非连续性或非拟凹的收益函数是很常见的。如果

11、有不连 续的收益，则一个紧的战略空间就不再确保参与人对应其对手战略的 最优反应一定存在。为了探寻此时均衡的存在性，Dasgupta进一步 对以上存在性条件进行放松，得到如下存在性定理。定理4-4 （Nash均衡的存在性定理4, Dasgupta和Maskin 1986） 对 于战略式博弈G =（*）;（.），若对于所有的,，S为有限维欧氏空 间的非空紧凸子集；.关于七拟凹，关于s上半连续且 Max气（七，七）关于s连续，则该博弈存在一个纯战略的Nash均 s i衡。该定理的证明仍然与前述定理的证明类似，仍然采用Kakutani 不动点定理，其中收益函数关于自己战略的拟凹性保证了反应对应的凸值性

12、，的极大值关于s，的连续性及的上半连续性保证了反应对 应具有闭图，因此证明过程类似定理4-1,这里不再重复。在上述定理的基础上，Dasgupta继续对u的连续性及拟凹性进 行放松，得到了当支付函数只在战略集的某个子集上不连续时，相关条件下混合战略均衡的存在性。其思想是用有限分割去近似战略空 间，证明的方法仍然是用Kakutani不动点定理。由于涉及一些较复 杂的数学名词的解释，这里不再介绍，建议有兴趣的读者参阅相关文 献。至此为止，所列出的关于Nash均衡的存在性结论其证明思想都 是Kakutani不动点定理。从数学上看，以上一系列的存在性定理都 是在不断放松Kakutani不动点定理成立的条

13、件，而且都在试图不断 放松对支付函数的要求以满足Kakutani不动点定理的条件。在反应 对应具体凸性这一点上它们是相同的。当反应对应的凸性不再满足， 而只是满足一定的单调性（通常指单调增，有些情况下可以单调减） 时，支付函数也只是满足一定的单调性时，关于Nash均衡的存在性 结论也已经有所发展，这便是超模博弈理论。超模博弈理论为战略空 间只是满足一定的序结构，支付函数只是满足一定的单调性的博弈的 Nash均衡存在性提供了一定的保证，不仅如此，它还保证了这种博弈有纯战略的Nash均衡。在战略空间的一定序结构下，该类博弈的 Nash均衡的战略集的上下界存在且与可理性化战略集的上下界重 合。在思想

14、方法上由于反应对应的凸性假设不再必要，该类博弈的 Nash均衡的存在性的理论基础不再是Kakutani不动点定理，而是 Tarski不动点定理。关于该类博弈的具体内容有兴趣的读者请参阅 Topkis的相关著作。实际讲授第一部分回顾例子1猜币游戏一般地，用p*(q)表示在给定参与人2的战略a = (q,1 - q)的情况2下，参与人1的最优反应。由式(3-4)可得七(p,1 - p),(q,1 - q) = pvi (O,(q,1 - q) + (1 - p)V (R,(q,1 - q)=(2q -1) + p(2 - 4p)(3-10)在式(3-10)中，参与人1的期望收益在 2 - 4 p

15、0 时随p递增，在2 - 4p V 0时随p递减。因此当q -时，参与人1的最优反应p* （q） = 0 （即选择 2反面）（参见图3-7中p*（q）的两段水平虚线）。（反面）p、p*(q)（正面）1（反面）（正面）3-7参与人的最优反应前面已经提到，在q = 1时，参与人1选择纯战略正面（。）或反面 2（R）是无差异的。而且从式（3-10）可以看到，参与人1的期望收益在q = 1时与p无关，所有混合战略（p,1 - p）对参与人1都是无差异的。2也就是说，当q = 1时，对于0到1之间的任何p，混合战略（p,1-p）都2是对（q,1 - q） 的最优反应，即p * （2） ebjc参见图3-

16、7所示 p * （q） 中间的竖线段）。综上分析，可得参与人1最优反应p* （q）为p*(q) = ,11I 0,1q =21q 2(3-11)在式(3-11)中，当q = 1时，p * (!)可以为0,1中的任一值，从而使 22得p * (q)有不止一个值。因此，称p * (q)为参与人1的最优反应响应(best correspondence)，而不是最优反应函数1。对称地，可得参与人2的最优反应响应将参与人1与参与人2的最优反应响应置于同一张平面，最优反应响应曲线的交点，即是Nash均衡。1最优反应函数表示给定参与人2的一个战略，参与人1仅有一个最优战略与之相对成； 而最优反应响应则表示给

17、定参与人2的一个战略，参与人1不只有一个最优战略与之相对 应。参见第5章中关于Cournot模型的介绍。例子2 Cournot寡头博弈模型假设每个寡头企业具有相同的不变单位成本C ,即c(q尸c q 需求函数为线性形式P = a - (q1 +q2)，所以兀(q , q ) = q (a 一 q 一 q 一 c)i i j i i j此时，最优化的一阶条件为伽宜=a-(qi+q2)-qi -C = 0-2 = a - (q + q ) - q - C = 0四2企业的最优反应函数为q = R (q ) = 1(a - q - c)11222q2 = R2(qi) = 2(a - qi - c)

18、联立求解上式，可得企业的Nash均衡产量为(5-1)企业的Nash均衡利润分别为k k 1，、c(5-2)兀* =兀* = _ (a c )2在上述简单假设下，两个企业的最优反应函数均为直线，两条直线的交点即为Nash均衡，如图5-1所示。第二部分 实施Nash定理的证明已经知道，在考虑混合战略的情况下，一个完全信息静态博弈“通 常”都存在纳什均衡。这一认识最早由纳什（Nash，1950，1951）进 行了证明，称为纳什定理。定理2.1纳什定理 如果完全信息静态博弈G = &拾是有限的，即参 与人是有限的，S包含的纯策略也是有限的，那么一定存在至少个 （纯策略或混合策岫什均衡。所谓“通常”指的

19、就是博弈的有限性。到目前为止，我们分析的 博弈都满足这两个条件。参与人有限一一通常为两个人。S也是有限 的一一要么存在若干个纯策略，例如猜币游戏；要么虽然纯策略由无 穷多，但却是有界闭集2,例如古诺模型中的战略集Sj = 0,a，所以前 面分析的静态博弈都存在纳什均衡。对纳什定理的证明分三个部分来完成:第一步，介绍不动点定理；第二步，说明纳什均衡就是不动点；2在数学中，有界闭集必然意味着是有限的，即它不是无限的，或者说拒斥了无限情。第三步，完成证明。第一步，不动点定理。先来看图2-29。2-29从区间0,1区间0,1连续函数具有不动点图2-29中的方框为正方形。BD为45。线，它实际上等价于函

20、1仆丫 * x酷0叫D了不动点g (x)*CIBi0x *1x数y = ff。BD线上的每一点都满足ff，把满足f=尤的尤称为不动点。BD线所代表的函数自变量x取值为0,1，称为定义域，而因变量 y的取值为0,1,称为值域。定义域和值域都为0,1的函数f (x)，又可写作f : 0,1 0,1，读作从0,1到0,1的映射。现在做一个小游戏：拿一支笔，从AB线出发任意画一条曲线，记住可以任意画，但必须连续画不能断裂，至到CD线结束。这时发 现无论如何画，这条曲线一定会和BD相交，这个交点就是不动点 因为任意画的曲线等价于一个函数g，没有断裂意味着它是连续 的，与BD线相交意味着g* 3*)，所以

21、交点为不动点。所有任意画的曲线都有如下的性质：(1)定义域0,1是非空的、有界的、闭的、凸集合，简称非空凸紧集。 有界闭集即为紧集。(2)函数f (x)是连续的，并且是自身对自身的映射。上面考虑的只是一元函数，对于元函数是不是如果满足上述性 质就存在不动点？布劳尔(Brower)定理肯定地回答了这一点。定理2.2布劳尔(Brower)不动点定理。 假设auR是一个非空 凸紧集合，并且f : A t A是一个连续函数；那么f (.)必有一个不动点; 即，存在一个x e A使得x = f (x)这里R为实数，R为实数的n重笛卡尔积，x为n维向量。在前 面的例子中n = 1, A = 0,1。在实际

22、运用中，我们常常遇到的不是函数 而是对应的情况，例如猜币游戏这个博弈存在的是最优反应对应，而 不是函数，这就有了对布劳尔不动点定理的推广定理2.3角谷(Kakutani)不动点定理。假设auRn是非空凸紧 集，并且f : A-A是上半连续对应，并且对于每一个x e A，集合f(x)uA是非空凸集，那么f (.)必有一个不动点。即，存在一个x e A使得x e f (x) o角谷不动点定理与布劳尔不动点定理的区别在于:映射 f为对成而不是函数，所以f为一个集合(一个点也能组成 集合，所以函数是对成的特例)。映射f是上半连续的。一个对应只有既是上半连续又是下半连续才 能称为连续，因而上半连续比连续

23、的要求要弱。关于对应的上半连续，就是指如果存在一个序列x1, x2,.,收敛 于x并且 yi e f (xi), y2 e f (x2),., yn e f (xn) 收敛于y，那么一定有y e f (x) 仗口果f (x)只有唯一值，那么e就变为=),即对应包含着它的极限点在图2-30(a)中，当x 一 a ,即从a的左边向其收敛时，f(x)T A 但我们看到A ef (a)，即对应f (x)并不包含极限点A，所以它不是上 半连续的。在图2-30 (b)中，对应f (x)包含它的每一个序列的极限点，特 别是A e f (a)，因而它满足上半连续，但它不是连续的。例如，猜币 游戏中每个参与人的

24、最优反应对应就是上半连续的。对于函数而言，上半连续就等同于连续。3)上半连续(a)非上半连续2-30对成的上半连续第二步，纳什均衡是不动点。根据纳什均衡的定义，在给定其他参与人策略的情况下，参与人 i选择一个策略以使其收益最大化，并且对每一个参与人都如此，即 纳什均衡是一个使每一个参与人收益最大的策略组合。针对其他参与 人不同的策略，参与人i都有一个最优策略与之相对应，用数学来表 示就是最优反应函数或对应。如果参与人i的最优反应函数(对应) 定义为B (p，,p , p ,p ) =p ,其中i 1, ,n,那么个参与人的最优反 i 1i-1 i+1n i应函数(对应)就构成了一个方程，将其定

25、义为驰，,PJ，即B (P，P ) = P12n 1R ( p, Pn)=B (p ，p ，p ) = pii-1i+1n iBn (p, 1) = Pn如果(P*,P*)是纳什均衡，它一定满足R(P:，,P*)= (P:,P*)，即纳什均衡是一个不动点。例如，古 1n1n诺模型中的最优反应函数共同构成了一个方程组R (q , q ), i = 1,2，这个方程的解既是不动点，也是纳什均衡。第三步，完成证明。现在要完成的是证明：最优反应对应8,的定义域为耳度凸紧 集；B上半连续的对应。由于R是B (i = 1,2,n)的方程组，B,满足这两个条件，总的策略方程R必然满足这两个条件，而根据不动点

26、定理，我们知道存在着不 动点(P *，,P * ),使得 R ( P * ,P * ) = ( P * ,P * )1n ，1n1n (1)定义域为非空凸紧集。所谓有界集合就是任意画一个圆(圆的 半径可以任意大，但不能无穷大)可以把它包下。所谓闭集就是包含边界的集合。有界闭集即为紧致集合，简称紧集。所谓凸集就是在集 合内任意找两点，连接两点的直线一定位于集合中。图2-31中的直 线和三角平面显然是有界的，同时也是闭的，即它们是紧集。同时它 们也是凸集。如果博弈有个人参与人，参与人有k个纯策略，那么策略方程R的定义域为0,1kxn，它表示0,1的k X n重笛卡尔积，例如函数 f 3, y）,

27、x, y e A 那么函数的定义域就为A患，即x, y都从集合A中取值。由于混合策略的取值为0,1,显然0,1为非空凸紧集，所以0,1 Xn也 是非空凸紧集。在古诺模型中，它的定义域虽然与上面讲的有所不同， 即纯策略有无穷多个，但策略q （产量）的取值为0,a（或0,+皿），它 同样是非空凸集。这表明纳什均衡真正需要的并不是“有限的”要求， 而是策略空间必须为紧致集合。如果一个参与人有两个纯策略x和y 那么所有混合策略集合（策略空间）就是满足x + y = 1, x和y都大于等 于零的直线。如果有三个纯策略x, y, z，那么所有的混合策略集合（策 略空间）就是一个满足x + y + z =

28、1, x, y,z都大于等于零的一个三角平 面。如果2-31所示。（2）最优反应对应是上半连续的。根据前面的介绍，我们已经知道 混合策略空间是非空凸紧集，并且预期收益函数是混合策略的线性函 数，因而它是连续的和凹的（因为偏好为理性），这就保证了根据最 大化预期收益函数得到的最优反应对应必然是上半连续和非空凸集， 这在数学上被称为最大化定理。综上所述,最优反应方程R（% ,业）满足不动点定理的两个条件：策曜间为耳度凸紧集，最优反应对成为上半连续并*度凸集。因而存在着不动点，而不动点就是纳什均衡。知识扩展一、集值映射及其半连续性这里限于在欧氏空间中展开讨论，当然，我们也说成拓扑空间， 但在这里的上

29、下文，读者可以将拓扑空间直接理解为欧氏空间。设X是一个拓扑空间，X的所有子集的全体记作2X。即2 X = G: G u X 注意，0e 2 x , X e 2 x定义9.1.1设X和y是两个拓扑空间。若对任一尤e X，确定y的一个子集 (己作)F (X)与之对应。这样得到的对应F : X - 2y称作一个点对集 映射(point-to-set mapping)或一个 集 值映射(set-valued mapping)相应地，以往对每个x e X确定一个f (X) e y的映射f : X - Y 称为单值映射(single-valued mapping)如同单值映射的情形，我们引进集值映射的图像

30、的概念。定义9.1.2设F : X r 2y是一个集值映射。称X x Y的子集F (x) - (x, y) e X x Y : x e X, y e F (x)xeX为F的图像(graph)表现下面我们建立集值映射的半连续性和连续性的概念。定义9.1.3设F : X 2 y是一个集值映射，x 0 e X。若对Y的与F(x 0)之交 非空的每个开集g，存在X中包含工。的一个开集(x0)使得x eU(xo) 蕴涵F(x) G 0 ,就说F在x 0是下半连续的(lowersemicontinuous)若对Y的包含F (x 0 )的每个开集G，存在X中包含x0的一个开集U(x0)使得xeU(x0)蕴涵

31、F(x) u G ,就说F在x0是上半连续的 (upper semicontinuous)若F在x 0既是下半连续的又是上半连续的，就说F在x 0是连续的(continuous)集值映射的两种半连续性和连续性，都是单值映射的通常的连续性概念的推广。事实上，如果把单值映射看作在定义域的每点取值域 的一个单点集的集值映射，则作为集值映射的下半连续性、上半连续 性和连续性，都与作为单值I映射的通常的连续性吻合。对于集值映射，下半连续性和上半连续性是不同的。请看下面的 例子。例9.1.1设X = Y = I是实数轴上的一个闭区间，集值映射 F : X - 2y由图9.1给出。容易验证，在任一点X。xo

32、，连续性是不 成问题的。即在任一点xo，F既是下半连续的又是上半连续的。但在xo eX，F是下半连续的而不是上半连续的。例9.1.2仍取X = Y = I为闭区间，集值映射G: X - 2y由图9.2给出。容易验证，在任一点W X0,连续性是不成问题的，但在x = x0G是上半连续的却不是下半连续的。9.2其定义9.1.4若F : X - 2y在X的每个点都是下半连续的，就说F在X是下 半连续的。若F : X - 2丫在X的每个点都是上半连续的,就说F在X 是上半连续的。若F : X - 2y在X的每个点都是连续的,就说F在X 是连续的。为了下面讨论的方便，我们引入集值映射的逆象的概念。定义9

33、.1.5设F : X T 2 y是一个集映射，B是丫的一个子集。称F-1 (B) = x g X : F(x) H B，0为B的下逆象,或B的相交逆；称F-1 (B) = x g X : F(x) H B u B为B的上逆象,或B的包含逆基于上述定义，马上可以证明下面的定理。【定理9.1.1】F : X - 2y是下半连续的充要条件是开集的相交逆为开集, 即若仔是丫的开集，则F-1 (G)是乂的开集。f : X - 2y是上半连续 l的充要条件是开集的包含逆为开集，即若G是y的开集测F_1 (G) 是X的开集。利用这个定理，易知例9.1.1的F : X - 2y是下半连续的，因 为开集的相交逆

34、都是开集，但F不是上半连续的，因为开集的包含 逆不都是开集。同样,对于例9.1.2的G : X - 2y，因为开集的包含 逆都是开集，所以g是上半连续的，但开集的相交逆不都是开集， 所以不是下半连续的。下面是一个更为方便的上半连续性判别法。为行文方便，欧氏空 间的子空间也称为欧氏空间。注意在欧氏空间中，子集作为子空间的 紧致性与有界闭性等价。【定理9.1.2】设X和Y是欧氏空间，并且Y紧致，集值映射F : X - 2 y使得对每个x e X , F (x)是Y的紧致子集。那么”:X - 2y为上半连续的充要条件是：F的图像表 F (x) = (x, y) e X x Y : x e X, y

35、e F (x)xeX是X X Y中的一个闭子集。根据这个定理，仅仅因为例9.1.1中的映射的图像表现的闭性在x = x0处遭到破坏，我们马上知道F不是上半连续的。但例9.1.2中 的集值映射G的图像表现是X x Y = I x I中的闭集，即知G是上半连续的。二、Kakutani不动点定理我们主要关心有强烈应用背景的欧氏空间凸子集到其非空紧致 凸子集族的集值映射。设X为欧氏空间的凸集，我们约定，记X的非空紧致凸子集族为 P(X)。当然，P(X) e 2X定义1设X是欧氏空间的凸集, F : X - P(X)是集值|映射。如果x e X使得x e F (x)，就说工e X是集值映射F : X -

36、 P (X )的一个不动点为区别起见，常常把由x = f (x)定义的不动点称为Brouwer不动 点，而把由x e F(x)定义的不动点称为Kakutani不动点。后者是前者在集值映射情形的推广。Brouwer不动点定理说，闭胞腔的连续自映射必有不动点。而Kakutani不动点定理说，紧凸集的上半连续的集值自映射必 有不动点。三、Nash 定理的一般证明(重点，讲!)我们首先在博弈的一般表示G = S ,S ;u ,u 之下)将1n 1nNash均衡的概念加以推广，使之包含混合策略的情形。设G = S，,S ；U ,U 为一个有n个参与人的博1n 1n弈，S = s ,s ，每个s e S为

37、第i个参与人的一个纯策略。Sii 1iKiik ii上的一个概率分布P =(匕,P为第i个参与人的一个混合策略 i这里,0 p v (p , p *)i i -ii i -i下面我们就证明Nash定理【定理1】设博弈G = S ,S ;u ,u ，这里n为有限正整数，每个S为 1n 1nI有限集,则博弈g至少存在一个Nash均衡注意，这个均衡既可能是纯策略均衡，也可能是混合策略均衡。证明(0)对于任意的S = s 1,七,记其概率空间为A = Ak, i = p G Rk : p ,，p 0, P HF p = 1iii 1iKi 1iKii每个p G A,为第i个参与人的一个混合策略。显然A

38、,是一个前面讲过 的K -1维标准单纯形。 i对以下单纯形的笛卡尔积，如前引进简便记法：A = A x x AA = A x x A x A x x A i1i 1i+1n记第i个参与人的最佳反应对应为：f : a, t PH.),这里PH.) 表示a,的所有非空紧致凸子集的集合。对任意?gA)显然是 a,的非空闭子集，所以是a,的非空紧致子集。因为期望支付是纯策 略支付函数的线性组合(事实上还是凸组合)，所以f (p )是A的凸 i -ii子集。可见，对任意p,gA, f (p)是A,的非空紧致凸子集。这时， p Gf (p )表示除第i个参与人之外的其余n 1个参与人采用策略p i i i

39、i时,第i个参与人的一个最佳混合策略。定义总的最优反应对应映射为F : 2a, F(p)=(f (p ),.,f (p ) 1 -1n -n这里2 A表示A的所有子集的集合。如果F : Ar 2 a有Kakutani不动点p * e F (p *),即有P* e f (p* ),p* e f (p* )，则p怜显然就是该博弈的一个 Nash均 11 -1n n - n衡。(3)利用Kakutani不动点定理证明F : A - 2a确实存在Kakutani不动点 p * e F (p *)我们来验证F : Ar 2 a确实满足Kakutani不动点定理的条件即:A为非空紧致凸集，对任一 p eA

40、, F (p)为A的非空紧致凸子集，并且F为上半连续的集值映射。首先由于A都是K -1维标准单纯形，因而是非空紧致凸的，这 ii样A = A1 x .xA很显然就是非空紧致凸集。对于任意p eA，因为各A是非空紧致集,所以各f (p )非空紧 ii -i致，所以F(p) = (f (p1 ), f (p n)也是非空紧致集。如果 p, p e F(p)，那么对每个 i, v (p,p ) = v (p p) = max i i -ii i -i已经达到最大。设Xpf + (1 - X)p是p和p ”的任意凸组合，那么V.如 + (1 -人)p) = kv (pf, p ) + (1 -人)v

41、(p, p)= max 也达到这个最大，可见 Xp+ Q-X)p e F (p)。由此可见，F ( p)是凸集。这样F : 2a可以写作F : P(),这里P()同样表示a 的所有非空紧致凸子集的集合。剩下只须验证F : At P ()的上半连续性，而这只须验证F : At P (A)的图像(p, q) wAxA : p g , q g F (p)是闭集即可。 设 Pm T p0, qm G F(pm )且 qm T q0，我们来证明 q0 G F(p0 )。由于qm G F (pm )，也就是 qm G f i (p m ) , i = l,2,n 即对所有 p gA , i = 1,2,n，有 V (qm,pm) v (p , pm).由于 v 是线性因而i ii i -ii i -ii是连续的，当m Ts时，上述不等关系保持不变，即有对所有 p gA, i = 1,2, , n,v (q0,p 0) v (p , p0)i i -ii i -i也即q0 g f (p 0), i = 1,2,n这就说明q 0 g F (p 0)证毕