《[所有分类]《博弈论：原理、模型与教程》第04章 Nash均衡解的特性 第02节 Nash均衡的存在性.doc》由会员分享，可在线阅读，更多相关《[所有分类]《博弈论：原理、模型与教程》第04章 Nash均衡解的特性 第02节 Nash均衡的存在性.doc（34页珍藏版）》请在三一文库上搜索。
1、博弈论：原理、模型与教程 第一部分 完全信息静态博弈第4章 Nash均衡解的特性4.2 Nash均衡解的存在性（已精细订正！）=本节推荐参考文献：（01）张石生.不动点理论及应用（M）. 重庆：重庆出版社，1984年8月第1版.（注：有趣的是，该书的责任编辑尹明善，就是后来从摩配起步创业成功的力帆老总）（02）张奠宙，顾鹤荣.不动点定理（M）. 沈阳：辽宁教育出版社，1989年4月第1版.（03）王则轲，左再思，李志强.经济学拓扑方法（M）. 北京：北京大学出版社，2002年1月第1版.=将Nash均衡作为博弈的解，会面临这样的问题：Nash均衡是否存在，或者说对于所关心的博弈问题，是否一定存
2、在一个Nash均衡？非常庆幸的是，我们能够得到一个肯定的答案。下面将对本书所涉及的博弈论中一些经典的存在性结论进行介绍。定理4-1（Nash均衡的存在性定理1，1950） 每一个有限的战略式博弈至少存在一个Nash均衡（包括纯战略和混合战略Nash均衡）。定理4-1是博弈论中关于Nash均衡存在性的最基本定理。1950年，John Nash在文章Equilibrium points in n-person games 中首次提出Nash均衡的概念，并给出该存在性定理。无论怎样强调该定理对于博弈论以后的发展的意义都不过分，因为Nash均衡之后的博弈论的发展（尤其是非合作博弈论的发展）基本上都是以
3、该定理为基石的。定理4-1的条件简单，但得出的结论却十分肯定。下面给出的定理的详细证明。供有兴趣的读者参考。为证明该定理，先给出如下必要的基本概念。定义4-1 从集合到集合的一个规则，若满足：,都中的一个集合与之对应，则称为由到的对应，记为：。简单地说，对应是函数概念的扩展，函数将集合中的点映到中的点，而对应将集合中的点映到中的子集。对应：的图像是指中的集合。对应：为上半连续的，是指和中任意包含的开集，在中都存在的一个邻域，只要，就有。显然对应的上半连续性为函数连续性概念的扩展，对应一个函数它的上半连续性就等于它的连续性。对应：的图像为闭图，是指任意给定若就有。闭图将闭集的概念推广到集合的直积
4、中。若对应的值域为紧集，则有闭图就意味着为上半连续的。有了这些基本概念，下面证明基本定理4-1.证明的基本思想是将Kakutani不动点定理应用于参与人的反应对应上。参与人的反应对应 为对手选择时，将每一个战略组合映射到的一个混合战略集。给定对手选择，给混合战略集中的每个战略最大化参与人的支付。这里虽然只依赖于，而不依赖于，仍将 写作的对应，因为稍后会在战略组合空间之中寻找一个不动点。定义反应对应为的Cartesian直积，即，则的不动点为满足 的战略组合，因此对每个参与人，所以的不动点即为一个Nash均衡。因此，对定理4-1的证明转化为证明参与人的反应对应具有不动点。由Kakutani不动点
5、定理，,存在不动点的充分条件为：为有限维欧氏空间的紧的凸子集；非空；为凸；有闭图。在这里，若成立，即为紧集，且成立，则对应为上半连续的。下面分别证明这些条件满足：首先，因为为维数为的单纯形，所以满足。其次，因为每一个参与人的支付函数在自己的混合战略上是线性的，因此也是连续的。连续函数在紧集上取得最大值，所以非空，满足。再次，为了证明 ，采用反证法。若非凸，则存在及 ，且存在，使得，但对每一个，有 因此若，是相对于的最优反应，那么它们的加权平均也是。而这与非凸矛盾，所以凸。最后，仍用反证法证明 。假设不满足，则存在序列但，所以存在,。因此存在和，使得。又因为为连续的且，因此对足够大的,有 所以对
6、于 严格优于，这与矛盾。所以 满足。至此，也就完成了有限博弈中Nash均衡的存在性的证明。在经济学和现实生活中也有很多无限博弈，即参与人的战略有无限多个或参与人的战略能在一个集合中连续取值，如厂商之间的价格或产量竞争。对应于这些情况有如下的存在性定理。定理4-2（Nash均衡的存在性定理2，Debru 1952,Glicksberg 1952,Fan 1952） 对于战略式博弈,若为欧氏空间的非空紧凸子集，支付函数关于战略组合连续，关于拟凹，则该博弈存在纯战略的Nash均衡。该定理的证明与Nash均衡的存在性定理4-1类似，支付函数关于所有参与人战略组合的连续性意味着反应对应具有闭图。另外，支
7、付函数关于自己战略的拟凹性意味着反应对应为凸值的。同样运用Kakutani不动点定理便可以证明该定理。注意：在上述定理中关于参与人战略组合的连续性条件是非常重要的，它类似于有限博弈中期望支付关于混合战略是连续的，因此Nash均衡的存在性定理4-1可以看作是该定理的特例。但同时在参与人的支付函数上该定理的条件较Nash均衡的存在性条件强，但正是因为较强的条件从而导致了较强的结果纯战略Nash均衡的存在性！在很多博弈中不存在纯战略的Nash均衡，但却存在混合战略 Nash均衡，因此将上述条件放松便得到相关条件下关于混合战略的存在性结论。定理4-3(Nash均衡的存在性定理3，Glicksberg
8、1952) 对于战略式博弈，若战略空间为距离空间中的非空紧子集，支付函数关于战略组合连续，则该博弈存在混合战略的Nash均衡（将纯战略Nash均衡作为混合战略Nash均衡的特例）。在上述关于Nash均衡的存在性定理4-2和定理4-3中，都要求参与人的支付关于所有参与人战略组合的连续性，在经济学的一些理论或应用中，非连续性或非拟凹的收益函数是很常见的。如果有不连续的收益，则一个紧的战略空间就不再确保参与人对应其对手战略的最优反应一定存在。为了探寻此时均衡的存在性，Dasgupta进一步对以上存在性条件进行放松，得到如下存在性定理。定理4-4（Nash均衡的存在性定理4，Dasgupta和Mask
9、in 1986） 对于战略式博弈 ，若对于所有的，为有限维欧氏空间的非空紧凸子集；关于拟凹，关于上半连续且 关于连续，则该博弈存在一个纯战略的Nash均衡。该定理的证明仍然与前述定理的证明类似，仍然采用Kakutani不动点定理，其中收益函数关于自己战略的拟凹性保证了反应对应的凸值性，的极大值关于的连续性及的上半连续性保证了反应对应具有闭图，因此证明过程类似定理4-1，这里不再重复。在上述定理的基础上，Dasgupta继续对的连续性及拟凹性进行放松，得到了当支付函数只在战略集的某个子集上不连续时，相关条件下混合战略均衡的存在性。其思想是用有限分割去近似战略空间，证明的方法仍然是用Kakutan
10、i不动点定理。由于涉及一些较复杂的数学名词的解释，这里不再介绍，建议有兴趣的读者参阅相关文献。至此为止，所列出的关于Nash均衡的存在性结论其证明思想都是Kakutani不动点定理。从数学上看，以上一系列的存在性定理都是在不断放松Kakutani不动点定理成立的条件，而且都在试图不断放松对支付函数的要求以满足Kakutani不动点定理的条件。在反应对应具体凸性这一点上它们是相同的。当反应对应的凸性不再满足，而只是满足一定的单调性（通常指单调增，有些情况下可以单调减）时，支付函数也只是满足一定的单调性时，关于Nash均衡的存在性结论也已经有所发展，这便是超模博弈理论。超模博弈理论为战略空间只是满
11、足一定的序结构，支付函数只是满足一定的单调性的博弈的Nash均衡存在性提供了一定的保证，不仅如此，它还保证了这种博弈有纯战略的Nash均衡。在战略空间的一定序结构下，该类博弈的Nash均衡的战略集的上下界存在且与可理性化战略集的上下界重合。在思想方法上由于反应对应的凸性假设不再必要，该类博弈的Nash均衡的存在性的理论基础不再是Kakutani不动点定理，而是Tarski不动点定理。关于该类博弈的具体内容有兴趣的读者请参阅Topkis的相关著作。实际讲授=第一部分 回顾例子1 猜币游戏一般地，用表示在给定参与人2的战略的情况下，参与人1的最优反应。由式（3-4）可得= = （3-10）在式（3
12、-10）中，参与人1的期望收益在时随递增，在时随递减。因此当时，参与人1的最优反应（即选择正面）；当时，参与人1的最优反应（即选择反面）（参见图3-7中的两段水平虚线）。 1 （反面） （正面）（正面）1（反面）图3-7 参与人的最优反应前面已经提到，在时，参与人1选择纯战略正面或反面是无差异的。而且从式（3-10）可以看到，参与人1的期望收益在时与无关，所有混合战略对参与人1都是无差异的。也就是说，当时，对于到之间的任何，混合战略都是对的最优反应，即（参见图3-7所示中间的竖线段）。综上分析，可得参与人1最优反应为 （3-11）在式（3-11）中，当时，可以为 中的任一值，从而使得有不止一个
13、值。因此，称为参与人1的最优反应响应（best correspondence），而不是最优反应函数 最优反应函数表示给定参与人2的一个战略，参与人1仅有一个最优战略与之相对应；而最优反应响应则表示给定参与人2的一个战略，参与人1不只有一个最优战略与之相对应。参见第5章中关于Cournot模型的介绍。对称地，可得参与人2的最优反应响应。将参与人1与参与人2的最优反应响应置于同一张平面，最优反应响应曲线的交点，即是Nash均衡。（反面）11/21O（正面）（反面）正面图 参与人1的最优反应对应 1/21正面1/2背面 01正面图 参与人2的最优反应对应1/2纳什均衡点（不动点）1正面1/2背面 0
14、1正面图 纳什均衡点例子2 Cournot寡头博弈模型假设每个寡头企业具有相同的不变单位成本，即 ，需求函数为线性形式，所以此时，最优化的一阶条件为企业的最优反应函数为联立求解上式，可得企业的Nash均衡产量为 （5-1）企业的Nash均衡利润分别为 （5-2） 在上述简单假设下，两个企业的最优反应函数均为直线，两条直线的交点即为Nash均衡，如图5-1所示。（不动点）图5-1 Cournot 模型的Nash均衡第二部分 实施Nash定理的证明已经知道，在考虑混合战略的情况下，一个完全信息静态博弈“通常”都存在纳什均衡。这一认识最早由纳什（Nash，1950，1951）进行了证明，称为纳什定理
15、。定理2.1 纳什定理 如果完全信息静态博弈是有限的，即参与人是有限的，包含的纯策略也是有限的，那么一定存在至少一个(纯策略或混合策略)纳什均衡。所谓“通常”指的就是博弈的有限性。到目前为止，我们分析的博弈都满足这两个条件。参与人有限通常为两个人。也是有限的要么存在若干个纯策略，例如猜币游戏；要么虽然纯策略由无穷多，但却是有界闭集 在数学中，有界闭集必然意味着是有限的，即它不是无限的，或者说拒斥了无限情。，例如古诺模型中的战略集，所以前面分析的静态博弈都存在纳什均衡。对纳什定理的证明分三个部分来完成：第一步，介绍不动点定理；第二步，说明纳什均衡就是不动点；第三步，完成证明。第一步，不动点定理。
16、先来看图2-29。001ADC1B不动点图2-29 从区间0,1区间0,1连续函数具有不动点图2-29中的方框为正方形。为45线，它实际上等价于函数。线上的每一点都满足，把满足的称为不动点。线所代表的函数自变量取值为，称为定义域，而因变量的取值为,称为值域。定义域和值域都为的函数，又可写作，读作从到的映射。现在做一个小游戏：拿一支笔，从线出发任意画一条曲线，记住可以任意画，但必须连续画不能断裂，至到线结束。这时发现无论如何画，这条曲线一定会和相交，这个交点就是不动点。因为任意画的曲线等价于一个函数，没有断裂意味着它是连续的，与线相交意味着，所以交点为不动点。所有任意画的曲线都有如下的性质：（1
17、）定义域是非空的、有界的、闭的、凸集合，简称非空凸紧集。有界闭集即为紧集。(2)函数是连续的，并且是自身对自身的映射。上面考虑的只是一元函数，对于元函数是不是如果满足上述性质就存在不动点？布劳尔（Brower）定理肯定地回答了这一点。定理2.2布劳尔（Brower）不动点定理。 假设是一个非空凸紧集合，并且是一个连续函数；那么必有一个不动点；即，存在一个使得。这里为实数，为实数的重笛卡尔积，为维向量。在前面的例子中。在实际运用中，我们常常遇到的不是函数而是对应的情况，例如猜币游戏这个博弈存在的是最优反应对应，而不是函数，这就有了对布劳尔不动点定理的推广。定理2.3角谷(Kakutani)不动点
18、定理。 假设是非空凸紧集，并且是上半连续对应，并且对于每一个，集合是非空凸集，那么必有一个不动点。即，存在一个使得。角谷不动点定理与布劳尔不动点定理的区别在于：映射为对应而不是函数，所以为一个集合(一个点也能组成集合，所以函数是对应的特例)。映射是上半连续的。一个对应只有既是上半连续又是下半连续才能称为连续，因而上半连续比连续的要求要弱。关于对应的上半连续，就是指如果存在一个序列收敛于并且收敛于，那么一定有（如果只有唯一值，那么就变为），即对应包含着它的极限点。在图2-30(a)中，当，即从的左边向其收敛时，但我们看到，即对应并不包含极限点，所以它不是上半连续的。在图2-30（b）中，对应包含
19、它的每一个序列的极限点，特别是，因而它满足上半连续，但它不是连续的。例如，猜币游戏中每个参与人的最优反应对应就是上半连续的。对于函数而言，上半连续就等同于连续。（a）非上半连续 （b）上半连续图2-30 对应的上半连续第二步，纳什均衡是不动点。根据纳什均衡的定义，在给定其他参与人策略的情况下，参与人选择一个策略以使其收益最大化，并且对每一个参与人都如此，即纳什均衡是一个使每一个参与人收益最大的策略组合。针对其他参与人不同的策略，参与人都有一个最优策略与之相对应，用数学来表示就是最优反应函数或对应。如果参与人的最优反应函数（对应）定义为那么个参与人的最优反应函数（对应）就构成了一个方程，将其定义
20、为，即如果是纳什均衡，它一定满足，即纳什均衡是一个不动点。例如，古诺模型中的最优反应函数共同构成了一个方程组，这个方程的解既是不动点，也是纳什均衡。第三步，完成证明。现在要完成的是证明：最优反应对应的定义域为非空凸紧集；为上半连续的对应。由于是的方程组，满足这两个条件，总的策略方程必然满足这两个条件，而根据不动点定理，我们知道存在着不动点，使得。（1）定义域为非空凸紧集。所谓有界集合就是任意画一个圆（圆的半径可以任意大，但不能无穷大）可以把它包下。所谓闭集就是包含边界的集合。有界闭集即为紧致集合，简称紧集。所谓凸集就是在集合内任意找两点，连接两点的直线一定位于集合中。图2-31中的直线和三角平
21、面显然是有界的，同时也是闭的，即它们是紧集。同时它们也是凸集。而图2-32中的环是非空紧集，但却不是凸集。11BABA0图2-31 非空凸紧集图2-32 圆为凸集，环为非凸集如果博弈有个人参与人，参与人有个纯策略，那么策略方程的定义域为，它表示的重笛卡尔积，例如函数，那么函数的定义域就为，即都从集合中取值。由于混合策略的取值为，显然为非空凸紧集，所以也是非空凸紧集。在古诺模型中，它的定义域虽然与上面讲的有所不同，即纯策略有无穷多个，但策略（产量）的取值为，它同样是非空凸集。这表明纳什均衡真正需要的并不是“有限的”要求，而是策略空间必须为紧致集合。如果一个参与人有两个纯策略，那么所有混合策略集合
22、（策略空间）就是满足都大于等于零的直线。如果有三个纯策略，那么所有的混合策略集合（策略空间）就是一个满足都大于等于零的一个三角平面。如果2-31所示。（2）最优反应对应是上半连续的。根据前面的介绍，我们已经知道混合策略空间是非空凸紧集，并且预期收益函数是混合策略的线性函数，因而它是连续的和凹的（因为偏好为理性），这就保证了根据最大化预期收益函数得到的最优反应对应必然是上半连续和非空凸集，这在数学上被称为最大化定理。综上所述，最优反应方程满足不动点定理的两个条件：策略空间为非空凸紧集，最优反应对应为上半连续并且是非空凸集。因而存在着不动点，而不动点就是纳什均衡。=知识扩展一、集值映射及其半连续性
23、这里限于在欧氏空间中展开讨论，当然，我们也说成拓扑空间，但在这里的上下文，读者可以将拓扑空间直接理解为欧氏空间。设是一个拓扑空间，的所有子集的全体记作。即.注意, ,。定义9.1.1设和是两个拓扑空间。若对任一,确定的一个子集(己作)与之对应。这样得到的对应称作一个点对集映射(point-to-set mapping)或一个集值映射(set-valued mapping)。相应地，以往对每个确定一个的映射,称为单值映射(single-valued mapping)。如同单值映射的情形，我们引进集值映射的图像的概念。定义9.1.2设是一个集值映射。称的子集为的图像(graph)表现。下面我们建立
24、集值映射的半连续性和连续性的概念。定义9.1.3设是一个集值映射，。若对的与之交非空的每个开集，存在中包含的一个开集使得蕴涵,就说在是下半连续的(lower semicontinuous)。若对的包含的每个开集，存在中包含的一个开集使得蕴涵，就说在是上半连续的(upper semicontinuous)。若在既是下半连续的又是上半连续的,就说在是连续的(continuous)。集值映射的两种半连续性和连续性,都是单值映射的通常的连续性概念的推广。事实上，如果把单值映射看作在定义域的每点取值域的一个单点集的集值映射，则作为集值映射的下半连续性、上半连续性和连续性，都与作为单值映射的通常的连续性吻
25、合。图9.1对于集值映射，下半连续性和上半连续性是不同的。请看下面的例子。例9.1.1 设是实数轴上的一个闭区间，集值映射由图9.1给出。容易验证，在任一点，连续性是不成问题的。即在任一点，既是下半连续的又是上半连续的。但在，是下半连续的而不是上半连续的。例9.1.2 仍取为闭区间，集值映射由图9.2给出。容易验证，在任一点，连续性是不成问题的，但在，是上半连续的却不是下半连续的。图9.2定义9.1.4若在的每个点都是下半连续的，就说在是下半连续的。若在的每个点都是上半连续的，就说在是上半连续的。若在的每个点都是连续的，就说在是连续的。为了下面讨论的方便，我们引入集值映射的逆象的概念。定义9.
26、1.5设是一个集值映射，是的一个子集。称为的下逆象,或的相交逆；称为的上逆象,或的包含逆。基于上述定义，马上可以证明下面的定理。【定理9.1.1】是下半连续的充要条件是“开集的相交逆为开集”，即若是的开集，则是的开集。是上半连续的充要条件是“开集的包含逆为开集”，即若是的开集，则是的开集。利用这个定理，易知例9.1.1的是下半连续的，因为开集的相交逆都是开集，但不是上半连续的，因为开集的包含逆不都是开集。同样,对于例9.1.2的，因为开集的包含逆都是开集，所以是上半连续的，但开集的相交逆不都是开集，所以不是下半连续的。下面是一个更为方便的上半连续性判别法。为行文方便，欧氏空间的子空间也称为欧氏
27、空间。注意在欧氏空间中，子集作为子空间的紧致性与有界闭性等价。【定理9.1.2】设和是欧氏空间，并且紧致，集值映射使得对每个，是的紧致子集。那么，为上半连续的充要条件是:的图像表现是中的一个闭子集。根据这个定理，仅仅因为例9.1.1中的映射的图像表现的闭性在处遭到破坏，我们马上知道不是上半连续的。但例9.1.2中的集值映射的图像表现是中的闭集，即知是上半连续的。二、Kakutani不动点定理我们主要关心有强烈应用背景的欧氏空间凸子集到其非空紧致凸子集族的集值映射。设为欧氏空间的凸集，我们约定，记的非空紧致凸子集族为。当然，。定义1设是欧氏空间的凸集，是集值映射。如果使得，就说是集值映射的一个不
28、动点。为区别起见,常常把由定义的不动点称为Brouwer不动点，而把由定义的不动点称为Kakutani不动点。后者是前者在集值映射情形的推广。Brouwer不动点定理说，闭胞腔的连续自映射必有不动点。而Kakutani不动点定理说，紧凸集的上半连续的集值自映射必有不动点。三、Nash定理的一般证明（重点，讲！）我们首先在博弈的一般表示之下将Nash均衡的概念加以推广,使之包含混合策略的情形。 设为一个有个参与人的博弈, ,每个为第个参与人的一个纯策略。上的一个概率分布为第个参与人的一个混合策略,这里, , ,并且。这时,为这个博弈的参与人分别采用混合策略时，第个参与人所得到的期望支付。为符号方
29、便,我们如前记定义1设博弈,，第个参与人的混合策略为,为第个参与人的期望支付。个参与人的一组混合策略称为博弈的一个Nash均衡，如果对任意的参与人及参与人的任意混合策略,有下面我们就证明Nash定理。【定理1】设博弈,这里为有限正整数，每个为有限集,则博弈至少存在一个Nash均衡。注意,这个均衡既可能是纯策略均衡,也可能是混合策略均衡。 证明(0)对于任意的,记其概率空间为每个为第个参与人的一个混合策略。显然是一个前面讲过的维标准单纯形。对以下单纯形的笛卡尔积，如前引进简便记法: (1)记第个参与人的最佳反应对应为:,这里表示的所有非空紧致凸子集的集合。对任意显然是的非空闭子集，所以是的非空紧
30、致子集。因为期望支付是纯策略支付函数的线性组合(事实上还是凸组合),所以是的凸子集。可见,对任意是的非空紧致凸子集。这时, 表示除第个参与人之外的其余个参与人采用策略时,第个参与人的一个最佳混合策略。 定义总的最优反应对应映射为，,这里表示的所有子集的集合。(2)如果有Kakutani不动点,即有,则怜显然就是该博弈的一个Nash均衡。(3)利用Kakutani不动点定理证明确实存在Kakutani不动点。我们来验证确实满足Kakutani不动点定理的条件即: 为非空紧致凸集,对任一,为的非空紧致凸子集,并且为上半连续的集值映射。首先由于都是维标准单纯形，因而是非空紧致凸的,这样很显然就是非空紧致凸集。对于任意,因为各是非空紧致集,所以各非空紧致,所以也是非空紧致集。如果,那么对每个，已经达到最大。设是和的任意凸组合,那么也达到这个最大,可见。由此可见, 是凸集。这样可以写作,这里同样表示的所有非空紧致凸子集的集合。 剩下只须验证的上半连续性，而这只须验证的图像是闭集即可。设,且,我们来证明。由于，也就是,即对所有,有.由于是线性因而是连续的,当时,上述不等关系保持不变,即有对所有,，也即,这就说明证毕。=34