研究人员解决了近60年的博弈论困境

诸平

Credit: Pixabay/CC0 Public Domain

据美国加州大学圣克鲁斯分校（University of California - Santa Cruz）2023年3月14日提供的消息，美国加州大学圣克鲁斯分校（University of California, Santa Cruz, CA, USA）的研究人员与美国赖特-帕特森空军基地空军研究实验室（Air Force Research Laboratory, Wright-Patterson Air Force Base, OH, USA）、美国赖特-帕特森空军基地空军理工学院（Air Force Institute of Technology, Wright-Patterson Air Force Base, OH, USA）研究人员合作，解决了近60年的博弈论困境（Researcher solves nearly 60-year-old game theory dilemma）。相关研究结果于2021年12月23日已经在《IEEE自动控制汇刊》(IEEE Transactions on Automatic Control)杂志网站发表(印刷版出版时间为2023年元月份)——Dejan Milutinović; David W. Casbeer; Alexander Von Moll; Meir Pachter; Eloy Garcia. Rate of Loss Characterization That Resolves the Dilemma of the Wall Pursuit Game Solution. IEEE Transactions on Automatic Control, January 2023, 68(1): 242 – 256. DOI: 10.1109/TAC.2021.3137786. Date of Publication: 23 December 2021.

为了理解无人驾驶汽车如何在复杂的道路上行驶，研究人员经常使用博弈论数学模型，来代表理性的行为主体在战略上实现目标的方式。

上述论文的第一作者德扬·米卢蒂诺维奇（Dejan Milutinovic）是加州大学圣克鲁兹分校电子与计算机工程学教授，长期以来，他与同事们一起研究博弈论（game theory）的复杂子集——微分博弈（differential games），这与运动中的游戏玩家（game players）有关。其中一种游戏被称为追墙游戏（wall pursuit game），这是一种相对简单的模式，在这种情况下，速度较快的追逐者有目标抓住速度较慢的逃避者，后者被限制在沿墙移动。

自从这个游戏在近60年前首次被描述以来，游戏中一直存在一个困境——一组被认为不存在游戏最优解的位置。但现在，德扬·米卢蒂诺维奇和他的同事在《IEEE自动控制汇刊》(IEEE Transactions on Automatic Control)上发表的一篇新论文中证明了这个长期存在的困境实际上并不存在，并引入了一种新的分析方法，证明了墙追游戏总是有确定性的解决方案。这一发现为解决微分游戏领域中存在的其他类似挑战打开了大门，并使人们能够更好地推理无人驾驶汽车等自主动系统。

博弈论被用于对广泛领域的行为进行推理，如经济学、政治学、计算机科学和工程学。在博弈论中，纳什均衡（Nash equilibrium）是最普遍认可的概念之一。这个概念是由数学家约翰·纳什（John Nash）提出的，它定义了博弈中所有参与者以最少的遗憾完成博弈的博弈最优策略（optimal strategy）。任何不选择最优策略的参与者都会后悔，因此，理性的参与者都有动力选择均衡策略。

这个概念适用于追墙游戏两个参与人，即追击者和逃避者的经典纳什均衡策略对（Nash equilibrium strategy pair），描述了他们在几乎所有位置上的最佳策略。但是，在追赶者和逃避者之间存在着一系列的位置，经典的分析并没有得出最优的博弈策略，从而得出了困境的存在。这组位置被称为奇异曲面（singular surface），多年来，研究界已经将这一困境作为事实接受。但是德扬·米卢蒂诺维奇和他的合著者不愿意接受这一点。

德扬·米卢蒂诺维奇说:“这让我们感到困扰，因为我们认为，如果逃避者知道有一个奇异曲面，就有可能去到此奇异曲面并滥用它。逃避者可以迫使你进入一个你不知道如何最佳行动的奇异曲面，然后我们就不知道这在更复杂的游戏中意味着什么。”

因此，德扬·米卢蒂诺维奇和他的合著者想出了一种新的方法来解决这个问题，他们使用了一种在最初构思追墙游戏时还不存在的数学概念。通过使用汉密尔顿·雅可比·艾萨克斯方程（Hamilton–Jacobi–Isaacs equation）的粘度解（viscosity solution），并引入求解奇异曲面的损失率分析，他们能够发现在游戏的所有情况下都可以确定游戏的最优解，从而解决了困境问题。

偏微分方程的粘度解是20世纪80年代才出现的一个数学概念，并提供了一个关于汉密尔顿-雅可比-艾萨克斯方程解的独特推理路线。众所周知，这个概念与最优控制和博弈论问题的推理有关。

使用粘度解，也就是函数，来解决博弈论问题，包括用微积分来求这些函数的导数。当与游戏相关的粘度解具有定义良好的导数时，找到游戏最优解相对容易。但在逐墙的游戏中，情况并非如此，缺乏定义明确的导数造成了困境。

通常，当困境存在时，一种实际的方法（practical approach）是玩家随机选择一种可能的行动，并接受由这些决定造成的损失。但这里存在一个问题:如果出现了损失，每个理性的玩家都会希望使损失最小化。

因此，为了找出玩家如何将损失最小化，作者分析了汉密尔顿-雅可比-艾萨克斯方程在导数未明确定义的奇异曲面周围的粘度解。然后，他们在方程的奇异曲面态上引入了损失率分析。他们发现，当每个参与者将自己的损失率降到最低时，他们在奇异曲面上的行动就有明确的博弈策略。

作者发现，这种损失最小化率不仅定义了奇异曲面的博弈最优行动，而且它也与经典分析也能够找到这些行动的每种可能状态下的博弈最优行动相一致。

德扬·米卢蒂诺维奇说:“当我们把损失率分析应用到其他地方时，经典分析中的游戏优化操作不会受到影响。我们采用经典理论，并将其与损失率分析相结合，因此解决方案无处不在。这是一个重要的结果，表明增强不仅仅是在奇曲面上找到解的固定，而是对博弈论的基本贡献。”

德扬·米卢蒂诺维奇和他的合著者对探索奇异曲面的其他博弈论问题感兴趣，在那里他们的新方法可以应用。这篇论文也是对研究界的一个公开呼吁，以类似的方式研究其他困境。

“现在的问题是，我们还能解决什么样的困境?”德扬·米卢蒂诺维奇说。

上述介绍，仅供参考。欲了解更多信息，敬请注意浏览原文或者相关报道。

Abstract:

The scope of this article is the well-known wall pursuit game, which has been used in the literature to illustrate the existence of a singular surface (dispersal line) and the associated game dilemma. We derive an analytical expression for the value function of the game, which is the viscosity solution of the Hamilton–Jacobi–Isaacs equation. Then, we introduce a hold time analysis and the rate of change for the loss of time to capture along the dispersal line, and show that the rate has a well-defined saddle point along the dispersal line, which can be used to resolve the dilemma. Moreover, we prove that the saddle point of the rate characterizes optimal game actions not only on the dispersal line, but also for all other states of the game. Finally, we analyze the same game in a version with a nonzero hold time and show that in that case, the actions from the dispersal line have to be applied both on the dispersal line and in a narrow band around it. To illustrate that, we use an example to compute the band around the line.