研究人员解决了将近60年的博弈论难题

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

DejanMilutinovic是加州大学圣克鲁兹分校的电气和计算机工程教授，长期以来一直与同事合作研究称为微分游戏的复杂博弈论子集，这与运动中的游戏玩家有关。其中一个游戏称为追墙游戏，这是一种相对简单的模型，适用于速度较快的追逐者的目标是追赶速度较慢且只能沿墙移动的逃避者的情况。

自从近60年前首次描述这个游戏以来，游戏中一直存在一个困境——一组被认为不存在游戏最优解的位置。但现在，Milutinovic和他的同事在IEEETransactionsonAutomaticControl期刊上发表的一篇新论文中证明，这个长期存在的困境实际上并不存在，并引入了一种新的分析方法，证明总有一个确定性的解决方案追墙游戏。这一发现为解决微分博弈领域中存在的其他类似挑战打开了大门，并能够更好地推理无人驾驶汽车等自主系统。

博弈论用于推理广泛领域的行为，例如经济学、政治学、计算机科学和工程学。在博弈论中，纳什均衡是最普遍认可的概念之一。这个概念是由数学家约翰纳什提出的，它定义了游戏中所有玩家以最少的遗憾完成游戏的游戏最优策略。任何选择不执行他们博弈最优策略的玩家最终都会有更多的遗憾，因此，理性的玩家都有动力去执行他们的均衡策略。

这个概念适用于追墙博弈——追逐者和逃避者这两个玩家的经典纳什均衡策略对，描述了他们在几乎所有位置上的最佳策略。然而，在追击者和逃避者之间存在一组位置，经典分析无法得出博弈最优策略，并得出两难困境存在的结论。这组位置被称为奇异曲面——多年来，研究界已经接受了这一困境作为事实。

但米卢蒂诺维奇和他的合著者不愿意接受这一点。

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

因此，米卢蒂诺维奇和他的合著者想出了一种解决这个问题的新方法，使用了最初构思追墙游戏时不存在的数学概念。通过使用Hamilton-Jacobi-Isaacs方程的粘性解并引入损失率分析来求解奇异曲面，他们能够发现可以在博弈的所有情况下确定博弈最优解并解决困境。

偏微分方程的粘度解是一个直到1980年代才存在的数学概念，它提供了关于Hamilton-Jacobi-Isaacs方程解的独特推理路线。现在众所周知，这个概念与最优控制和博弈论问题的推理有关。

使用作为函数的粘性解来解决博弈论问题涉及使用微积分来找到这些函数的导数。当与游戏相关的粘度解具有明确定义的导数时，找到游戏最优解相对容易。追墙游戏的情况并非如此，缺乏明确定义的衍生品造成了困境。

通常当存在困境时，一种实用的方法是玩家随机选择一种可能的行动并接受这些决定造成的损失。但这里有一个陷阱：如果有损失，每个理性的玩家都会希望将损失降到最低。

因此，为了找到玩家如何最大限度地减少损失，作者分析了Hamilton-Jacobi-Isaacs方程在导数未明确定义的奇异曲面周围的粘性解。然后，他们对方程的这些奇异表面状态引入了损失率分析。他们发现，当每个参与者将其损失率降至最低时，他们在奇异表面上的行动就有明确的博弈策略。

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

“当我们采用损失率分析并将其应用于其他地方时，经典分析中的游戏最佳行动不会受到影响，”米卢蒂诺维奇说。“我们采用经典理论，并通过损失率分析对其进行扩充，因此到处都存在解决方案。这是一个重要的结果，表明扩充不仅是在奇异曲面上找到解决方案的方法，而且是一项基本贡献到博弈论。

Milutinovic和他的合著者有兴趣探索可以应用他们的新方法的奇异曲面的其他博弈论问题。该论文还公开呼吁研究界对其他困境进行类似的研究。

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