第四章纳什均衡的存在性与多重性

115第四章纳什均衡的存在性与多重性对于数学家来说，一个数学概念的存在性与唯一性是特别需要加以关注的。这是因为，从形式逻辑角度看，如果某个事物并不存在，那么关于这个杜撰中的事物所给出的任何陈述或判断都可认为是正确的或错误的，因为对于不存在的事物来说，任何关于它的陈述或判断都不可能加以证伪。所以，倘若某个概念所对应的事物并不存在。那么，关于这个概念所给出的研究结论都必然不存在被证伪的可能。因而根据波普尔的证伪主义观点，这样的研究不具备科学上的意义。所以，我们在对任何新提出来的数学概念加以系统研究之前，首先需要弄清楚所研究的对象事物是否存在。有许多被称为伪科学的东西，它们之所以被人们认为是“伪科学”的原因就是它们大肆谈论的东西并不存在或并未被证实其存在性。譬如，所谓的特异功能或“超灵学”并未得到证实，而UFO研究迷们至今也未能拿出一件存在球外生命的证据，所以，特异功能学或“超灵学”或“不明飞行物学”实际上都可被归入伪科学。除了存在性之外，概念事物的唯一性也是数学家们所关心的问题。从纯理论的兴趣上看，数学家们更多地是从审美的角度上看待概念的唯一性，但从波普尔的证伪主义哲学看，模型均衡解的唯一性关系到模型的预测功能，从而是科学理论应基本具有的特征。我们在第二章中曾指出，理论的预测功能是判别理论的科学性的准绳，而在第三章中，我们提出用纳什均衡作为模型的预测结果。按照这样的逻辑，一个自然的推论就是：模型能否具有科学意义取决于纳什均衡的唯一性。因为倘若纳什均衡不是唯一的，那么就难以根据模型对即将出现的结果加以预测，这种不确定性对于科学理论来说是不存在的。再加上前面谈到的存在性问题，我们可以这样说，模型能否具有科学意义取决于纳什均衡的存在性和唯一性，因为这正是科学理论所具有的基本性质。博弈论目前发展的情况是这样的：已经证明在非常一般的情况下，纳什均衡是存在的，这是一个好的结果；但是，在许多情形，模型的纳什均衡解不是唯一的，这被称为纳什均衡的多重性问题。纳什在1950年代证明了纳什均衡的存在性定理，为非合作博弈打下了重要基础。纳什的工作不仅解决了存在性问题，而且还为其后的博弈论研究提供了一整套方法论工具，即运用不动点定理(fixedpointtheorem)这一强有力的数学工具进行博弈论数学分析，这对后来的博弈论甚至数理经济学的发展产生了很大的影响。纳什均衡的多重性问题至今仍是困扰博弈论学者的一个主要问题。为了攻克这一问题，博弈论专家已经做出了许多贡献，如聚点均衡、相关均衡，子博弈精炼纳什均衡，颤抖手均衡，序贯均衡等概念的提出。但不幸的是，这类努力还未使得多重均衡问题完全得到解决，许多博弈论专家正在这一领域进行着不懈的工作。本章将给出纳什均衡的存在性定理和讨论存在多重均衡情况下的均衡选择问题。1164.1纳什均衡的存在性定理自从纳什(1950)首先给出存在性定理及其证明之后，许多学者又相继提出了不同表述下的存在性定理和不同的证明方法。这里，我们介绍Myerson(1991)给出的存在性定理和证明。4.1.1纳什均衡与不动点定理所有的存在性定理证明都采用了不动点定理，这是因为，纳什均衡的概念在数学上就是一个不动点的概念。在给出存在性定理及其证明之前，我们先来说明不动点的概念和给出不动点定理。什么是“不动点”呢？考虑一个方程xxf，其中x为方程的解。我们将f视为一种“变换”，即f是将x对应为xfy的变换，其中x和y分别是属于集合X和Y的两个元素，x，Yy。如果YX，则方程xxf的几何意义就是：变换f将x变为自己，即x在f变换下是不变的，故称xxf的解为变换f的不动点。一般地，我们可以将所有的方程都写为如下形式：0xy(4.1)在式(4.1)两端加上一个x，则变为xxxy。令xxyxf则有xxf所以，一般地，方程求解的问题本质上是寻找变换的不动点问题。对于这样一种非常一般地的问题，数学家们感到十分高兴的是居然在不太严格的条件下式(4.1)存在解，即不动点是较为广泛地存在的。譬如，图4.1表明不动点是曲线f与45o线的交点。当函数xf定义在1,0x区间上且因变量xfy的值域也为1,0区间时，如果xf是连续的，则必然存在不动点。图4.1[0,1]区间上的自变换函数的不动点45of(x)x*10x*020406080100第一季度第二季度第三季度第四季度东部西部北部)(xfx1117那么，这种现象到底具有多大的一般性意义呢？数学家Brouwer在很久以前就注意到这一现象，他得出了如下的一般性定理，即著名的Brouwer不动点定理。定理4.1(Brouwer……)设xf是定义在集合X上的实函数，且xf，x。如果xf是连续的，为一非空的有界凸闭集，则至少存在一个Xx*使**xxf。即xf至少存在一个不动点[1]。有意思的是，Brouwer不动点定理存在很强的几何直观[2]，但其数学证明却十分艰深，需要动用代数拓扑这类就是职业数学家也感到望而生畏的超级抽象数学工具[3]。在此，我们不给出Brouwer不动点定理的证明。直接用来证明纳什存在性定理的不动点定理还不是Brouwer不动点定理，而是角谷静夫(Kakutani)不动点定理，而后者的证明只是前者的一个相对简单的运用。我们所以要引用角谷静夫不动点定理，是因为在纳什均衡存在性证明中所遇到的反应函数一般是多个因变量函数，即所谓对应(correspondence)，而角谷静夫不动点定理正好描述的是对应的一种性质。角谷静夫不动点定理是Brouwer不动点定理的推广，但其自身的证明要用到Brouwer不动点定理。我们在这里不打算给出这两个不动点定理的证明，因为这类证明只是一种纯数学过程，但我们将给出纳什存在性定理的一种证明，因为了解存在性定理的证明过程有助于我们更好地理解纳什均衡。为了解读角谷静夫不动点定理，我们先来准备一下一些有关的数学概念。对于任一有限集M，我们用RM表示形如Mmmxx的所有向量组成的集合，其中对M中每一个m，第m个分量mx是实数域R的一个元素。为方便计，我们也可将RM等价地理解为M到R上的所有函数组成的集合，这时RM中x的m分量mx也可被记为mx。令S是RM中的一个子集，我们有如下定义：定义4.1S是凸的(Convex)当且仅当对任意的MMRyRx,及满足10的，只要Sx和Sy，则有Syx1这里，MmyxyxyyxxmmMmmMmm,11,,定义4.2，S是闭的(Closed)当且仅当对每个收敛的序列1jjx，如果对每个j都有Sjx，则有Sjxjlim定义4.3，RM中的子集S是开的(open)当且仅当它的补集RM/S是闭的。定义4.4，S是有界的(bounded)当且仅当存在某个正数K使得对S中的每个元素x都有118MmmKx定义4.5，一个点到集合的“对应”(correspondence)YXG:是任何一个规定了对X中的每个点x，xG是与x相对应的Y中的一个子集。如果X和Y都是度量空间，则X和Y上的收敛和极限概念已经定义，这时有：定义4.6，一个对应G:X→Y是上半连续的(upper—hemicontinuous)，当且仅当对每个序列1,jjyjx，如果对于每个j有Xjx和jyjxG，而且序列1jjx收敛于某个点Xx，又序列1jjy收敛于某个点Yy，则有)(xGy定理4.2，对应YXG:是上半连续的当且仅当集合xGyXxyx,,是集合YX中的一个闭子集。证明：必要性。记集合YXxGyXxyxA,,.设jyjxZj,为A中一收敛序列，其中Xjx,,,1),(jjXgjy由上半连续性知jxGjyjjlimlim显然有Xjxjlim故AZjjlim，所以A为YX中一闭子集。充分性。假设A为YX上的一个闭子集。如果序列1,jjyjx中每个jx和jy都有Xjx，jxGjy且1jjx收敛于x和1jjy收敛于y，则jyjxZj,收敛于yx,。由A的闭性知Ayx,，即xGy故G为上半连续。证毕！上半连续性是我们熟知的连续函数概念的一种推广，而函数的连续性比上半连续性要强一些，于是有定理4.3，如果YXy:是一个从X到Y的连续函数，且对X中的每一个X都有xyxG，那么YXG:是一个点到集的上半连续对应。证明：设序列1,jjyjx，且对每个j有Xjx和jxGjy，1jjx收敛于x，1jjy收敛于y。119由y的连续性知xyy故xGy于是G是上半连续的。下面，我们将不动点概念扩充到对应的情形。定义4.7，一个对应F：SS的一个不动点是S中任一满足xFx的x。角谷静夫得出如下被广泛应用的一个重要定理。定理4.4（角谷不动点定理）令S是一个有限维向量空间中任一非空有界闭凸子集。设F：SS是任一上半连续的点到集对应，且对S中每个xFx,都是S的一个非空凸子集。那么，S中一定存在某个x使得xFx(Kakutani,1941)角谷不动点定理说的是对于有限维向量空间中任一非空有界闭凸子集上的上半连续自对应来说，在一定条件下都至少存在一个不动点。角谷不动点定理及其它的一系列相关定理的证明还可参见Burger(1963),Franklin(1980)和Border(1985)。数理经济学家Scarf(1973)曾通过一种计算不动点的算法而提供了一个构造性证明，其中不动点的存在性是由这个定理所保证的。关于角谷不动点定理的推广，可参见Glicksberg(1952)。4.1.2纳什存在性定理及其证明下面，我们来证明纳什存在性定理，该定理最早由纳什得出，这里的证明由Myerson(1991)给出[5]。定理4.5(Nash,1950)，任何一个战略式表述的有限博弈都至少存在一个混合博弈纳什均衡。证明：令是任—战略式表述有限博弈，即nnuuSS,;11显然，nii1是一个有限维向量空间的一个非空有界闭凸子集(注意是有限博弈，即局中人数和每个iS中的元素个数都是有限数)[6]。任给和任一局中人i，令iiiiiVRii,maxarg即iiR是局中人i在i中对其余局中人独立混合战略组合i的最优反应混合战略。根据定理3.2，iiR是iS上所有的概率分布i组成的集，且使得对每一个满足iiiSsisVSii,maxarg的iS有0iis，由定理3.2的证明过程知道，kikiiikiiisVV,,任给令,1,0,,'iiiiiiRRiii1''120显然ii''，kiikiikiiiSVV,,''''kkiikiikiikiiksVsV,1,'iiiiiiVv,~1,~)(~,,~iiiiiiRV故iiiR''，所以iiR是凸的。根据RiikiikiiisVV,,，因为iS是有限集，故存在某个k使iililiikisVsV,max,即argmaxiiisV,是非空的。令klilik,0,1，则iiiiiiVVii,max,即iiiR故