馮·諾伊曼極小極大值定理,博弈論的開端,數學經濟學最重要理論
就我所知,不可能有博弈論……沒有這個定理……我認為在極小極大值定理被證明之前,沒有什麼值得發表的——約翰·馮·諾伊曼
匈牙利科學家約翰·馮·諾伊曼(1903-1957)對基礎數學、集合理論、量子力學和遍歷理論有著重要的貢獻,此外,他在計算機、核能和人工智慧等方面也深有研究。事實上,馮·諾伊曼在1925年到1950年期間的成果是如此之大,以至於直到今天,他發明的博弈論仍然經常被當作附註提到。
毫無疑問,現代博弈論始於兩人零和博弈中的混合博弈均衡,1928年,約翰·馮·諾伊曼提供了一個證明,這篇論文的標題是:《博弈論》。
16年後,他在1944年與奧斯卡•摩根斯特恩( Oskar Morgenstern)合著的《博弈論與經濟行為理論》被認為是博弈論領域的第一本重要著作。本文的目的是向讀者解釋馮·諾依曼1928年極小極大值定理及其背景。
博弈論
博弈論的歷史可以追溯到1713年,當時詹姆斯·瓦德格拉夫(1864-1741)發明了一種紙牌遊戲“Le Her”,艾薩克·託德亨特在1865年出版的《機率數學理論的歷史——從帕斯卡到拉普拉斯》中描述了這個遊戲:
彼得拿著一副普通的牌,他隨機給保羅一張牌,自己拿了一張,他們的目標是獲得一張比對手更大的牌。
牌從小到大一次是2、3、4……騎士、王后、國王。現在,如果保羅對他的牌不滿意,他可以讓彼得與他交換。但如果彼得有國王,他可以保留國王。
如果彼得對他發到的第一張牌不滿意,或者他對從保羅那裡得到的牌不滿意,他可以隨機從牌堆中換一張牌。但是,如果彼得抽到的牌是王,他就不能得到這張牌,必須保留他不滿意的那張牌。如果保羅和彼得最後得到的牌相同,則保羅為輸家。——節選,《機率數學理論的歷史——從帕斯卡到拉普拉斯》,作者託德亨特。
瓦德格拉夫得出的博弈結論是:
彼得保留8以上的牌,並且交換較小的牌的機率為 62。5%
彼得交換8及以下的牌,持有更大的牌的機率為37。5%
保羅持有7及以上的牌的機率為37。5%
其他早期博弈論分析的例子包括詹姆斯·麥迪遜對不同稅收制度下國家的預期行為方式的分析,以及安東尼·古諾在1838年對雙寡頭壟斷下的納什均衡解的分析。1913年,恩斯特·澤梅洛證明了國際象棋的最優策略是嚴格確定的,即博弈至少存在一個雙方都使用純策略的納什均衡。所有這些早期的例子都出現在約翰·F·納什於1949年發明的非合作博弈論之前。
約翰·馮·諾伊曼1928年的論文
20世紀20年代的兩幅約翰·馮·諾伊曼的畫像
匈牙利約翰·馮·諾伊曼在1926年第一次將注意力轉向博弈論,當時他還是哥廷根大學大衛·希爾伯特的學生。馮·諾伊曼自1923年以來一直致力於集合論的公理化,並剛剛開始為量子力學建立嚴格的數學框架。根據倫納德的說法:
在1926年的某個時候,馮·諾伊曼提出了他對極小極大值定理的證明,毫不奇怪,這個證明被他同時代的研究所掩蓋。
他的方法論顯然是從他在希爾伯特集合論中的研究中得到的公理方法。事實上,正如倫納德所指出的那樣,“機會的概念,透過機率的發揮而成為中心”,這與量子力學的非決定論相一致。馮·諾伊曼在他1928年的論文中指出:
機率是遊戲本身的內在組成部分,所以沒有必要透過遊戲規則人為地引入它,它會自我表現。
MiniMax & MaxiMin
從歷史上看,人們認為有兩種方法可以最佳化“Le Her”等遊戲的結果:
保守貪婪的方法(稱為maximin)
保守激進的方法(稱為minimax)
MaxiMin法
A的選擇是由極大值準則決定的,她會考慮她可能採取的每種策略,在每種情況下,考慮她遵循這些策略所能獲得的最低收益。然後她選擇最小收益最大的策略。
正如作者所指出的,A的策略是極其保守和悲觀的。這是因為,該策略很大程度上依賴於代理人B的能力。玩家A透過這種方法確保了自己的最低收益。
MiniMax法
另一個參與人C,採用了
MiniMax法
,看看對手D在C的每種策略下能獲得多少收益,然後C選擇給D最低收益的策略,D總是這麼做以使自己的收益最大化的話。
正如戴曼德所說,“
MaxiMin法
假設玩家希望保證自己的最小收益。
Minimax法
推測一個玩家想要保證對手的最大收益最小”。M
aximin
是保守貪心的,
而
Minimax
是保守進攻性的。
馮·諾伊曼極小極大值定理(Minimax Theorem)(1928)
馮·諾伊曼和他的論文《論策略的博弈理論》。
任何事件都可以被認為是一種策略遊戲,如果你觀察它對參與者的影響,在外部條件下,假設參與者是自願行動的。——摘自《數學原理》馮·諾伊曼
在1926年的某個時候,馮·諾伊曼提出了他的極小極大值定理的證明。馮·諾伊曼在1926年12月7日,也就是他23歲生日的前三週,向
哥根廷
大學數學學會遞交了他的第一個結果。他的證明是複雜的,因為他以一種讀者難以理解的方式結合了基本概念和拓撲概念,但它仍然是一個有效的證明。1928年,這一結果發表在兩篇文章中:
von Neumann, J. (1928a)
。 Sur la théorie des jeux (“On Game Theory”)。
Comptes Rendus de l’Académie des Sciences, 186
(25): 1689–91。
von Neumann, J. (1928b)
。 Zur Theorie der Gesellschaftsspiele (“The Theory of Games”)。
Mathematische Annalen 100
: 295–320。
法國數學家埃米爾·波雷爾(Émile Borel,1871-1956)在1921-27年間發表了四篇關於戰略博弈的論文,差不多是在同一時間,馮·諾伊曼在他1928年的論文中發展了這一結果。馮·諾伊曼在寫給波萊爾的信中說,他的證明在1926年就得出了。他確信自己是獨立得出這個結論的。
他在腳註中寫道:
當這篇論文完成時,我在1927年1月10日看到了波雷爾的論文。波雷爾給出了對稱二人博弈的雙線性形式問題,並指出MaxMin < MinMax 極大極小是已知的。我們以上的結果回答了他的問題。
極大極小定理(如馮·諾伊曼1928年的結果)提供了保證極小極大不等式也是一個等式的條件,即:
馮·諾伊曼的極小極大值定理也就是說,具有有限多個純策略的兩人零和博弈在Maximin和Minimax 策略相同的情況下有解。這可以保證玩家在最壞的情況下最小化可能的損失。
以後的研究
1937年,馮·諾依曼利用LEJ布勞維爾關於緊凸集連續對映的不動點定理,提供了一個純粹的拓撲證明,證明了一般競爭均衡的存在,這個證明比他1928年的論文更清晰、更簡潔:
von Neumann, J. (1937).
‘Über ein Oikonomisches Gleichungssystem und eine Verallgemeinerung des Brouwerschen Fixpunktsatzes’ in in Menger, K。 (ed)。
Ergebnisse eines Mathematischen Seminars.
Vienna
.
溫特勞布(Weintraub)後來稱這篇論文為“數學經濟學中最重要的論文”,因為它是:
現代一般均衡模型存在性證明;
線性規劃和對偶不等式系統;
高速公路收費理論;
不動點理論的起源。
極大極小定理的第一個純初等證明是在馮·諾伊曼1937年的論文之後的一年,博雷爾的學生讓·維勒(Jean Ville)證明同樣的結果:
Ville, J. (1938).
‘Sur le théorié générale des jeux où intervient l’habiliité des joueurs’。 In Borél et al (ed。), vol。 4。
Applications des jeux de hasard,
p。 105–13。
在同一章中,維勒還首次證明了可能的純博弈連續體情況下的極大極小定理。
博弈論與經濟行為
馮·諾依曼1928年和1937年的論文,簡要指出博雷爾和維勒的證明,在馮·諾依曼和摩根施特恩1944年的著作《博弈論與經濟行為》出版之前,關於博弈均衡的定義和存在性的正式研究相對較少。兩人於1938年在普林斯頓第一次見面,但直到1939年才開始討論博弈論,之後在1941年至1944年期間進行了密切合作,編寫了第一本關於博弈論的長篇著作:
von Neumann, J. & Morgenstern, O. (1944). Theory of Games and Economic Behavior.
Princeton University Press。