第四章 納什均衡的存在性與多重性

/第四章納什均衡的存在性與多重性對于數(shù)學(xué)家來說，一個數(shù)學(xué)概念的存在性與唯一性是特別需要加以關(guān)注的。這是因為，從形式邏輯角度看，如果某個事物并不存在,那么關(guān)于這個杜撰中的事物所給出的任何陳述或判斷都可認為是正確的或錯誤的，因為對于不存在的事物來說,任何關(guān)于它的陳述或判斷都不可能加以證偽。所以,倘若某個概念所對應(yīng)的事物并不存在。那么，關(guān)于這個概念所給出的研究結(jié)論都必然不存在被證偽的可能.因而根據(jù)波普爾的證偽主義觀點，這樣的研究不具備科學(xué)上的意義。所以，我們在對任何新提出來的數(shù)學(xué)概念加以系統(tǒng)研究之前,首先需要弄清楚所研究的對象事物是否存在。有許多被稱為偽科學(xué)的東西，它們之所以被人們認為是“偽科學(xué)”的原因就是它們大肆談?wù)摰臇|西并不存在或并未被證實其存在性。譬如，所謂的特異功能或“超靈學(xué)”并未得到證實，而UＦO研究迷們至今也未能拿出一件存在球外生命的證據(jù),所以，特異功能學(xué)或“超靈學(xué)”或“不明飛行物學(xué)”實際上都可被歸入偽科學(xué).除了存在性之外，概念事物的唯一性也是數(shù)學(xué)家們所關(guān)心的問題。從純理論的興趣上看，數(shù)學(xué)家們更多地是從審美的角度上看待概念的唯一性,但從波普爾的證偽主義哲學(xué)看,模型均衡解的唯一性關(guān)系到模型的預(yù)測功能，從而是科學(xué)理論應(yīng)基本具有的特征。我們在第二章中曾指出,理論的預(yù)測功能是判別理論的科學(xué)性的準繩，而在第三章中，我們提出用納什均衡作為模型的預(yù)測結(jié)果。按照這樣的邏輯，一個自然的推論就是：模型能否具有科學(xué)意義取決于納什均衡的唯一性。因為倘若納什均衡不是唯一的，那么就難以根據(jù)模型對即將出現(xiàn)的結(jié)果加以預(yù)測,這種不確定性對于科學(xué)理論來說是不存在的.再加上前面談到的存在性問題，我們可以這樣說，模型能否具有科學(xué)意義取決于納什均衡的存在性和唯一性，因為這正是科學(xué)理論所具有的基本性質(zhì)。博弈論目前發(fā)展的情況是這樣的：已經(jīng)證明在非常一般的情況下，納什均衡是存在的，這是一個好的結(jié)果;但是，在許多情形，模型的納什均衡解不是唯一的,這被稱為納什均衡的多重性問題.納什在1９５0年代證明了納什均衡的存在性定理，為非合作博弈打下了重要基礎(chǔ)。納什的工作不僅解決了存在性問題，而且還為其后的博弈論研究提供了一整套方法論工具,即運用不動點定理（fixｅdpoiｎttheoｒeｍ)這一強有力的數(shù)學(xué)工具進行博弈論數(shù)學(xué)分析,這對后來的博弈論甚至數(shù)理經(jīng)濟學(xué)的發(fā)展產(chǎn)生了很大的影響.納什均衡的多重性問題至今仍是困擾博弈論學(xué)者的一個主要問題。為了攻克這一問題，博弈論專家已經(jīng)做出了許多貢獻，如聚點均衡、相關(guān)均衡,子博弈精煉納什均衡，顫抖手均衡，序貫均衡等概念的提出。但不幸的是,這類努力還未使得多重均衡問題完全得到解決，許多博弈論專家正在這一領(lǐng)域進行著不懈的工作。本章將給出納什均衡的存在性定理和討論存在多重均衡情況下的均衡選擇問題。４.1納什均衡的存在性定理自從納什(1９50）首先給出存在性定理及其證明之后,許多學(xué)者又相繼提出了不同表述下的存在性定理和不同的證明方法.這里，我們介紹Myeｒｓｏn（19９１）給出的存在性定理和證明.４．１.1納什均衡與不動點定理所有的存在性定理證明都采用了不動點定理，這是因為,納什均衡的概念在數(shù)學(xué)上就是一個不動點的概念.在給出存在性定理及其證明之前,我們先來說明不動點的概念和給出不動點定理。什么是“不動點”呢？考慮一個方程,其中為方程的解.我們將視為一種“變換",即是將對應(yīng)為的變換，其中和分別是屬于集合和的兩個元素,，.如果，則方程的幾何意義就是：變換將變?yōu)樽约?，即在變換下是不變的，故稱的解為變換的不動點.一般地，我們可以將所有的方程都寫為如下形式:（4.1）在式（4.1）兩端加上一個,則變?yōu)?。令則有所以，一般地,方程求解的問題本質(zhì)上是尋找變換的不動點問題.對于這樣一種非常一般地的問題,數(shù)學(xué)家們感到十分高興的是居然在不太嚴格的條件下式（４.1）存在解,即不動點是較為廣泛地存在的。45of(x)x*10x*1譬如，圖4。1表明不動點是曲線與4５45of(x)x*10x*1圖4．1[0,1］區(qū)間上的自變換函數(shù)的不動點那么,這種現(xiàn)象到底具有多大的一般性意義呢？數(shù)學(xué)家Brouwer在很久以前就注意到這一現(xiàn)象，他得出了如下的一般性定理，即著名的Brouwｅr不動點定理。定理4．1（Brouweｒ……)設(shè)是定義在集合Ｘ上的實函數(shù)，且，。如果是連續(xù)的,為一非空的有界凸閉集，則至少存在一個使.即至少存在一個不動點［1］。有意思的是，Brouwer不動點定理存在很強的幾何直觀[2］,但其數(shù)學(xué)證明卻十分艱深,需要動用代數(shù)拓撲這類就是職業(yè)數(shù)學(xué)家也感到望而生畏的超級抽象數(shù)學(xué)工具[3］。在此,我們不給出Brouweｒ不動點定理的證明。直接用來證明納什存在性定理的不動點定理還不是Bｒｏuｗeｒ不動點定理,而是角谷靜夫（Ｋａkｕtａnｉ)不動點定理，而后者的證明只是前者的一個相對簡單的運用。我們所以要引用角谷靜夫不動點定理，是因為在納什均衡存在性證明中所遇到的反應(yīng)函數(shù)一般是多個因變量函數(shù),即所謂對應(yīng)（correｓpondence),而角谷靜夫不動點定理正好描述的是對應(yīng)的一種性質(zhì)。角谷靜夫不動點定理是Bｒｏuwｅr不動點定理的推廣，但其自身的證明要用到Brouwer不動點定理。我們在這里不打算給出這兩個不動點定理的證明，因為這類證明只是一種純數(shù)學(xué)過程，但我們將給出納什存在性定理的一種證明，因為了解存在性定理的證明過程有助于我們更好地理解納什均衡。為了解讀角谷靜夫不動點定理，我們先來準備一下一些有關(guān)的數(shù)學(xué)概念。對于任一有限集M，我們用ＲM表示形如的所有向量組成的集合,其中對Ｍ中每一個ｍ，第m個分量是實數(shù)域Ｒ的一個元素。為方便計，我們也可將ＲM等價地理解為M到R上的所有函數(shù)組成的集合，這時ＲＭ中的分量也可被記為。令Ｓ是RM中的一個子集，我們有如下定義：定義4.1S是凸的（Ｃｏnveｘ）當且僅當對任意的及滿足的,只要和，則有這里，定義４.２，S是閉的(Closeｄ)當且僅當對每個收斂的序列，如果對每個都有，則有定義４．3，RM中的子集Ｓ是開的（oｐeｎ)當且僅當它的補集RM/Ｓ是閉的。定義4。4,S是有界的（bounded）當且僅當存在某個正數(shù)K使得對S中的每個元素都有定義４。５，一個點到集合的“對應(yīng)”（correspｏｎｄencｅ）是任何一個規(guī)定了對Ｘ中的每個點,是與相對應(yīng)的Y中的一個子集。如果X和Y都是度量空間,則X和Y上的收斂和極限概念已經(jīng)定義，這時有：定義4．6,一個對應(yīng)G：X→Y是上半連續(xù)的（upｐer—ｈｅmｉcontinuous），當且僅當對每個序列,如果對于每個有和,而且序列收斂于某個點，又序列收斂于某個點，則有定理4．2,對應(yīng)是上半連續(xù)的當且僅當集合是集合中的一個閉子集。證明：必要性。記集合．設(shè)為A中一收斂序列,其中，由上半連續(xù)性知顯然有故,所以A為中一閉子集。充分性。假設(shè)A為上的一個閉子集。如果序列中每個和都有,且收斂于和收斂于，則收斂于.由A的閉性知,即故G為上半連續(xù)。證畢!上半連續(xù)性是我們熟知的連續(xù)函數(shù)概念的一種推廣，而函數(shù)的連續(xù)性比上半連續(xù)性要強一些，于是有定理４。3,如果是一個從X到Y(jié)的連續(xù)函數(shù),且對Ｘ中的每一個X都有，那么是一個點到集的上半連續(xù)對應(yīng)。證明:設(shè)序列，且對每個有和,收斂于,收斂于。由的連續(xù)性知故于是G是上半連續(xù)的.下面，我們將不動點概念擴充到對應(yīng)的情形.定義4.７,角谷靜夫得出如下被廣泛應(yīng)用的一個重要定理。定理4。4（角谷不動點定理）令Ｓ是一個有限維向量空間中任一非空有界閉凸子集。設(shè)F：是任一上半連續(xù)的點到集對應(yīng),且對S中每個都是S的一個非空凸子集.那么，S中一定存在某個使得(Kakuｔaｎi，19４1）角谷不動點定理說的是對于有限維向量空間中任一非空有界閉凸子集上的上半連續(xù)自對應(yīng)來說,在一定條件下都至少存在一個不動點.角谷不動點定理及其它的一系列相關(guān)定理的證明還可參見Burger（1963)，Ｆrａnklin（1980）和Boｒdｅr（1985）。數(shù)理經(jīng)濟學(xué)家Sｃarｆ（1973）曾通過一種計算不動點的算法而提供了一個構(gòu)造性證明，其中不動點的存在性是由這個定理所保證的。關(guān)于角谷不動點定理的推廣，可參見Ｇlicksbｅrg（19５2）。4。1。2納什存在性定理及其證明下面，我們來證明納什存在性定理，該定理最早由納什得出，這里的證明由Ｍyｅrsoｎ(1９91）給出[5］。定理4。5（Ｎａsｈ,１9５0），任何一個戰(zhàn)略式表述的有限博弈都至少存在一個混合博弈納什均衡。證明：令是任—戰(zhàn)略式表述有限博弈，即顯然，是一個有限維向量空間的一個非空有界閉凸子集(注意是有限博弈，即局中人數(shù)和每個中的元素個數(shù)都是有限數(shù))[6]。任給和任一局中人i，令即是局中人在中對其余局中人獨立混合戰(zhàn)略組合的最優(yōu)反應(yīng)混合戰(zhàn)略。根據(jù)定理3。2,是上所有的概率分布組成的集，且使得對每一個滿足的有，由定理3.２的證明過程知道，任給顯然，故，所以是凸的。根據(jù),因為是有限集,故存在某個使即arｇmaｘ是非空的。令，則即故非空.下面構(gòu)造對應(yīng)R，它將中的點映射于中的子集，滿足：由于對每一個，都是非空凸集,顯然也是非空凸集。下面我們來證明R是上半連續(xù)的.假設(shè)和都是收斂序列且為了證明R是上半連續(xù)的,我們將需要證明.因為有：顯然期望效用函數(shù)是上的連續(xù)函數(shù)，故有因此，對于每一個有。所以R是到自身上的一個上半連續(xù)對應(yīng)。根據(jù)角谷不動點定理,存在中的某個混合戰(zhàn)略組合使，即對于每一個有，因此就是的一個（混合)納什均衡。證畢!4.1.3其它的納什均衡存在性定理在納什存在性定理中,我們只談及到包括混合戰(zhàn)略均衡在內(nèi)的納什均衡存在性問題,除此之外，我們自然會對純戰(zhàn)略納什均衡的存在性感到特別的興趣。另外,許多博弈不一定是有限博弈,一些常見的博弈的純戰(zhàn)略空間通常都是無限集。在納什定理之后，其他研究者還得到許多進一步的結(jié)果,這些結(jié)果中與上述問題相關(guān)的有如下幾個定理。定理4.6（Debreu，1952；clｉckｓbeｒｇ,1952,Ｆan,1９52）在ｎ人戰(zhàn)略式表述博弈中,如果純戰(zhàn)略空間Ｓi是歐氏空間上的非空有界閉凸子集，支付函數(shù)是連續(xù)的且對是擬凹的，則G存在一個純戰(zhàn)略納什均衡。一般地，當函數(shù)滿足下述性質(zhì)時,我們稱其為凹的:如果當時上面的不等式嚴格成立，則稱為嚴格凹的。一個函數(shù)是凸的當且僅定函數(shù)-是凹的;為嚴格凸函數(shù)當且僅當—為嚴格凹函數(shù).擬凹函數(shù)是凹函數(shù)概念的一種推廣，它包括了凹函數(shù)在內(nèi)的一大類函數(shù)，而這類函數(shù)在經(jīng)濟學(xué)中有著廣泛應(yīng)用,關(guān)于擬凹函數(shù)的定義如下:定義４．8,函數(shù)定義在Rｎ中的子集D上，當且僅當滿足如下性質(zhì)時，是擬凹的：［0，1]顯然,凹函數(shù)是擬凹的，但反過來并不成立，即擬凹函數(shù)不一定是凹函數(shù)。在圖3。2中，函數(shù)是擬凹的，但不是凹的。xx1y0x2x圖4.2不是凹函數(shù)的擬凹函數(shù)在定理4．6中，與定理4。5相比，我們增強了對支付函數(shù)性質(zhì)的假設(shè),于是獲得更進一步的結(jié)論,即保證了存在的納什均衡還是純戰(zhàn)略博弈納什均衡。在有限博弈場合，即使純戰(zhàn)略空間可能是非凸的，支付函數(shù)也可能是非連續(xù)的，但混合戰(zhàn)略空間是歐氏空間上的非空有界閉凸集，期望支付函數(shù)是連續(xù)的,擬凹的。當純戰(zhàn)略空間本身是歐氏空間上一個非空的，閉的，有界的凸集且支付函數(shù)在純戰(zhàn)略空間上是連續(xù)的，擬凹的時,就沒有必要引入混合戰(zhàn)略了。如果放松定理4.6中關(guān)于支付函數(shù)的擬凹性假設(shè)，則只能保證混合戰(zhàn)略均衡的存在性，這就是下面的定理4。7。定理4．7（Ｇlｉcｋsｂerｇ，1952）,在n人戰(zhàn)略式表述博弈中,如果純戰(zhàn)略空間是歐氏空間上一個非空有界閉凸集,支付函數(shù)是連續(xù)的，則G存在一個混合戰(zhàn)略納什均衡。注釋：[１]這個定理的表述中隱含了X為一個度量空間，所謂度量空間,即在空間Ｘ上定義了一個“距離”函數(shù)，使得對任意的都有（三角不等式，意思是三角形的兩邊之和大于第三邊)

同時還有 當且僅當當然,這種定義又要求在空間上首先定義了一種加法“+”和“零”元素。一般地,度量空間的形式化定義為:集合X上的“距離"指到實數(shù)軸R上的一個函數(shù),滿足：對X中任意的和Ｚ，有：(對稱性)