吴文俊院士与“田忌赛马”鲜为人知的故事
2017/5/8 科学大院
点击上方“科学大院” 可以订阅哦!作者：曹志刚(中国科学院数学与系统科学研究院)
杨晓光(中国科学院数学与系统科学研究院)
俞建(贵州大学理学院)
在中国，“田忌赛马”的故事可谓家喻户晓(故事出自《史记》，讲的是战国时期，齐国大将田忌经常与人赛马，一次，在孙膑的建议下，用和之前同样的马匹，只是通过调换在比赛中的出场顺序而反败为胜)。不过，很多人可能并不知道，这个故事和我国著名数学家吴文俊院士还有一段鲜为人知的联系。
吴院士是最早提出“田忌赛马”属于博弈论的数学家，除了在拓扑学等方面的突出成就，吴院士也是我国最早研究博弈论的数学家。而关于他与博弈论的故事，历史上却是长期被忽视的。
在2010年姜伯驹、李邦河、高小山、李文林主编的为庆祝吴文俊先生九十华诞而出版的《吴文俊与中国数学》一书中，曹志刚、杨晓光、俞建等三位学者合作撰写了《吴文俊关于纳什均衡稳定性的工作及其影响》一文，详细地介绍了吴院士在博弈论方面的贡献，今科学大院经授权刊载(有删减，小标题为编者新加)，缅怀这位中国博弈论研究的先驱。
与博弈论结缘
吴文俊院士是中国最早从事博弈论研究的数学家。
1958年大跃进时期，国内的政治气氛要求数学面向应用，包括华罗庚在内的一批中国顶尖数学家开始从事运筹学的研究。
博弈论属于运筹学的一个分支。由于经典博弈论的一个重要工具是拓扑学中熟知的布劳威尔不动点定理，而吴文俊院士是拓扑学研究的大家，因此他选择了博弈论作为他从事运筹学研究的切入点。
1959年，吴文俊院士发表了中国第一篇博弈论研究论文《关于博弈理论基本定理的一个注记》(科学记录(《科学通报》的前身)，1959，10)。
1960年，他还写了一篇普及性文章《博弈论杂谈：(一)二人博弈》(数学通报，1960，10)，深入浅出地介绍了基本定理的证明。在这篇文章中，第一次明确提出“田忌赛马”的故事属于博弈论范畴，使得中国古代思想宝库中的博弈论思想重放光辉。
同年，吴文俊院士等出版了《对策论(博弈论)讲义》(人民教育出版社出版，1960)，这是我国最早一本有关博弈论的教材。
提出“本质均衡”
吴文俊院士在博弈论方面的最大贡献，是他与他的学生江嘉禾先生合作于1962年对于有限非合作博弈提出了本质均衡(essential equilibrium)的概念，并给出了它的一个重要性质和存在性定理[1]。
本质均衡是这样一个特殊的纳什均衡：如果对支付函数作一个足够小的扰动，那么扰动后的博弈总存在一个与该均衡距离也足够小的纳什均衡。
文章证明了如下性质：给定每个参与者的有限策略集，则所有本质博弈构成的集合是相应空间上的稠密剩余集(即一列稠密开集的交集)。其中本质博弈是指所有纳什均衡都为本质均衡的博弈。因为稠密剩余集是第二纲的，所以在Baire分类意义上几乎所有的博弈都是本质博弈。
文章还给出了如下存在性定理：一个有限策略的策略型博弈(strategic-form game)，如果其纳什均衡的个数有限，则这些纳什均衡中至少有一个是本质均衡。
本质性很好地刻画了纳什均衡的稳定性或鲁棒性(robustness)，所以有的文献经常把本质性和鲁棒性替换使用。
吴文俊院士和江嘉禾先生的结果实际上告诉了我们，无论是从Baire分类意义上还是从测度论意义上来说，几乎所有的博弈都是稳定的。
这是中国数学家在博弈论领域最早的贡献之一，也是迄今为止中国数学家在博弈论领域取得的最具国际影响的成就之一。
为证明其结果，吴文俊院士及时找到了当时最新的数学工具——福特(M.K. Fort)的本质不动点定理[2]。福特的本质不动点是具有某种稳定性的特殊不动点，其存在性定理今天已成为博弈论稳定性分析的标准工具，而吴文俊院士则是国际上最早意识到福特定理重要性的学者之一。
对纳什均衡精炼研究的意义
吴文俊和江嘉禾先生结果的意义还远不局限上述介绍，更重要的是它开创了纳什均衡精炼研究的先河。
纳什均衡，作为博弈论最核心的概念，其最严重的缺点是非唯一性，且经常包含非理性解。如何剔除非理性解对纳什均衡进行精炼以使得它尽可能合理，是上世纪七八十年代博弈论最核心的研究课题。德国博弈论学家泽尔腾(R. Selten)[3]正是凭借这方面的著名工作获得了1994年度的诺贝尔经济学奖。
纳什均衡精炼方面的研究工作是针对扩展型博弈(extensive-form game)和策略型博弈分别进行的。
前一方面的研究思路是要求参与人在博弈不断推进的时候始终具有理性，最著名的工作是泽尔腾在1965年提出的子博弈精炼纳什均衡(sub-game perfect equilibrium,[4])；后一方面的研究思路是要求均衡在各种扰动下保持稳定。纳什均衡在参与人策略扰动的时候应保持稳定，这是泽尔腾1975年提出的颤抖手均衡(trembling hand equilibrium,[5])的主要思想。参与人的策略为什么会出现扰动呢？泽尔腾的解释是任何人做决策的时候都有至少非常微小的概率犯任何错误，这正是该均衡名称的由来。
而纳什均衡在支付函数扰动时应保持稳定，则是吴文俊院士1962文章中率先开辟的思想。同样是均衡在扰动下应保持稳定的思想，吴文俊院士要早于泽尔腾13年正式提出。
博弈论研究成果逐渐被关注
吴文俊院士在本质均衡方面的工作是关于纳什均衡精炼研究方面最早的结果，但是由于历史的原因，改革开放以前的中国学术界与世界学术界处于一种隔绝的状态，一直到上个世纪八十年代吴文俊院士的这一结果才逐步得到了国际博弈论学界的关注，并带动着相关研究的发展：
1、1981年，荷兰学者琴生(M.J.M. Jansen)针对双矩阵博弈，即只有两个参与者的策略型博弈，避开了福特定理，只利用基本的博弈分析重新证明了吴文俊院士的结果。这也是国际上首次对吴文俊院士结果的正式关注[6]；
2、1984年，前苏联博弈论研究的奠基人沃罗比约夫(N. N. Vorobev)在其专著《博弈论基础：非合作博弈》中多次引用了吴文俊院士的结果，并在该书第二章对其1962年的结果作了如此评价，“有限非合作博弈的稳定性，即均衡解对博弈的连续依赖性，很显然首先是由吴文俊和江嘉禾在文章中研究的” 。[7]；
3、1985年，日本学者小岛(M. Kojima)等提出了强稳定均衡的概念(strongly stable equilibrium)，对本质均衡进行了进一步的精炼[8]；
4、1986年，哈佛大学商学院教授科尔伯格(E. Kohlberg)等在著名论文《关于均衡的策略稳定性》中引用了吴先生的工作，指出本质均衡只对策略型博弈有意义[9]；
5、1987年，荷兰学者范德蒙在研究纳什均衡精炼的经典专著《纳什均衡的稳定性与精炼》中[10]，对本质均衡给予了高度评价，并在该书第二章第四节对其进行了专门介绍。由于此书第一章为概述，第二章第一节为基础知识介绍，吴文俊院士的工作被放在了仅次于泽尔腾的颤抖手均衡和迈尔森(R.Myerson)[11]的恰当均衡(proper equilibrium)的重要位置。
又由于恰当均衡是颤抖手均衡的进一步精炼，与颤抖手均衡的的研究思路是相同的，更加可以看出作者对吴文俊院士工作的重视。范德蒙还在此章第六节中利用正则均衡(regular equilibrium)的性质进一步加强了吴文俊先生的结果；
6、1991年，弗登伯格(D.Fudenberg)[12]和梯若尔(J. M. Tirole)[13]合著的世界流行的教科书《博弈论》也在该书第十二章对本质均衡及其理论渊源——福特定理进行了专门介绍，也指出了本质均衡只对策略型博弈有意义[14]；
7、上个世纪九十年代以来，我国博弈论学者俞建教授对吴文俊院士的本质均衡结果进行了一系列推广，不仅将本质均衡推广到线性赋范空间以及线性赋范空间上的广义博弈、多目标博弈和连续博弈，而且进一步研究了平衡点集本质连通区的存在性等问题[15]；
8、2009年，美国学者卡博奈尔-尼科拉(O. Carbonell-Nicolau)在其即将发表于著名的Journal of Economic Theory上的文章中在俞建教授结果的基础上对吴文俊院士的结果进行了进一步的推广[16]；
……
佳话永传
虽然经过二十多年的苦苦探索，博弈论学者并没有找到一个完美的均衡精炼概念，各种均衡精炼概念层出不穷，然而在令人眼花缭乱的均衡精炼概念中，本质均衡是除子博弈精炼纳什均衡和颤抖手均衡以外屈指可数的几个存活下来的概念之一。
更为难能可贵的是，在近半个世纪后的今天，吴文俊院士在本质均衡方面的主要思想及结果，依然被包括马斯金(E. Maskin)、梯若尔[17、18]，威布尔[19、20]等在内的世界一流的博弈论学者在最顶尖的刊物上持续引用，而且近几年的引用频次越来越高。
多少有些令我们感到慨叹的是，吴文俊院士当时工作的出发点更多的是纯数学，文章主要是稳定性研究而没有意识到纳什均衡精炼研究的必要性以及本质均衡与纳什均衡精炼的密切联系。
又由于吴文俊院士的研究兴趣很快转至他处而没能将此工作持续下去(江嘉禾先生有后续的几篇工作，但也都是从纯数学角度研究的)，更没有从事扩展型博弈纳什均衡精炼的研究——这是比策略型博弈纳什均衡精炼重要得多的研究方向，其代表性成果子博弈精炼纳什均衡在扩展型博弈中已完全取代了纳什均衡的位置，渗透到其研究的各个角落，并被写入任何一本博弈论教材。
由于与国际博弈论学界沟通的不足，吴文俊院士的成果直到1981年才在国际上被首次注意，八十年代末才被更多的主流学者所知晓，而此时纳什均衡精炼方面的研究的高潮已经过去。
由于这种种的原因，吴文俊院士的研究在博弈论发展的黄金时期并没有起到按一般逻辑起应该起到的引领潮流的作用，其工作的影响力不仅无法与泽尔腾、范德蒙等人的相关工作相比肩，甚至在纳什均衡精炼方面的研究尘埃落定的今天也并没有得到完全公正的评价。一个代表性的例子是，在新帕尔格雷夫大辞典“纳什均衡精炼”词条中，尽管支付函数扰动的思想被高度认可并做了大篇幅的介绍，吴文俊院士的名字及文章都未被提及[21]。
幸运的是，吴文俊院士的结果在今天依然充满了令人惊异的活力，2007年至今一直被频繁引用，显示了一个数学思想生命力的顽强。而吴文俊院士从事博弈论研究曲曲折折的故事，也必将成为中国数学界和博弈论学界的一段佳话，给我们以永远的启迪。
注释：
[1] W.T. Wu and J.H. Jiang: Essential equilibrium points of n-person non-cooperative games, Scientia Sinica, 11, 1962, 1307-1322.
[2] M.K. Fort, Jr.: Essential and nonessential fixed points. American Journal of Math, 72, 1950, 315-322.
[3] 泽尔腾(Reinhard Selten)，1930——，德国波恩大学(Bonn)教授，著名的博弈论学家，1994年度诺贝尔经济学奖得主。泽尔腾教授不仅在纳什均衡精炼领域有举世公认的成就，还是实验博弈理论的开拓者之一，在有限理性领域也有深刻的研究。南开大学的泽尔腾实验室就是以泽尔腾教授命名的。泽尔腾教授还以喜欢将文章发表到无需同行评议的非正规学术刊物从而避免他认为对其文章不应有的任何修改而闻名博弈论学界。
[4] R. Selten: Spieltheorethische Behandlung eines Oligopolmodells mit Nachfragetra gheit, Z. Ges. Staats. 12 , 1965, 301-324.
[5] R. Selten: Reexamination of the perfectness concept for equilibrium points in extensive games, International Journal of Game Theory, 4(1) , 1975, 25-55.
[6] M.J.M. Jansen: Regularity and stability of equilibrium points of bimatrix games. Mathematics of Operations Research, 6(4), 1981, 530-550.
[7] N. N. Vorobev，Foundations of Game Theory：noncooperative games，Birkhauser, 1994 (翻译自1984年俄文版).
沃罗比约夫1960年曾来中国讲学，并受到周恩来总理的接见。吴文俊院士等编写的《对策论(博弈论)讲义》一书的序言中曾对沃罗比约夫来中国的讲学表示感谢。
[8] M. Kojima, A. Okada & S. Shindoh: Strongly stable equilibrium points of n-person non-cooperative games. Mathematics of Operations Research, 10(4), 1985, 650-663.
[9] E. Kohlberg, J.F. Mertens : On the strategic stability of equilibria. Econometrica: Journal of the Econometric Society, 54(5), 1986, 1003-1037。
这是博弈论著名论文之一，google scholar显示已被引用达851次。
[10] E. van Damme: Stability and Perfection of Nash Equilibria, Springer-Verlag, 1987.
[11] 迈尔森(Roger Myerson)， 1951——，美国芝加哥大学教授，当今最活跃最有影响力的博弈论学家和经济学家之一，因其在机制设计方面的著名工作而获得了2007年度的诺贝尔经济学奖。
[12] 弗登伯格(Drew Fudenberg)，1957——，美国哈佛大学教授，著名的博弈论学家，美国科学与艺术院院士。
[13] 梯若尔(Jean Marcel Tirole)，1953——，法国图卢兹大学(Toulouse)教授，美国科学与艺术院外籍院士，曾任国际经济学会主席，在博弈论、合同理论、产业组织学、认知心理学、政治经济学及货币银行学等多个领域都有建树，并有多本风靡全球的教材，是当今少有的经济学通才及最有影响力的经济学家之一。
[14] D.Fudenberg & J. Tirole: Game Theory. MIT Press, 1991. 有中译本：黄涛等译，《博弈论》，中国人民大学出版社，2003.
[15] 俞建，中国贵州大学教授。他在本质博弈方面的系列性工作，绝大多数都反应在他的专著《博弈论与非线性分析》(科学出版社，2008)。
[16] O. Carbonell-Nicolau: Essential equilibria in normal-form games, Journal of Economic Theory, 2009 (available online).
[17] 马斯金(Eric Maskin)，1950——，美国普林斯顿大学高等研究中心教授，当今最德高望重的博弈论学家和经济学家之一，以其机制设计方面的理论而获得了2007年度的诺贝尔经济学奖。
[18] E.Maskin & J. Tirole: Markov Perfect Equilibrium: I. Observable Actions. Journal of Economic Theory, 100(2), 2001, 191-219.
[19] 威布尔(J?rgen Weibull)，1948——，瑞典斯德哥尔摩经济学院教授，著名的演化博弈论大师，瑞典皇家科学院院士，曾任诺贝尔经济学奖委员会主席。
[20] J. Weibull: Robust set-valued solutions in games. 2009 (available online).
[21] S. Govindan & R. Wilson: Refinements of Nash equilibrium, The New Palgrave Dictionary of Economics, 2nd Edition.
(科学大院已获作者授权转载，发布时略有删改)
大院热门文章top榜
点击文章标题，可直接阅读哦~
1、活下去，需要多少智慧？
2、基因检测，究竟要不要做？
3、中药也有“身份证”？
4、我国恶劣天气是在减少么？
5、为了研究长寿，科学家也是拼了
6、如何肉眼识别夜空中的人造卫星？
7、钱德拉望远镜对银河系外曝光七百万秒，它究竟在拍啥？
8、院士专访|姜文汉：“苦”出来的“自适应光学”
9、当我们阅读外语时我们在阅读什么？
10、突然冒出个“第八大洲”，哦，原来是这样~
科学大院
ID：kexuedayuan
从此，爱上科学~
长按二维码，即刻关注
转载授权、合作、投稿事宜请联系cas@cnic.cn
http://weixin.100md.com
返回 科学大院 返回首页 返回百拇医药