冯·诺伊曼极小极大值定理，博弈论的开端，数学经济学最重要理论

就我所知，不可能有博弈论……没有这个定理……我认为在极小极大值定理被证明之前，没有什么值得发表的——约翰·冯·诺伊曼

　　匈牙利科学家约翰·冯·诺伊曼（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法推测一个玩家想要保证对手的最大收益最小”。Maximin是保守贪心的， 而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）后来称这篇论文为“数学经济学中最重要的论文”，因为它是：

1. 现代一般均衡模型存在性证明；
2. 线性规划和对偶不等式系统；
3. 高速公路收费理论；
4. 不动点理论的起源。

　　极大极小定理的第一个纯初等证明是在冯·诺伊曼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.