2022年纳什均衡的存在性与多重性 .pdf

《2022年纳什均衡的存在性与多重性 .pdf》由会员分享，可在线阅读，更多相关《2022年纳什均衡的存在性与多重性 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、115 第四章纳什均衡的存在性与多重性对于数学家来说，一个数学概念的存在性与唯一性是特别需要加以关注的。这是因为，从形式逻辑角度看，如果某个事物并不存在，那么关于这个杜撰中的事物所给出的任何陈述或判断都可认为是正确的或错误的，因为对于不存在的事物来说，任何关于它的陈述或判断都不可能加以证伪。所以，倘若某个概念所对应的事物并不存在。那么，关于这个概念所给出的研究结论都必然不存在被证伪的可能。因而根据波普尔的证伪主义观点，这样的研究不具备科学上的意义。所以，我们在对任何新提出来的数学概念加以系统研究之前，首先需要弄清楚所研究的对象事物是否存在。有许多被称为伪科学的东西，它们之所以被人们认为是“伪科

2、学”的原因就是它们大肆谈论的东西并不存在或并未被证实其存在性。譬如，所谓的特异功能或“超灵学”并未得到证实，而UFO 研究迷们至今也未能拿出一件存在球外生命的证据，所以，特异功能学或“超灵学”或“不明飞行物学”实际上都可被归入伪科学。除了存在性之外，概念事物的唯一性也是数学家们所关心的问题。从纯理论的兴趣上看，数学家们更多地是从审美的角度上看待概念的唯一性，但从波普尔的证伪主义哲学看，模型均衡解的唯一性关系到模型的预测功能，从而是科学理论应基本具有的特征。我们在第二章中曾指出，理论的预测功能是判别理论的科学性的准绳，而在第三章中，我们提出用纳什均衡作为模型的预测结果。按照这样的逻辑，一个自然的

3、推论就是：模型能否具有科学意义取决于纳什均衡的唯一性。因为倘若纳什均衡不是唯一的，那么就难以根据模型对即将出现的结果加以预测，这种不确定性对于科学理论来说是不存在的。再加上前面谈到的存在性问题，我们可以这样说，模型能否具有科学意义取决于纳什均衡的存在性和唯一性，因为这正是科学理论所具有的基本性质。博弈论目前发展的情况是这样的：已经证明在非常一般的情况下，纳什均衡是存在的，这是一个好的结果；但是，在许多情形，模型的纳什均衡解不是唯一的，这被称为纳什均衡的多重性问题。纳什在 1950 年代证明了纳什均衡的存在性定理，为非合作博弈打下了重要基础。纳什的工作不仅解决了存在性问题，而且还为其后的博弈论研

4、究提供了一整套方法论工具，即运用不动点定理(fixed point theorem)这一强有力的数学工具进行博弈论数学分析，这对后来的博弈论甚至数理经济学的发展产生了很大的影响。纳什均衡的多重性问题至今仍是困扰博弈论学者的一个主要问题。为了攻克这一问题，博弈论专家已经做出了许多贡献，如聚点均衡、相关均衡，子博弈精炼纳什均衡，颤抖手均衡，序贯均衡等概念的提出。但不幸的是，这类努力还未使得多重均衡问题完全得到解决，许多博弈论专家正在这一领域进行着不懈的工作。本章将给出纳什均衡的存在性定理和讨论存在多重均衡情况下的均衡选择问题。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页

5、-116 4.1 纳什均衡的存在性定理自从纳什(1950)首先给出存在性定理及其证明之后，许多学者又相继提出了不同表述下的存在性定理和不同的证明方法。这里，我们介绍Myerson(1991)给出的存在性定理和证明。4.1.1 纳什均衡与不动点定理所有的存在性定理证明都采用了不动点定理，这是因为，纳什均衡的概念在数学上就是一个不动点的概念。在给出存在性定理及其证明之前，我们先来说明不动点的概念和给出不动点定理。什么是“不动点”呢？考虑一个方程xxf，其中x为方程的解。我们将f视为一种“变换”，即f是将x对应为xfy的变换，其中x和y分别是属于集合X和Y的两个元素，x，Yy。如果YX，则方程xxf

6、的几何意义就是：变换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区间上的自变换函

7、数的不动点45of(x)x*1 0 x*020406080100东 部西 部北 部)(xfx1 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -117 那么，这种现象到底具有多大的一般性意义呢？数学家 Brouwer 在很久以前就注意到这一现象，他得出了如下的一般性定理，即著名的 Brouwer 不动点定理。定理 4.1(Brouwer)设xf是定义在集合 X 上的实函数，且xf，x。如果xf是连 续 的，为一 非空 的有 界 凸 闭集，则 至少存 在一个Xx*使*xxf。即xf至少存在一个不动点1。有意思的是，Brouwer 不动点定理存在很强的几何直观2，但其数学

8、证明却十分艰深，需要动用代数拓扑这类就是职业数学家也感到望而生畏的超级抽象数学工具3。在此，我们不给出Brouwer 不动点定理的证明。直接用来证明纳什存在性定理的不动点定理还不是Brouwer 不动点定理，而是角谷静夫(Kakutani)不动点定理，而后者的证明只是前者的一个相对简单的运用。我们所以要引用角谷静夫不动点定理，是因为在纳什均衡存在性证明中所遇到的反应函数一般是多个因变量函数，即所谓对应(correspondence)，而角谷静夫不动点定理正好描述的是对应的一种性质。角谷静夫不动点定理是Brouwer 不动点定理的推广，但其自身的证明要用到Brouwer 不动点定理。我们在这里不

9、打算给出这两个不动点定理的证明，因为这类证明只是一种纯数学过程，但我们将给出纳什存在性定理的一种证明，因为了解存在性定理的证明过程有助于我们更好地理解纳什均衡。为了解读角谷静夫不动点定理，我们先来准备一下一些有关的数学概念。对于任一有限集 M，我们用 RM表示形如Mmmxx的所有向量组成的集合，其中对 M 中每一个 m，第 m 个分量mx是实数域 R的一个元素。为方便计，我们也可将RM等价地理解为 M 到 R 上的所有函数组成的集合，这时RM中x的m分量mx也可被记为mx。令 S 是 RM中的一个子集，我们有如下定义：定义 4.1 S是凸的(Convex)当且仅当对任意的MMRyRx,及满足1

10、0的，只要Sx和Sy，则有Syx1这里，MmyxyxyyxxmmMmmMmm,11,定义 4.2，S 是闭的(Closed)当且仅当对每个收敛的序列1jjx，如果对每个j都有Sjx，则有Sjxjlim定义 4.3，RM中的子集 S 是开的(open)当且仅当它的补集RM/S是闭的。定义 4.4，S是有界的(bounded)当且仅当存在某个正数K 使得对 S中的每个元素x都有名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -118 MmmKx定义 4.5，一个点到集合的“对应”(correspondence)YXG:是任何一个规定了对X 中的每个点x，xG是与x相对应的

11、Y 中的一个子集。如果 X 和 Y 都是度量空间，则X 和 Y 上的收敛和极限概念已经定义，这时有：定义 4.6，一个对应 G:XY 是上半连续的(upperhemicontinuous)，当且仅当对每个序列1,jjyjx，如果对于每个j有Xjx和jyjxG，而且序列1jjx收敛于某个点Xx，又序列1jjy收敛于某个点Yy，则有)(xGy定理 4.2，对应YXG:是上半连续的当且仅当集合xGyXxyx,是集合YX中的一个闭子集。证明：必要性。记集合YXxGyXxyxA,.设jyjxZj,为 A 中一收敛序列，其中Xjx,1),(jjXgjy由上半连续性知jxGjyjjlimlim显然有Xjxj

12、lim故AZjjlim，所以 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

13、。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 10 页 -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)角谷不动点定理说的是对于有限维向量空间中任一非空有界闭凸子集上的上半连续自对应

14、来说，在一定条件下都至少存在一个不动点。角谷不动点定理及其它的一系列相关定理的证明还可参见Burger(1963),Franklin(1980)和 Border(1985)。数理经济学家Scarf(1973)曾通过一种计算不动点的算法而提供了一个构造性证明，其中不动点的存在性是由这个定理所保证的。关于角谷不动点定理的推广，可参见Glicksberg(1952)。4.1.2 纳什存在性定理及其证明下面，我 们来证 明纳 什存在 性定理，该定 理最早 由纳 什得出，这里 的证明 由Myerson(1991)给出5。定理 4.5(Nash,1950)，任何一个战略式表述的有限博弈都至少存在一个混合博

15、弈纳什均衡。证明：令是任战略式表述有限博弈，即nnuuSS,;11显然，nii1是一个有限维向量空间的一个非空有界闭凸子集(注意是有限博弈，即局中人数和每个iS中的元素个数都是有限数)6。任给和任一局中人i，令iiiiiVRii,maxarg即iiR是局中人i在i中对其余局中人独立混合战略组合i的最优反应混合战略。根据定理3.2，iiR是iS上所有的概率分布i组成的集，且使得对每一个满足iiiSsisVSii,maxarg的iS有0iis，由定理 3.2 的证明过程知道，kikiiikiiisVV,任给令,1,0,iiiiiiRRiii1 名师资料总结-精品资料欢迎下载-名师精心整理-第 5

16、页，共 10 页 -120 显然ii，kiikiikiiiSVV,kkiikiikiikiiksVsV,1,iiiiiiVv,1,)(,iiiiiiRV故iiiR，所以iiR是凸的。根 据RiikiikiiisVV,，因 为iS是 有 限 集，故 存 在 某 个k使iililiikisVsV,max,即 argmax iiisV,是非空的。令klilik,0,1，则iiiiiiVVii,max,即iiiR故iiR非空。下面构造对应 R，它将中的点映射于中的子集，满足：niiiRR1,由于对每一个ni,1，iiR都是非空凸集，显然R也是非空凸集。下面我们来证明 R 是上半连续的。假设1kk和1k

17、k都是收敛序列kkkR,2,1k且kkkklim,lim为了证明 R 是上半连续的，我们将需要证明R。因为有：iikiiikikiiVV,2,1k显然期望效用函数iV是上的连续函数，故有iiiiiiiiVV,因此，对于每一个i有故,iiiRR。所以 R 是到自身上的一个上半连续对应。根据角谷不动点定理，存在中的某个混合战略组合使R，即对于每一个i有iiiR，因此就是的一个（混合）纳什均衡。证毕！名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 10 页 -121 4.1.3 其它的纳什均衡存在性定理在纳什存在性定理中，我们只谈及到包括混合战略均衡在内的纳什均衡存在性问题，除此之外，

18、我们自然会对纯战略纳什均衡的存在性感到特别的兴趣。另外，许多博弈不一定是有限博弈，一些常见的博弈的纯战略空间通常都是无限集。在纳什定理之后，其他研究者还得到许多进一步的结果，这些结果中与上述问题相关的有如下几个定理。定理 4.6(Debreu,1952;clicksberg,1952,Fan,1952)在 n 人 战 略 式表 述 博弈nnuuSSG,;,1中，如果纯战略空间 Si是欧氏空间上的非空有界闭凸子集，支付函数iu是连续的且对iS是拟凹的ni,1，则 G 存在一个纯战略纳什均衡。一般地，当函数xf满足下述性质时，我们称其为凹的：nRxxxfxfxxf212121,1,0,11如果当1

19、,0时上面的不等式严格成立，则称xf为严格凹的。一个函数xf是凸的当且仅定函数-xf是凹的；xf为严格凸函数当且仅当-xf为严格凹函数。拟凹函数是凹函数概念的一种推广，它包括了凹函数在内的一大类函数，而这类函数在经济学中有着广泛应用，关于拟凹函数的定义如下：定义 4.8，函数xf定义在 Rn中的子集 D 上，当且仅当xf满足如下性质时，xf是拟凹的：2121,min1xfxfxxf0,1 显然，凹函数是拟凹的，但反过来并不成立，即拟凹函数不一定是凹函数。在图 3.2 中，函数xf是拟凹的，但不是凹的。图 4.2 不是凹函数的拟凹函数在定理 4.6 中，与定理 4.5 相比，我们增强了对支付函数

20、iu性质的假设，于是获得更进一步的结论，即保证了存在的纳什均衡还是纯战略博弈纳什均衡。在有限博弈场合，即使纯战略空间可能是非凸的，支付函数也可能是非连续的，但混合战略空间是欧氏空间上的非空有界闭凸集，期望支付函数是连续的，拟凹的。当纯战略空间本身是欧氏空x1y 0 x2x xf名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -122 间上一个非空的，闭的，有界的凸集且支付函数在纯战略空间上是连续的，拟凹的时，就没有必要引入混合战略了。如果放松定理 4.6 中关于支付函数的拟凹性假设，则只能保证混合战略均衡的存在性，这就是下面的定理4.7。定理 4.7(Glicksber

21、g,1952)，在 n人战略式表述博弈nuuuSSG11;,中，如果纯战略空间iS是欧氏空间上一个非空有界闭凸集，支付函数iu是连续的，则G 存在一个混合战略纳什均衡。名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 10 页 -123 注释：1这个定理的表述中隐含了X 为一个度量空间，所谓度量空间，即在空间X 上定义了一个“距离”函数，使得对任意的XxXx21,都有2121xxxxi(三角不等式，意思是三角形的两边之和大于第三边)0,021xxii同时还有0 x当且仅当0 x当然，这种定义又要求在空间X上首先定义了一种加法“+”和“零”元素。一般地，度量空间的形式化定义为：集合

22、X 上的“距离”指XX到实数轴 R 上的一个函数yx,，满足：对 X 中任意的yx,和 Z，有：0,xyyx(对称性)yxyx当且仅当0,zxzyyx,(三角不等式)2譬如，揉面的师傅都有着这样的体验，即在面板上揉面时总有一些面粒的位置基本上不因揉面动作变化；另外，男人在梳头时总会发现某一撮头发梳不平整它们呈竖立状伸出。3某些数学家声称已找到Brouwer 不动点定理的初等证明，但从严格的数学证明所要求的严密程度看，这类“证明”，并非真正数学意义上的证明，同时，它们还十分繁锁。譬如见。4这个定义中隐含了Xx的假设。5我们这里将Myerson(1997)中的证明作了一些形式上的修改，主要是为了适应本书的符号系统。6是MR中的一个子集，而1iiSM。名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -124 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -