美国工程院院士深度解析：博弈论与控制面临哪些挑战和机遇？|美国

　　作者 | 张纪峰

　　翻译 | 冯维维

　　近年来，博弈论相关的概念和工具在控制、多智能体系统和网络研究中的应用几乎呈指数增长。

　　在接受《国家科学评论》（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、中国科学院数学与系统科学研究院副研究员穆义芬审校。）