|
来源 | 张纪峰、冯维维 编辑 | 学术君 近年来，博弈论相关的概念和工具在控制、多智能体系统和网络研讨中的应用简直呈指数增长。 在接受《国度科学评论》（NSR）访谈时，美国国度工程院院士，伊利诺伊大学香槟分校Swanlund讲席教授（该校教员最高荣誉）、高等研讨中心主任，IEEE控制系统学会和美国自动控制理事会前任主席，国际动态博弈论学会开创主席塔米尔·巴萨（Tamer Basar），谈到了最近博弈论在控制和网络研讨中的新兴角色、它如何将控制范畴的边疆拓展到工程以外的学科，以及未来的机遇和应战。
Tamer Basar（Swanlund讲席教授、伊利诺斯大学香槟分校高等研讨中心主任） 博弈论是什么及其在控制中的作用 NSR：您能简单地通知我们什么是博弈论、它是做什么的吗？ Basar： 博弈论处置的是多个决策者即博弈参与者（某些状况下称为代理人）之间的战略交互。由一个目的函数描写每个参与者在多个可能的博弈结果之间的排序偏好，她要么试图最大化目的函数（在此状况下，目的函数是功效函数或效益函数），要么最小化目的函数（在这种状况下，我们称目的函数为成本函数或损失函数）。 对非平凡博弈来说，参与者的目的函数取决于至少一位其他参与者的选择（行为或决策变量），并且通常是一切参与者的选择，因而参与者不能简单地独立于其他人的选择而优化自己的目的函数。 因而，这使参与者的行动之间产生了耦合，并招致即便在非协作环境下，参与者在决策过程中也绑定在一同。 假如参与者能达成协作协议，构成集体性的、完整可信的行动或决策选择，让一切参与者都能尽可能地受益，那么我们将处于协作博弈论的范畴。 假如参与者之间不允许协作，那么我们就处于非协作博弈论的范畴。博弈论，作为一种系统性的措施，首先必须引入一个令人称心的解概念。 首要地，解应具有这样的特征：一切参与者都不能经过单边行动来进步收益，这就是所谓的非协作均衡或以约翰纳什的名字命名的纳什均衡。 60多年前，约翰·纳什引入了它，并且证明它存在于有限博弈（即每个参与者只需有限数量的替代计划的博弈）和混合战略中。对恣意一个参与者，假如其他参与者依照纳什均衡采取行动，这个参与者将无法经过偏离纳什均衡来进步自己的收益。 请留意，我们不允许两个或两个以上的参与者从解点集体行动，由于这样的集体行动需求协作，这是不允许在非协作博弈中发作的。 另一个非协作均衡解的概念是斯塔克尔伯格均衡（Stackelberg equilibrium），它实践上先于纳什均衡提出。 其中，参与者的决策之间有一个层次，一些参与者被指定为指导者，有才干首先宣布他们的战略（并承诺执行他们）；其他的参与者被指定为跟随者，依据指导者的战略决议他们的战略（跟随者之间也存在相互博弈）。 但是，在宣布战略之前，指导者会预测跟随者的反响，并以一种对自己最有利的方式决议其行动（就其目的函数而言）。 NSR：我们遇到的不同类型的博弈有哪些？ Basar： 我们能够把博弈分为两大类，即协作博弈和非协作博弈。后一类是更普遍意义下的控制界所感兴味的，我们能够对它做进一步的分类。 假如参与者的目的函数之和不能在恰当的正缩放和/或不依赖于参与者的决策变量的平移后变为零，我们称这样的非协作博弈是严厉的（或真正的）非零和博弈。 假如一个博弈只需两个参与者，两个参与者的目的函数之和为零，或者能够经过恰当的正缩放和/或不依赖于参与者的决策变量的平移使其为零，我们称它是零和博弈。 进一步的细分基于参与者可运用的行动计划性质，以及这些行动如何决议结果。假如每个参与者只需数量有限的行动计划，即参与者从有限汇合（动作集）当选择他们的动作，这种博弈就是有限博弈，否则就是无限博弈。 有限博弈也称为矩阵博弈。假如参与者的动作集是连续的，且其目的函数相关于一切参与者的动作变量是连续的，则无限博弈被称为连续核博弈。 正如目的函数所捕获的，假如参与者的行为单独决议结果，那么这样的博弈被以为是肯定性博弈；而假如至少一个参与者的目的函数依赖于一个具有潜在概率散布的附加变量（自然状态），那么我们就称之为随机博弈。 假如博弈描画（即参与者、目的函数和潜在概率散布（假如是随机的）是一切参与者的共同信息，那么这就是完整信息博弈；否则我们就称其为不完整信息博弈。 假如参与者只能取得先验信息（一切人共享），而不能取得任何其他参与者的行动信息，我们会称其为静态博弈；否则，我们就称其为动态博弈。假如每个参与者只行动一次，我们称其为单次博弈；否则将称其为多次博弈。请留意，单次博弈可能是动态的，多次博弈可能是静态的。 假如断策过程的演化（由参与者随时间控制）发作在连续的时间内，通常触及一个微分方程，这样的动态博弈就被称为微分博弈；假如它发作在离散的时间范围内，则动态博弈有时被称为离散时间博弈。 NSR：战略的概念在博弈中起着重要作用，特别是在动态博弈中，是这样吗？ Basar： 的确如此。在动态博弈中，随着博弈的中止，参与者取得关于其他参与者过去行为的信息（完好或部分的），并在选择自己的行为时运用这些信息。 例如，在有限动态博弈中，博弈过程可用树结构表示（也称为扩展式），其中每个节点代表一个参与者及其行动时间，节点的分支显现特定参与者可能的行动。 当参与者对其他参与者过去的行动没有完好的信息时，就构成了参与者的信息集。在扩展式博弈中，参与者决议的不是他们的行动，而是他们的战略，即他们在每个信息集采取的行动。然后，依据战略以及在博弈树上的位置，他们采取特定的行为。 因而，此时的均衡是定义在战略上而非行动上的。假如非要与控制论相比，那么，战略就像控制律，或等价地，控制战略，它依据控制者所能取得的信息，通常包含被控系统的状态，来生成控制信号(或命令)作为系统的输入控制。被控系统的状态信息能够经过圆满或含噪信道取得。 NSR：请问控制和动态博弈之间能否存在关联？ Basar： 的确有。控制，特别是最优控制，能够看作是单个参与者的动态（或微分）博弈。进一步，由于纳什均衡的表征和计算触及到每个参与者个体优化问题的解，因而给最优控制开发的工具，如动态规划或极大值原理，在动态博弈中肯定是有用的。 但是，假如参与者有不同类型的信息，那么动态博弈的状况就会愈加复杂。即便一些参与者具有开环信息，而其他参与者都具有完整信息，不论是动态规划还是极大值原理，都不能用来结构纳什均衡。 对其他类型的信息结构，状况愈加复杂。这在目前依旧是一个生动的研讨范畴，而且动态博弈中信息结构的复杂性也是我多年来不时很感兴味的问题。 关于零和动态博弈或微分博弈来说，状况更容易处置一些，这招致了鲁棒控制的胜利，其中系统可能有模型不肯定性和/或未知输入。 基于零和博弈论措施的鲁棒控制允许系统的未知信息被视为对手博弈者所控制的输入，而其目的与控制器完整相反。 这种控制器和虚拟对手之间的直接利益抵触招致了零和动态博弈的构成，其在给定的控制器信息结构下的极大极小解或鞍点解也由对手（中止收益最大化的博弈参与者）共享，从而为系统提供了鲁棒控制律。 这种措施曾经产生了不同信息结构下线性和非线性系统的最优H∞设计（即H无量控制），并曾经为经济学家所采用，例如被诺贝尔奖得主拉尔斯·汉森（Lars Hansen）和托马斯· 萨金特（Thomas Sargent）2008年在普林斯顿大学出版社出版的《鲁棒性》（Robustness）一书中采用。 博弈论的历史演化 NSR：博弈论的来源能够追溯到什么时分？您能够谈谈相关历史吗？ Basar： 1944年，约翰·冯·诺伊曼和奥斯卡·摩根斯坦合著的《博弈论与经济行为》(Theory of Games and Economic Behavior)一书的出版，被普遍以为是这一范畴的正式起点。尔后，博弈论的理论成果不时增加，应用的范围和范畴也在不时扩展。 作为对该范畴生机的认可，到目前为止，共有10个诺贝尔经济学奖，其主要工作是博弈论。 1994年，约翰·海萨尼（John Harsanyi）、约翰·纳什（ John Nash）和莱因哈德·泽尔腾（Reinhard Selten）取得了第一次博弈论相关的诺奖，以惩处他们“在非协作博弈理论中对均衡的开创性剖析”。 2005年，博弈论方面的第二次诺贝尔奖颁给了罗伯特奥曼（Robert Aumann）和托马斯谢林（Thomas Schelling），获奖理由是“经过博弈论剖析加深了我们对抵触和协作的了解”。 2007年，博弈论相关的第三次诺贝尔奖颁给了列昂尼德·赫维奇（Leonid Hurwicz）、埃里克·马斯金（Eric Maskin）和罗杰·迈尔森（ Roger Myerson），以为他们“为机制设计理论奠定了基础”。 最近一次是2012年，阿尔文·罗斯（Alvin Roth）和劳埃德·沙普利（Lloyd Shapley）因“关于稳定分配的理论和市场设计的理论”而获奖。在这个与博弈论贡献相关的最高水平奖的名单中，我还应该参与1999年的克拉福德奖（由瑞典皇家科学院设立的生物科学最高奖项），当年该奖项授予约翰·梅纳德·史密斯（John Maynard Smith），以及恩斯特·迈尔（Ernst Mayr）和G·威廉姆斯 （G. Williams），由于他们“展开了进化生物学的概念”。 其中，经过其在演化博弈论和进化稳定战略/均衡方面的研讨，史密斯这一被公认的贡献有很强的博弈论基础。 固然冯·诺依曼和摩根斯坦1944年的书籍被普遍以为是博弈论科学措施的起点，但博弈论的概念和一些孤立的关键结果却能够追溯到更早，以至是几个世纪前。 16年前，即1928年，约翰·冯·诺依曼自己彻底处置了零和博弈中一个悬而未决的基本问题，即证明了每个有限的两人零和博弈在混合战略下都存在一个鞍点，这就是众所周知的极小极大定理——这是埃米尔·博雷尔（Emile Borel）八年前猜测为错误的结果。 博弈论思索的一些早期痕迹还可见于安德烈·玛丽·安培(Andre-Marie Ampere，1775-1836)1802年的著作《关于数学的思想》，而他则遭到了乔治·路易·布丰(Georges Louis Buffon，1707-1788)1777年著作的影响。 NSR：在此期间，最优控制方面能否有平行展开，对微分博弈论的展开有何影响？ Basar： 事实上，在大约相同的时间范围内，我们看到理查德·贝尔曼（上世纪50年代）在兰德公司工作时引入了动态规划，作为最优控制和更普遍意义上的多阶段决策的主要准绳和工具。 20世纪50年代初期，兰德公司（美国最重要的以军事为主的综合性战略研讨机构）吸收并安置了当时最巨大的一些人物，除了贝尔曼之外，还有伦纳德·贝尔科维奇（Leonard D. Berkovitz）、大卫·布莱克韦尔（David Blackwell）、乔治·丹茨格（George Dantzig）、温德尔·弗莱明（Wendell Fleming）、M.R.海斯滕斯（M.R. Hestenes）、鲁弗斯·伊萨克斯（Rufus Isaacs）、塞缪尔·卡林（Samuel Karlin）、约翰·纳什、J.P.拉萨尔（J.P. LaSalle）和劳埃德·沙普利（Lloyd Shapley）（仅罗列其中几位）。 这些人和其他人奠定了决策论和博弈论的基础，从而为控制研讨添加了动力。 在这种共同的、十分有益的环境中，贝尔曼早在1949年就开端了多阶段决策过程的研讨，但更充沛的（研讨）是在1952年之后—— 一个或许不为人知的历史事实是，贝尔曼在兰德工作时的早期主题之一就是博弈论（零和与非零和博弈），他与布莱克韦尔、拉萨尔共同撰写了研讨讲演。 32年后贝尔曼写了一本内容翔实且有趣的自传（《飓风眼》，Eye of the Hurricane，世界科学出版社，新加坡），在1984年3月19日他英年早逝前不久完成的这本书中，贝尔曼洋洋洒洒地描画了兰德公司的研讨环境和他发明“动态规划”这个术语的缘由。 动态规划在不同类型问题中的应用，以及“动态规划函数方程”的取得，促使贝尔曼随后提出“最优性原理”作为一个统一的准绳。这一准绳由简直同时同样供职于兰德公司的伊萨克斯在微分博弈的更宽广背景下，将其称为“变更准绳”，这一称谓抓住了对立环境下战略性动态决策特性。 事实上，伊萨克斯被以为是在零和框架下竞争性连续时间动态决策中发明了“微分博弈”一词的人，也有人把最优性原理归功于他，由于它能够看作是变更准绳的一个惯例。由于工作的秘密性，多年来伊萨克斯不时未能在公开文献中发布他的发现(贝尔曼则能够)，直到1965年其书籍《微分博弈》（Differential Games）的出版。 该书惹起了研讨兴味的跃迁，首先是追逃博弈（更普遍地，零和微分博弈)，后来是上世纪70年代初的非零和微分博弈，由哈佛大学的何毓琦及其协作者领头。 博弈论研讨的应战 NSR：您能谈谈目前博弈论，特别是在动态博弈方面的主要研讨范畴，以及主要的应战是什么吗？ Basar： 我谈几个方面，但绝非完好和详尽。像我之前简单说过的，信息结构在动态博弈的非协作均衡表征和计算中所起的作用是目前一个生动的研讨范畴，由于其中仍有许多复杂的要素尚未完整得到了解。 这些都与均衡对决策过程中博弈者所取得信息类型的相关性有关系：谁与谁交流、一个博弈者的行动怎样从质量和数量上影响其他博弈者接纳到的与其决策相关的信息。 显然，这些问题在单一决策者状况下都不会呈现。还有不同参与者的理性问题——有意或无意的理性缺失，即便他们在某种水平上是理性的，其理性的“边疆”是什么（可能是由于对资源如计算才干或感知才干的约束所招致的限制构成），以及这一切如何影响均衡。还有一个问题是均衡对未被建模的不肯定性以及对立性干预（如加在通讯链路上的）的鲁棒性。 之前我提到过鲁棒(H-∞)最优控制胜利地与零和微分博弈相联络，这对其他学科也有影响，并为与非零和动态博弈树立相似的联络提供了相当丰厚的途径。 另一个内容丰厚的研讨范畴是网络博弈。 广义上，这里的背景是存在一个底层的网络或图形结构，可能是多层的，约束着参与者之间的交互：由邻居关系决议谁与谁交流，谁与谁协作，以及哪些参与者的目的或动态是相互耦合的。 另一个高产的研讨范畴是平均场博弈，触及到另一种结构特异性，其中参与者的互动不是与其他个体参与者中止，而是与无限数量的参与者对应的整体中止，单个成员的行为对群体的整体行为只需极小的影响。这是我自己目前感兴味的一个方向。 最后，当前一个日益增长的研讨范畴触及到将机器学习，特别是强化学习工具引入博弈论，以处置“无模型”的多智能体决策问题，其中参与者并没有其他参与者的变更规律或目的函数信息——而其他参与者的行为会影响他们的表示，但会将自己经过察看所得的数据，好比在决策过程中取得的“奖励”，整合到自己的行为生成算法中。 早在2018年1月，NSR就有一个关于“机器学习”的专题（第1期第5卷），我看到了将其中的框架和工具扩展到博弈论框架下多智能体系统研讨的庞大潜力。这也是我目前感兴味的范畴之一。 如何为博弈论的研讨做好准备 NSR：关于这一范畴的新入门者，如研讨生，您有何倡议？在深化研讨博弈论，特别是动态博弈之前，他们应该具备什么背景? Basar： 首先，强大的数学背景，特别是实剖析，是必须的。其次，深化控制（肯定性的、随机的，以及最优的）控制论学问是必不可少的，然后才干面对从单一到多个决策者所产生的复杂问题。 当然，作为其中的一部分，还需求扎实的概率、随机过程、最优化等学问，以及博弈论方面的一些入门学问也是需求的。 最后，依据要中止的研讨所触及的细致应用范畴，一些范畴的学问也必不可少。当然，更不用说一个研讨范畴的新入门者还应该熟习该范畴已完成的研讨成果以及目前的相关文献。 结语 NSR：十分感激您参与这次NSR专题的采访，感激您对这个新兴范畴的深化评论和瞻望。 Basar： 谢谢您给我这个共同的机遇。我知道中国对这一范畴有浓厚的兴味，我看到中国研讨人员的参与度越来越高，对当前的展开有很大的影响。 （作者系中国科学院数学与系统科学研讨院研讨员，感激纽约大学坦登工程学院电气和计算机工程专业副教授Quanyan Zhu、中国科学院数学与系统科学研讨院副研讨员穆义芬审校。） 本文来源：张纪峰、冯维维 转载本文请联络原作者获取受权，同时请注明本文来源。 |
名表回收网手机版
