1、博弈論與非線性分析俞建貴州大學(xué)數(shù)學(xué)系貴州省博弈、決策和控制理論重點(diǎn)實(shí)驗(yàn)室2008年3月（一）我們知道，博弈論是由Von Neumann和Morgenstern在1944年合作的名著“博弈論與經(jīng)濟(jì)行為”1的出版而宣告誕生的. 在“序言”中，他們就提出“經(jīng)濟(jì)與社會(huì)問(wèn)題可以從這個(gè)角度得到最好的解釋”，在第1章中，他們又指出“博弈論是建立經(jīng)濟(jì)行為理論的最恰當(dāng)?shù)姆椒ā?1J.Von Neumann, O.Morgenstern, Theory of Games and Economic Behavior, 1944(有中譯本，王文玉等譯，2004).1中深入研究了矩陣博弈：局中人1，純策略的集合，混合策

2、略的集合.局中人2，純策略的集合，混合策略的集合.如果局中人1選擇，局中人2選擇，則局中人2支付局中人1，所有構(gòu)成一個(gè)矩陣. 這樣，如果局中人1選擇混合策略，局中人2選擇混合策略，則局中人2支付局中人1的期望支付是.Von Neumann證明了:,使換句話說(shuō)，是此矩陣博弈的平衡點(diǎn)，或者有.以上結(jié)果稱為最大最小定理(最好的愿望，最壞的準(zhǔn)備).年輕的Nash將Von Neumann的矩陣博弈的模型在兩個(gè)方面作了推廣：由2人人，尤其是由零和非零和, 這種博弈稱為人有限非合作博弈. 以二人有限非合作博弈（雙矩陣博弈）為例來(lái)說(shuō)明：如果局中人1選擇純策略, 局中人2選擇純策略，則局中人1得到支付, 局中人

3、2得到支付, 未要求（），允許，雙贏. 這樣如果局中人1選擇混合策略, 局中人2選擇混合策略, 則局中人1和局中人2得到的期望支付分別是和.1950和1951年，Nash23證明了：,使這樣的之后稱為Nash平衡點(diǎn)：誰(shuí)都不能通過(guò)單獨(dú)改變自己的策略而使自己獲得更大的利益 .Nash平衡點(diǎn)是非合作博弈中最重要、最核心的概念 .2, Proceedings of the National Academy of Sciences,USA,36(1950),48-49.3 Annals of Mathematics,54(1951),286-295. Von Neumann 和Nash工作的兩個(gè)理論前提

4、：對(duì)每個(gè)局中人來(lái)說(shuō)，所有信息都是公開的，完全的，對(duì)稱的；每個(gè)局中人都是完全理性的，都能夠在各自策略集中選擇對(duì)自己最為有利的策略.對(duì)應(yīng)用來(lái)說(shuō)，以上兩個(gè)假設(shè)太理想了，太苛刻了，因?yàn)樗竺總€(gè)局中人都是神無(wú)所不知且無(wú)所不能. Harsanyi和Selten的工作分別在這兩個(gè)方面提出了新的思想，大大擴(kuò)展了博弈論的應(yīng)用，正因?yàn)槿绱耍麄儾排cNash一起，在“博弈論與經(jīng)濟(jì)行為”一書出版整整50年后，共同獲得了1994年的Nobel經(jīng)濟(jì)獎(jiǎng)，也正是這次獲獎(jiǎng)，才確認(rèn)了博弈論對(duì)經(jīng)濟(jì)理論的核心重要性.具體來(lái)說(shuō), Harsanyi在非對(duì)稱信息條件下，提出了“類型”的概念，用Bayes方法對(duì)博弈論模型進(jìn)行分析，為信息經(jīng)

5、濟(jì)學(xué)奠定了基礎(chǔ). 而Selten將完全理性看作有限理性的極限，提出了Nash平衡點(diǎn)精練的概念.Nobel經(jīng)濟(jì)獎(jiǎng)中的博弈論工作獲獎(jiǎng)年 份獲獎(jiǎng)?wù)攉@獎(jiǎng)原因1994HarsanyiNashSelten在非合作博弈平衡分析的研究中，作出了開創(chuàng)性的貢獻(xiàn)2005AumannSchelling在沖突與合作問(wèn)題的研究中，作出了開創(chuàng)性的貢獻(xiàn)獲獎(jiǎng)年份獲獎(jiǎng)?wù)攉@獎(jiǎng)原因1996MirrlessVickrey在非對(duì)稱信息條件激勵(lì)理論的研究中，作出了開創(chuàng)性的貢獻(xiàn)2001AkelofSpenceStiglitz在非對(duì)稱信息市場(chǎng)的研究中，作出了開創(chuàng)性的貢獻(xiàn)2007HurwiczMaskinMyerson在機(jī)制設(shè)計(jì)理論的研究中，作

6、出了開創(chuàng)性貢獻(xiàn)1996年、2001年和2007年的獲獎(jiǎng)工作屬于信息經(jīng)濟(jì)學(xué)的領(lǐng)域，而從本質(zhì)上講，這些工作都是非合作博弈論在經(jīng)濟(jì)學(xué)中的重要應(yīng)用，因此也都包含在20世紀(jì)90年代以來(lái)出版的任何一本博弈論的教科書中. Maskin和Myerson都是杰出的博弈論學(xué)者，Myerson還有名著“博弈論，矛盾沖突分析”出版. 此外，2002年Nobel經(jīng)濟(jì)獎(jiǎng)的獲得者是Kahneman和Smith，其中Kahneman是因把心理學(xué)研究融入經(jīng)濟(jì)學(xué)而獲獎(jiǎng),他是行為經(jīng)濟(jì)學(xué)的倡導(dǎo)人; Smith是因在實(shí)驗(yàn)經(jīng)濟(jì)學(xué)作出了開創(chuàng)性貢獻(xiàn)而獲獎(jiǎng)，而許多經(jīng)濟(jì)學(xué)實(shí)驗(yàn)也是從博弈論開始的.博弈論的研究近些年來(lái)如此火熱，主要原因還在于經(jīng)濟(jì)實(shí)

7、踐發(fā)展和與之相適應(yīng)的經(jīng)濟(jì)理論發(fā)展的需要. 近些年來(lái)，經(jīng)濟(jì)全球化深入發(fā)展，生產(chǎn)規(guī)模擴(kuò)大，壟斷勢(shì)力增強(qiáng)，人們要談判，討價(jià)還價(jià)，進(jìn)行交易，所有這一切都建立在個(gè)人理性的基礎(chǔ)上，建立在競(jìng)爭(zhēng)的基礎(chǔ)之上. 隨著這種競(jìng)爭(zhēng)和沖突的日益加劇，各種策略和利益的對(duì)抗、依存和制約的持續(xù)發(fā)展，使博弈論（主要是非合作博弈）的研究達(dá)到了全盛時(shí)期，由它的概念、內(nèi)容、思想和方法出發(fā)，已經(jīng)并將繼續(xù)幾乎全面地改寫經(jīng)濟(jì)學(xué)，也并將得到更加廣泛的應(yīng)用.博弈論與經(jīng)濟(jì)學(xué)的關(guān)系極為密切，這是可以理解的，但是博弈論與非線性分析的關(guān)系又如何呢？二者也是非常密切的.首先，Von Neumann在1中的“技術(shù)說(shuō)明”中就指出：“很難說(shuō)當(dāng)代數(shù)學(xué)中的哪一分支

8、學(xué)科及其哪一部分是必需的.不過(guò)，要想比較透徹地了解本書所分析的問(wèn)題，讀者必須超越傳統(tǒng)的數(shù)學(xué)推理方式，這些推理主要是數(shù)理邏輯、集合論和泛函分析的推理”.在1中，Von Neumann是用凸集分離定理來(lái)證明矩陣博弈平衡點(diǎn)的存在性的，而在4中，他用的是以下引理：Von Neumann引理設(shè)是兩個(gè)非空有界閉凸集，是兩個(gè)非空閉集. 如果1)是非空閉凸集2)是非空閉凸集，則.4J.Von Neumann, Ergebnisse eines Mathenmatischen Kolloquiums,8(1935-1936),73-83.在2和3中，Nash是分別應(yīng)用以下Brouwer不動(dòng)點(diǎn)定理和Kakutan

9、i不動(dòng)點(diǎn)定理來(lái)證明人有限非合作博弈平衡點(diǎn)的存在性的.Brouwer不動(dòng)點(diǎn)定理設(shè)是非空有界閉凸集,映射連續(xù),則,使.Kakutani不動(dòng)點(diǎn)定理設(shè)是非空有界閉凸集,集值映射上半連續(xù),且，是中的非空閉凸集,則，使.我們知道, Kakutani不動(dòng)點(diǎn)定理是應(yīng)用Brouwer不動(dòng)點(diǎn)定理來(lái)證明的,而它也是Brouwer不動(dòng)點(diǎn)定理的推廣,見5; 而Kakutani不動(dòng)點(diǎn)定理與Von Neumann引理是等價(jià)的,見6.5J.Franklin,Methods of Mathematical Economics,1980(有中譯本,俞建,顧悅譯,1985).order,Fixed Point Theorems w

10、ith Applications and Game Theory,1985. 這樣, 無(wú)論是Von Neumann還是Nash, 兩位大師對(duì)博弈論研究的奠基之作就與凸分析、集值映射、不動(dòng)點(diǎn)定理，與非線性分析緊密聯(lián)系在一起了.(二)Von Neumann的矩陣博弈的概念很快就被推廣到以下二人零和博弈:設(shè)和分別是局中人1和局中人2的策略集, 當(dāng)局中人1選擇策略,局中人2選擇策略, 則局中人1從局中人2獲得的支付為（此時(shí)局中人2從局中人1獲得的支付為，支付和為零，故稱為二人零和博弈）. 如果存在,使則稱為此二人零和博弈的平衡點(diǎn)，此時(shí), 有, 即是在中的鞍點(diǎn). Nash的 人非合作有限博弈的概念很快就

11、被推廣到以下人非合作博弈:設(shè)是局中人的集合, ,是第個(gè)局中人的策略集, 是第個(gè)局中人的支付函數(shù). ,記.如果存在,使,有,則稱為此博弈的Nash平衡點(diǎn). 如果,則此博弈的Nash平衡點(diǎn)即為在中的鞍點(diǎn).1) 平衡點(diǎn)與不動(dòng)點(diǎn)的關(guān)系:,定義集值映射如下: .定義集值映射如下:.則是以上博弈的Nash平衡點(diǎn)當(dāng)且僅當(dāng)是集值映射的不動(dòng)點(diǎn).2) Nash平衡點(diǎn)與Ky Fan點(diǎn)的關(guān)系:Ky Fan點(diǎn)的概念是由我們7引入的:設(shè)函數(shù),如果,使,有,則稱為函數(shù)的Ky Fan點(diǎn). 注意到8引入了平衡問(wèn)題的概念:如果,使,有,則稱為平衡問(wèn)題的解.無(wú)論是7還是8,都是建立在非線性分析中著名的Ky Fan不等式的基礎(chǔ)之上的

12、9.8E.Blum,W.Oettli,Math.Student,63(1994),123-145.9Ky Fan,in Inequality (O.Shisha Eds),1972,103-113.定義函數(shù)如下:.則是以上博弈的Nash平衡點(diǎn)當(dāng)且僅當(dāng)是函數(shù)的KyFan點(diǎn).以上人非合作博弈的概念很快又被推廣到以下的廣義博弈:設(shè),是第個(gè)局中人的可行策略映射.如果存在,使,有,且,則稱為此廣義博弈的平衡點(diǎn).如果,則此廣義博弈的平衡點(diǎn)即為人非合作博弈Nash平衡點(diǎn).1) 平衡點(diǎn)與不動(dòng)點(diǎn)的關(guān)系:,定義集值映射如下:.定義集值映射如下:.則是以上廣義博弈的平衡點(diǎn)當(dāng)且僅當(dāng)是集值映射的不動(dòng)點(diǎn).2) 平衡點(diǎn)與擬

13、變分不等式(QVI)解的關(guān)系:定義函數(shù)如下:.定義集值映射如下:.則是以上廣義博弈的平衡點(diǎn)當(dāng)且僅當(dāng)是擬變分不等式的解(即, 且,有). 1954年, Arrow和Debreu10正是應(yīng)用廣義博弈平衡點(diǎn)的存在性證明了數(shù)理經(jīng)濟(jì)學(xué)中一般均衡的存在性, Arrow和Debreu也主要是因?yàn)檫@項(xiàng)杰出的工作而分別在1972年和1983年獲得Nobel經(jīng)濟(jì)獎(jiǎng). 更加詳盡的研究見11.1011Theoy,1995(有中譯本，劉文忻，李紹榮主譯2001) .以下是著名的Fan-Glicksberg不動(dòng)點(diǎn)定理, FanBrowder不動(dòng)點(diǎn)定理和Ky Fan不等式:(1) Fan-Glicksberg不動(dòng)點(diǎn)定理設(shè)是

14、Hausdorff局部凸空間中的非空凸緊集, 集值映射是上半連續(xù)的,且, 是中的非空凸緊集, 則, 使.(2) FanBrowder不動(dòng)點(diǎn)定理設(shè)是Hausdorff線性拓?fù)淇臻g中的非空凸緊集, 集值映射滿足1), 是中的非空凸集, 2), 是中的開集, 則, 使. (3) Ky Fan不等式設(shè)是Hausdorff線性拓?fù)淇臻g中的非空凸緊集, 滿足1）, 在上是下半連續(xù)的, 2）, 在上是擬凹的, 3）, , 則, 使, 有. 應(yīng)用以上三個(gè)結(jié)果,可以證明以下二人零和博弈平衡點(diǎn)存在性定理, 人非合作博弈Nash平衡點(diǎn)存在性定理和廣義博弈的平衡點(diǎn)存在性定理.(1)二人零和博弈鞍點(diǎn)存在性定理設(shè)和分別是

15、Hausdorff線性拓?fù)淇臻g和中的非空凸緊集, 滿足1) , 是下半連續(xù)和擬凸的, 2）, 是上半連續(xù)和擬凹的, 則, 使, 有. (2) 人非合作博弈Nash平衡點(diǎn)存在性定理設(shè)是局中人的集合, 設(shè)是Hausdorff線性拓?fù)淇臻g中的非空凸緊集, 連續(xù), 且, 在上是擬凹的, 則, 使, 有.(3) 廣義博弈的平衡點(diǎn)存在性定理設(shè)是局中人的集合, , 設(shè)是Hausdorff局部凸空間中的非空凸緊集, 連續(xù), 且, 在上是擬凹的,集值映射 連續(xù), 且,是中的非空凸緊集, 則, 使, 有, 且.當(dāng)然以上存在性定理都可以有不少推廣,我們做過(guò)不少工作,例如見12.12Theory,24(1995),2

16、17-222. (三)目前博弈論的難題是一個(gè)博弈可能有多個(gè)平衡點(diǎn)而如何選取的問(wèn)題.對(duì)矩陣博弈,或者更廣泛的二人零和博弈,這個(gè)難題不存在. 設(shè)和分別是局中人1和局中人2的策略集, 是局中人1的支付函數(shù),記是在中的鞍點(diǎn)全體. 可以容易地證明,如果, , 則, 且. 這說(shuō)明即使在中的鞍點(diǎn)不唯一,也不存在如何合理選取的問(wèn)題,因?yàn)榫种腥?選擇策略或, 局中人2選擇策略或,得到的都是鞍點(diǎn),且無(wú)論在哪個(gè)鞍點(diǎn)處, 局中人1和局中人2得到的支付都是相等的.以上結(jié)果對(duì)雙矩陣博弈就不成立. Nash平衡點(diǎn)太多了,應(yīng)當(dāng)加以精練, Selten在1975年給出了以下完美平衡點(diǎn)的概念13.13R以雙矩陣博弈為例：設(shè)局中人

17、1和局中人2都不是完全理性的，而是有限理性的，是可能犯錯(cuò)誤的，在他們作出決策時(shí)可能會(huì)發(fā)生某種“顫抖”. 設(shè)足夠小（滿足, ）, 而是擾動(dòng)博弈中局中人1的策略集, 是擾動(dòng)博弈中局中人2的策略集.擾動(dòng)博弈必存在Nash平衡點(diǎn).如果是當(dāng)時(shí)的一個(gè)極限點(diǎn), 即是當(dāng)局中人1和局中人2犯錯(cuò)誤的概率逐漸減小, “顫抖”逐漸消失時(shí)被擾動(dòng)博弈平衡點(diǎn)的極限點(diǎn), 則稱是原博弈的一個(gè)完美平衡點(diǎn). Selten證明了完美平衡點(diǎn)必存在. 這種經(jīng)擾動(dòng)而回復(fù)的平衡點(diǎn), 當(dāng)然具有一種穩(wěn)定性. 用這種方法, Selten就刪除了一些不穩(wěn)定的平衡點(diǎn), 使太多了的Nash平衡點(diǎn)得到了一種精煉.實(shí)際上,中國(guó)數(shù)學(xué)家吳文俊和江加禾14早在1

18、962年就給出了一個(gè)深刻的結(jié)果.為了研究Nash平衡點(diǎn)的穩(wěn)定性, 他們對(duì)人有限非合作博弈引入了本質(zhì)平衡點(diǎn)和本質(zhì)博弈的概念, 并證明了任意有限非合作博弈都可以用一列本質(zhì)博弈來(lái)任意逼近,而他們是應(yīng)用15中關(guān)于本質(zhì)不動(dòng)點(diǎn)的結(jié)果而得到這一結(jié)果的. 1415以雙矩陣博弈為例, ,定義映射如下:, ；, . 容易驗(yàn)證: ；, . Nash早已證明, 是雙矩陣博弈的平衡點(diǎn)當(dāng)且僅當(dāng)是連續(xù)映射在中的不動(dòng)點(diǎn). 14證明了由雙矩陣博弈(和確定)到連續(xù)映射的映射是連續(xù)的,于是由15中本質(zhì)不動(dòng)點(diǎn)的結(jié)果即可推得雙矩陣博弈本質(zhì)平衡點(diǎn)的結(jié)果.一般情況下,我們可以考慮定義在線性賦范空間凸緊集上滿足一定連續(xù)性和凸性條件的向量值函

19、數(shù)的集合,在適當(dāng)引進(jìn)距離之后, 成為一個(gè)完備度量空間. 表示對(duì)應(yīng)于博弈(分別表示個(gè)局中人的定義在上的支付函數(shù))的所有Nash平衡點(diǎn)所成之集.我們要問(wèn):當(dāng)變化很小時(shí),集合是否變化也很小?這當(dāng)然是穩(wěn)定性問(wèn)題的研究. 稱為博弈的本質(zhì)平衡點(diǎn),是指當(dāng)充分接近時(shí),有也充分接近;稱為本質(zhì)博弈,是指所有都是博弈的本質(zhì)平衡點(diǎn).我們16證明了: 是本質(zhì)博弈當(dāng)且僅當(dāng)集值映射在是連續(xù)的;應(yīng)用Fort關(guān)于集值映射通有連續(xù)性(generic continuity)的結(jié)果17,我們16還證明了:存在中一個(gè)稠密剩余集 (稱為剩余集,是指包含一列在中稠密開集的交集),使,是本質(zhì)博弈(因在中稠密,任一博弈當(dāng)然可以用一列本質(zhì)博弈來(lái)

20、任意逼近),此時(shí), ,其中是上的Hausdorff距離,博弈的Nash平衡點(diǎn)集是穩(wěn)定的.更加深入的研究可見1819,其中19是關(guān)于空間類的討論.16俞建，應(yīng)用數(shù)學(xué)學(xué)報(bào)，16（1993），153-157.1718J.Yu,J of Mathematical Economics,31(1999),361-372.19 J.Yu,在Baire分類的意義下，稠密剩余集是第二類型的（第二綱的），即對(duì)大多數(shù)的博弈來(lái)說(shuō)，它的Nash平衡點(diǎn)集都是穩(wěn)定的.應(yīng)用類似的方法，我們20還證明了：設(shè)和分別是線性賦范空間和中的凸緊集，是滿足一定連續(xù)性和凸性條件的函數(shù)的集合(在適當(dāng)引進(jìn)距離之后, 成為一個(gè)完備度量空間)，則

21、存在中的一個(gè)稠密剩余集，使,在中的鞍點(diǎn)是唯一的，即在Baire分類的意義上，對(duì)絕大多數(shù)的函數(shù)，它的鞍點(diǎn)都是唯一的.20 Acad. of Sci. Mathematics,43(1995),119-129.關(guān)于有限理性與平衡的穩(wěn)定性的關(guān)系，還可見2122.21C.Yu,J.Yu,Nonlinear Analysis,Theroy,Method s and Applications,65(2006),583-592.22C.Yu,J.Yu,Nonlinear Analysis,Theroy,Methods and Applications,67(2007),930-937.在Selten之后,

22、考慮到各種形式的顫抖和擾動(dòng), 又有恰當(dāng)平衡點(diǎn)23、序列平衡點(diǎn)24等精煉概念. 2324D.Kreps,R.Wilson,Econometrica,50(1982),863-894.1986年, 為了更加全面地研究Nash平衡點(diǎn)的穩(wěn)定性, Kohlberg和Mertens25提出了這樣的問(wèn)題: 一個(gè)穩(wěn)定的Nash平衡點(diǎn)應(yīng)該滿足哪些必要的條件? 這是公理化的方法, 他們希望用這種方法對(duì)平衡點(diǎn)進(jìn)行精煉. 通過(guò)細(xì)致的論證, 他們得出結(jié)論: 一般還不能將它精煉成單點(diǎn)集, 它只能是集值的，是所謂平衡點(diǎn)集的本質(zhì)連通區(qū). 因?yàn)樵谌擞邢薹呛献鞑┺闹校總€(gè)局中人的策略集均為單純形, 支付函數(shù)也均為多項(xiàng)式, 其Na

23、sh平衡點(diǎn)集就必是等式和不等式的有限系統(tǒng)的解集,稱為半代數(shù)集(semi-algebraic set). 他們首先應(yīng)用代數(shù)幾何的方法證明了: 任一人有限非合作博弈，其平衡點(diǎn)集的連通區(qū)必為有限個(gè), 然后證明了至少有一個(gè)是本質(zhì)的. 這一工作影響很大, 而他們的工作又被26等改進(jìn)和推廣. 更加深入的研究可見2728.2526J.Hillas,Econometrica,58(1990),1365-1390.27J.Hillas,M.Jensen,J.Potters,D.Vermeulen,Mathematics of Operations Research,26(2001),611-636.28102(200