博弈论

博弈论,又译为对策论,或者赛局表面,运用数学的一个分支,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),出生于匈牙利的美国籍犹太人数学家,当代电子盘算机与博弈论的主要创始人,泛函剖析、遍历表面、几何学、拓扑学和数值剖析等众大都学范畴及盘算机学、量子力学和经济学中都有庞大奉献。
简介
相关人物