博弈论

博弈论,又译为对策论,或者赛局理论,应用数学的一个分支,1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》,标志着现代系统博弈理论的的初步形成,因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

来源:维基百科
简介

博弈的标准式表达包括:1)博弈的参与者,2)每一参与者可供选择的战略集,3)针对所有参与者可能选择的战略组合,每一个参与者获得的收益。我们后面将经常讨论到n个参与者的博弈,其中参与者从1到n排序,设其中任一参与者的序号为i,令S_{i} 代表参与者i可以选择的战略集合(称为i的战略空间),其中任意一个特定的战略用 S_{i} 表示(有时我们写成 s_{i}\epsilon S_{i} 表示战略 s_{i} 是战略集S_{i} 中的要素)。令(s_{1},s_{2},......s_{n} )表示每个参与者选定一个战略形成的战略组合,u_{i} 表示第i个参与者的收益函数,u_{i}(s_{1},......,s_{n})即为参与者选择战略 (s_{1},s_{2},......s_{n} ) 时第i个参与者的收益。将上述内容综合起来,我们得到:

定义:在一个n人博弈的标准式表述中,参与者的战略空间为S_{1},......,S_{n} , 收益函数为 u_{1},......,u_{n} ,我们用G=\left \{ S_{1},...S_{n};u_{1},...,u_{n} \right \} 表示此博弈。

来源:《博弈论基础》 罗伯特·吉本斯著 高峰 译 中国社会科学出版社

年份事件相关论文
2008阐述了博弈论中推理与机器学习之间的等价性Iead Rezek, David S. Leslie.2008.On Similarities between Inference in Game Theory and Machine Learning.J. Artif. Intell. Res.
2012提出了一个基于博弈论的分类器,作为一个迭代博弈方法进行模式分类Craig M. Vineyard, Gregory L. Heileman.2012.Game theoretic mechanism design applied to machine learning classification. International Workshop on Cognitive Information Processing
2017针对高效视频编码(HEVC)中的帧间编码树单元(CTU)级比特分配和码率控制(RC)优化问题,提出了一种联合机器学习和博弈论建模(MLGT)框架。Wei Gao, Sam Kwong, Yuheng Jia.2017.Joint Machine Learning and Game Theory for Rate Control in High Efficiency Video Coding.IEEE Transactions on Image Processing

例子:

一天,警局接到报案,一位富翁被杀死在自己的别墅中,家中的财物也被洗劫一空。经过多方调查,警方最终将嫌疑人锁定在杰克和亚当身上,因为事发当晚有人看到他们两个神色慌张地从被害人的家中跑出来。警方到两人的家中进行搜查,结果发现一部分被害人家中失窃的财物,于是将二人作为谋杀和盗窃的嫌疑人拘留。

但是,到了拘留所里面,两人都矢口否认自己杀过人,他们辩解称自己只是路过那里,想进去偷点东西,结果进去的时候发现主人已经被人杀死了,于是他们随便拿点东西就走了。这样的解释不能让人信服,再说,谁都知道在判刑方面杀人要比盗窃严重得多。警察决定将两人隔离审讯。

隔离审讯的时候,警察告诉杰克:“尽管你们不承认,但是我知道人就是你们两个杀的,事情早晚会水落石出。现在我给你一个坦白的机会,如果你坦白了,亚当拒不承认,那你就是主动自首,同时协助警方破案,你将被立即释放,亚当则坐10年牢;如果你们都坦白了,每人坐8年牢;都不坦白的话,可能已入室盗窃罪判你们每人1年,如何选择你自己想一想吧。”同样的话,警察也说给了亚当。

一般人可能认为杰克和亚当都会选择不坦白,这样他们只能以入室盗窃的罪名被判刑,每人只需坐1年牢。这对于两人来说是最好的一个结局。可结果会是这样吗?答案是否定的,两人都选择了招供,结果每人各被判刑8年。

事情为什么会是这样呢?杰克和亚当为什么会做出这样“不理智”的选择呢?其实这种结果正是两人的理智造成的。我们先看一下两人坦白与否及其结局的矩阵图:


亚当
杰克
坦白不坦白
坦白(8,8)(0,10)
不坦白(10,0)(1,1)

当警察把坦白与否的后果告诉杰克的时候,杰克心中就会开始盘算坦白对自己有利,还是不坦白对自己有利。杰克会想,如果选择坦白,要么当即释放,要么同亚当一起坐8年牢;要是选择不坦白,虽然可能坐1年牢,但也可能坐10年牢。虽然(1,1)对两人而言是最好的一种结局,但是由于是被分开审讯,信息不通,所以谁也没法保证对方是否会选择坦白。选择坦白的结局是8年或者0年,选择不坦白的结局是10年或1年,在不知道对方选择的情况下,选择坦白对自己来说是一种优势策略。于是,杰克会选择坦白。同时,亚当也会这样想。最终的结局便是两个人都选择坦白,没人都要坐8年牢。

上面的这个案例就是著名的“囚徒困境”模式,是博弈论中最出名的一个模式。为什么杰克和亚当每个人都选择了对自己最有利的策略,最后得到的确实最差的结果呢?这其中便蕴含着博弈论的道理。

博弈论是指双方或者多方在竞争、合作、冲突的情况下,充分了解各方信息,并依此选择一种能为本方争取最大利益的最优策略的理论。

发展历史

约翰·冯·诺依曼和奥斯卡。摩根斯坦在他们1944年著名的《博弈论和经济行为》一书中引进了通用博弈理论的思想,书中提出大部分经济问题都应该被当作是博弈进行分析。他们介绍了博弈的扩展式和标准式的表示法,定义了最小最大解,并证明了这个解在所有双人零和博弈中存在。(在一个零和博弈中,两个参与人的利益是完全相对的,完全没有任何共同利益。)纳什提出了后来被称为“纳什均衡”的概念,将这一概念作为把博弈论的分析扩展到非零和博弈的一种方法,纳什均衡要求每个参与人的策略是针对他所预言的对手策略的支付最大化反应,并且进一步认为每个参与人的预言都是正确的。这是古诺和伯兰特所研究的特定模型均衡的一个自然推广,并且它是大多数经济分析的起点。泽尔腾和海萨尼引入了近年来被广为使用的概念。泽尔腾证明了再参与人选择相机计划的博弈中不是所有的纳什均衡都是同样合理的。

海萨尼提出了一种使用标准博弈论技术来模型化不完全信息情形的方法,在标准的技术中假设所有参与人都知道他人的收益函数,而在不完全信息下参与人对其他人的收益是不确定的。他的贝叶斯纳什均衡是很多博弈论分析的基础。

主要事件

年份事件相关论文
1950提出了纳什均衡的概念Nash,J.1950.Equilibrium points in N-person games. Proceedings of the National Academy of Sciences 36: 48-49
1965证明了再参与人选择相机计划的博弈中不是所有的纳什均衡都是同样合理的。Selten,R.1965. Spieltheoretische Behandlungeines Oligopolmodels mit Nachfragetragheit.Zeitschrift fur die gesamte Staatswissenschaft 12:301-324
1967使用标准博弈论技术来模型化不完全信息情形的方法Harsanyi,J. 1967-68. Games with incomplete information played by Bayesian players. Management Science 14:159-182,320-334,485-502
年份事件相关论文
2009介绍了合作博弈论的概念,即联盟博弈,和其在通信和无线网络中的潜在应用Walid Saad, Zhu Han, Mérouane Debbah, Are Hjørungnes, Tamer Basar.(2009).Coalitional Game Theory for Communication Networks: A Tutorial.ArXiv
2010介绍了博弈论最基本的概念,并详细解释了如何利用这些概念设计频谱共享协议Beibei Wang, Yongle Wu, K. J. Ray Liu.(2010).Game theory for cognitive radio networks: An overview.Computer Networks
2013使用博弈论的方法,研究了计算机和通信网络的安全性和隐私性Mohammad Hossein Manshaei, Quanyan Zhu, Tansu Alpcan, Tamer Basar, Jean-Pierre Hubaux.(2013).Game theory meets network security and privacy.ACM Comput. Surv.
2013博弈论方法被用作处理网络攻击Xiannuan Liang, Yang Xiao.(2013).Game Theory for Network Security.IEEE Communications Surveys & Tutorials

发展分析

瓶颈

  • 博弈论还应充分考虑特征、境域的影响,以对纳什均衡做更深层次的分析。
  • 博弈论赖以展开推理分析的隐含主体律是简单隐含主题律,它难以阐明现实世界中复杂的决策及决策间相互影响的过程。
  • 博弈论对信息的处理是理想化的,这在实际应用中存在严重缺陷

未来发展方向

根据以上三个缺陷发展的复合博弈论是博弈论基础理论和应用发展的必然取向,另外,要拓广博弈论的应用领域,要加深博弈论在各个领域尤其是在经济学领域中的应用。

Contributor:Peng Jiang

相关人物
Nahum Shimkin
Nahum Shimkin
Nahum Shimkin是以色列理工学院电气工程教授,研究兴趣包括:随机控制,马尔可夫决策过程;强化学习,在线学习,Bandit过程;排队系统:博弈论分析与控制;轨迹优化与任务规划。
冯·诺依曼
冯·诺依曼
约翰·冯·诺伊曼(德语:John von Neumann,1903年12月28日-1957年2月8日),原名诺依曼·亚诺什·拉约什(匈牙利语:Neumann János Lajos),出生于匈牙利的美国籍犹太人数学家,现代电子计算机与博弈论的重要创始人,在泛函分析、遍历理论、几何学、拓扑学和数值分析等众多数学领域及计算机学、量子力学和经济学中都有重大贡献。
简介
相关人物