(高等教育)《博弈论与经济模型》讲义第四章__纳什均衡的存在性与多重性

第四章 纳什均衡的存在性与多重性对于数学家来说，一个数学概念的存在性与唯一性是特别需要加以关注的。这是因为，从形式逻辑角度看，如果某个事物并不存在，那么关于这个杜撰中的事物所给出的任何陈述或判断都可认为是正确的或错误的，因为对于不存在的事物来说，任何关于它的陈述或判断都不可能加以证伪。所以，倘若某个概念所对应的事物并不存在。那么，关于这个概念所给出的研究结论都必然不存在被证伪的可能。因而根据波普尔的证伪主义观点，这样的研究不具备科学上的意义。所以，我们在对任何新提出来的数学概念加以系统研究之前，首先需要弄清楚所研究的对象事物是否存在。有许多被称为伪科学的东西，它们之所以被人们认为是“伪科学”的原因就是它们大肆谈论的东西并不存在或并未被证实其存在性。譬如，所谓的特异功能或“超灵学”并未得到证实，而UFO研究迷们至今也未能拿出一件存在球外生命的证据，所以，特异功能学或“超灵学”或“不明飞行物学”实际上都可被归入伪科学。除了存在性之外，概念事物的唯一性也是数学家们所关心的问题。从纯理论的兴趣上看，数学家们更多地是从审美的角度上看待概念的唯一性，但从波普尔的证伪主义哲学看，模型均衡解的唯一性关系到模型的预测功能，从而是科学理论应基本具有的特征。我们在第二章中曾指出，理论的预测功能是判别理论的科学性的准绳，而在第三章中，我们提出用纳什均衡作为模型的预测结果。按照这样的逻辑，一个自然的推论就是：模型能否具有科学意义取决于纳什均衡的唯一性。因为倘若纳什均衡不是唯一的，那么就难以根据模型对即将出现的结果加以预测，这种不确定性对于科学理论来说是不存在的。再加上前面谈到的存在性问题，我们可以这样说，模型能否具有科学意义取决于纳什均衡的存在性和唯一性，因为这正是科学理论所具有的基本性质。博弈论目前发展的情况是这样的：已经证明在非常一般的情况下，纳什均衡是存在的，这是一个好的结果；但是，在许多情形，模型的纳什均衡解不是唯一的，这被称为纳什均衡的多重性问题。纳什在1950年代证明了纳什均衡的存在性定理，为非合作博弈打下了重要基础。纳什的工作不仅解决了存在性问题，而且还为其后的博弈论研究提供了一整套方法论工具，即运用不动点定理(fixed point theorem)这一强有力的数学工具进行博弈论数学分析，这对后来的博弈论甚至数理经济学的发展产生了很大的影响。纳什均衡的多重性问题至今仍是困扰博弈论学者的一个主要问题。为了攻克这一问题，博弈论专家已经做出了许多贡献，如聚点均衡、相关均衡，子博弈精炼纳什均衡，颤抖手均衡，序贯均衡等概念的提出。但不幸的是，这类努力还未使得多重均衡问题完全得到解决，许多博弈论专家正在这一领域进行着不懈的工作。本章将给出纳什均衡的存在性定理和讨论存在多重均衡情况下的均衡选择问题。4.1 纳什均衡的存在性定理自从纳什(1950)首先给出存在性定理及其证明之后，许多学者又相继提出了不同表述下的存在性定理和不同的证明方法。这里，我们介绍Myerson(1991)给出的存在性定理和证明。4.1.1 纳什均衡与不动点定理所有的存在性定理证明都采用了不动点定理，这是因为，纳什均衡的概念在数学上就是一个不动点的概念。在给出存在性定理及其证明之前，我们先来说明不动点的概念和给出不动点定理。什么是“不动点”呢？考虑一个方程，其中为方程的解。我们将视为一种“变换”，即是将对应为的变换，其中和分别是属于集合和的两个元素，。如果，则方程的几何意义就是：变换将变为自己，即在变换下是不变的，故称的解为变换的不动点。一般地，我们可以将所有的方程都写为如下形式： (4.1)在式(4.1)两端加上一个，则变为。令则有所以，一般地，方程求解的问题本质上是寻找变换的不动点问题。对于这样一种非常一般地的问题，数学家们感到十分高兴的是居然在不太严格的条件下式(4.1)存在解，即不动点是较为广泛地存在的。45of(x)x*10x* 1譬如，图4.1表明不动点是曲线与45o线的交点。当函数定义在区间上且因变量的值域也为区间时，如果是连续的，则必然存在不动点。图4.1 0,1区间上的自变换函数的不动点那么，这种现象到底具有多大的一般性意义呢？数学家Brouwer在很久以前就注意到这一现象，他得出了如下的一般性定理，即著名的Brouwer不动点定理。定理4.1(Brouwer)设是定义在集合X上的实函数，且，。如果是连续的，为一非空的有界凸闭集，则至少存在一个使。即至少存在一个不动点1。有意思的是，Brouwer不动点定理存在很强的几何直观2，但其数学证明却十分艰深，需要动用代数拓扑这类就是职业数学家也感到望而生畏的超级抽象数学工具3。在此，我们不给出Brouwer不动点定理的证明。直接用来证明纳什存在性定理的不动点定理还不是Brouwer不动点定理，而是角谷静夫(Kakutani)不动点定理，而后者的证明只是前者的一个相对简单的运用。我们所以要引用角谷静夫不动点定理，是因为在纳什均衡存在性证明中所遇到的反应函数一般是多个因变量函数，即所谓对应(correspondence)，而角谷静夫不动点定理正好描述的是对应的一种性质。角谷静夫不动点定理是Brouwer不动点定理的推广，但其自身的证明要用到Brouwer不动点定理。我们在这里不打算给出这两个不动点定理的证明，因为这类证明只是一种纯数学过程，但我们将给出纳什存在性定理的一种证明，因为了解存在性定理的证明过程有助于我们更好地理解纳什均衡。为了解读角谷静夫不动点定理，我们先来准备一下一些有关的数学概念。对于任一有限集M，我们用RM表示形如的所有向量组成的集合，其中对M中每一个m，第m个分量是实数域R的一个元素。为方便计，我们也可将RM等价地理解为M到R上的所有函数组成的集合，这时RM中的分量也可被记为。令S是RM中的一个子集，我们有如下定义：定义4.1 S是凸的(Convex)当且仅当对任意的及满足的，只要和，则有这里，定义4.2，S是闭的(Closed)当且仅当对每个收敛的序列，如果对每个都有，则有定义4.3，RM中的子集S是开的(open)当且仅当它的补集RM/S是闭的。定义4.4，S是有界的(bounded)当且仅当存在某个正数K使得对S中的每个元素都有定义4.5，一个点到集合的“对应”(correspondence)是任何一个规定了对X中的每个点，是与相对应的Y中的一个子集。如果X和Y都是度量空间，则X和Y上的收敛和极限概念已经定义，这时有：定义4.6 ，一个对应G:XY是上半连续的(upperhemicontinuous)，当且仅当对每个序列，如果对于每个有和，而且序列收敛于某个点，又序列收敛于某个点，则有定理4.2，对应是上半连续的当且仅当集合是集合中的一个闭子集。证明：必要性。记集合.设为A中一收敛序列，其中,由上半连续性知显然有故，所以A为中一闭子集。充分性。假设A为上的一个闭子集。如果序列中每个和都有，且收敛于和收敛于，则收敛于。由A的闭性知，即故G为上半连续。证毕！上半连续性是我们熟知的连续函数概念的一种推广，而函数的连续性比上半连续性要强一些，于是有定理4.3，如果是一个从X到Y的连续函数，且对X中的每一个X都有，那么是一个点到集的上半连续对应。证明：设序列，且对每个有和，收敛于，收敛于。由的连续性知故于是G是上半连续的。下面，我们将不动点概念扩充到对应的情形。定义4.7，一个对应F：的一个不动点是中任一满足的。角谷静夫得出如下被广泛应用的一个重要定理。定理4.4 （角谷不动点定理）令S是一个有限维向量空间中任一非空有界闭凸子集。设F：是任一上半连续的点到集对应，且对S中每个都是S的一个非空凸子集。那么，S中一定存在某个使得(Kakutani, 1941)角谷不动点定理说的是对于有限维向量空间中任一非空有界闭凸子集上的上半连续自对应来说，在一定条件下都至少存在一个不动点。角谷不动点定理及其它的一系列相关定理的证明还可参见Burger(1963), Franklin (1980)和Border(1985)。数理经济学家Scarf(1973)曾通过一种计算不动点的算法而提供了一个构造性证明，其中不动点的存在性是由这个定理所保证的。关于角谷不动点定理的推广，可参见Glicksberg (1952)。4.1.2 纳什存在性定理及其证明下面，我们来证明纳什存在性定理，该定理最早由纳什得出，这里的证明由Myerson(1991)给出5。定理4.5 (Nash , 1950)，任何一个战略式表述的有限博弈都至少存在一个混合博弈纳什均衡。证明：令是任战略式表述有限博弈，即显然，是一个有限维向量空间的一个非空有界闭凸子集(注意是有限博弈，即局中人数和每个中的元素个数都是有限数)6。任给和任一局中人i，令即是局中人在中对其余局中人独立混合战略组合的最优反应混合战略。根据定理3.2，是上所有的概率分布组成的集，且使得对每一个满足的有，由定理3.2的证明过程知道，任给显然，故，所以是凸的。根据，因为是有限集，故存在某个使即argmax 是非空的。令，则即故非空。下面构造对应R，它将中的点映射于中的子集，满足：由于对每一个，都是非空凸集，显然也是非空凸集。下面我们来证明R是上半连续的。假设和都是收敛序列且为了证明R是上半连续的，我们将需要证明。因为有：显然期望效用函数是上的连续函数，故有因此，对于每一个有。所以R是到自身上的一个上半连续对应。根据角谷不动点定理，存在中的某个混合战略组合使，即对于每一个有，因此就是的一个（混合）纳什均衡。证毕！4.1.3 其它的纳什均衡存在性定理在纳什存在性定理中，我们只谈及到包括混合战略均衡在内的纳什均衡存在性问题，除此之外，我们自然会对纯战略纳什均衡的存在性感到特别的兴趣。另外，许多博弈不一定是有限博弈，一些常见的博弈的纯战略空间通常都是无限集。在纳什定理之后，其他研究者还得到许多进一步的结果，这些结果中与上述问题相关的有如下几个定理。定理4.6(Debreu, 1952; clicksberg, 1952, Fan, 1952)在n人战略式表述博弈中，如果纯战略空间Si是欧氏空间上的非空有界闭凸子集，支付函数是连续的且对是拟凹的，则G存在一个纯战略纳什均衡。一般地，当函数满足下述性质时，我们称其为凹的：如果当时上面的不等式严格成立，则称为严格凹的。一个函数是凸的当且仅定函数-是凹的；为严格凸函数当且仅当-为严格凹函数。拟凹函数是凹函数概念的一种推广，它包括了凹函数在内的一大类函数，而这类函数在经济学中有着广泛应用，关于拟凹函数的定义如下：定义4.8，函数定义在Rn中的子集D上，当且仅当满足如下性质时，是拟凹的： 0,1显然，凹函数是拟凹的，但反过来并不成立，即拟凹函数不一定是凹函数。在图3.2 中，函数是拟凹的，但不是凹的。x1y0x2x图4.2 不是凹函数的拟凹函数在定理4.6中，与定理4.5相比，我们增强了对支付函数性质的假设，于是获得更进一步的结论，即保证了存在的纳什均衡还是纯战略博弈纳什均衡。在有限博弈场合，即使纯战略空间可能是非凸的，支付函数也可能是非连续的，但混合战略空间是欧氏空间上的非空有界闭凸集，期望支付函数是连续的，拟凹的。当纯战略空间本身是欧氏空间上一个非空的，闭的，有界的凸集且支付函数在纯战略空间上是连续的，拟凹的时，就没有必要引入混合战略了。如果放松定理4.6中关于支付函数的拟凹性假设，则只能保证混合战略均衡的存在性，这就是下面的定理4.7。定理4.7 (Glicksberg, 1952) ，在n人战略式表述博弈中，如果纯战略空间是欧氏空间上一个非空有界闭凸集，支付函数是连续的，则G存在一个混合战略纳什均衡。注释：1这个定理的表述中隐含了X为一个度量空间，所谓度量空间，即在空间X上定义了一个“距离”函数，使得对任意的都有(三角不等式，意思是三角形的两边之和大于第三边)同时还有当且仅当当然，这种定义又要求在空间上首先定义了一种加法“+”和“零”元素。一般地，度量空间的形式化定义为：集合X上的“距离”指到实数轴R上的一个函数，满足：