研究者解决近60年的博弈论困境

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

加州大学圣克鲁斯分校(UC Santa Cruz)电气和计算机工程教授德扬·米卢蒂诺维奇(Dejan Milutinovic)长期以来一直与同事合作研究博弈论的复杂子集，称为微分博弈，这与运动中的博弈玩家有关。其中一个游戏被称为墙壁追逐游戏，这是一种相对简单的模型，其中更快的追逐者的目标是抓住一个被限制在沿着墙壁移动的较慢的逃避者。

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

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

这个概念适用于墙追逐博弈——一个经典的纳什均衡策略对，由追击者和躲避者两个玩家组成，它描述了他们在几乎所有位置上的最佳策略。然而，在追逐者和逃避者之间有一组位置，经典分析未能产生游戏最优策略，并以困境的存在而告终。这组立场被称为单一表面 - 多年来，研究界已经接受了这个困境的事实。

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

“这让我们感到困扰，因为我们认为，如果逃避者知道有一个单一的表面，那么逃避者可能会去奇异表面并滥用它，”米卢蒂诺维奇说。“逃避者可以强迫你去奇异的表面，在那里你不知道如何以最佳方式行事 - 然后我们只是不知道这在更复杂的游戏中意味着什么。

因此，Milutinovic和他的合著者提出了一种新的方法来解决这个问题，使用了一个数学概念，这个概念在最初构思墙壁追踪游戏时并不存在。通过使用汉密尔顿-雅可比-艾萨克斯方程的粘度解，并引入用于求解奇异表面的损失率分析，他们能够发现可以在游戏的所有情况下确定游戏最优解并解决困境。

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

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

通常，当存在困境时，一种实用的方法是玩家随机选择一种可能的行动并接受这些决定造成的损失。但这里有一个问题：如果有损失，每个理性的参与者都希望将其最小化。

因此，为了找到玩家如何最大限度地减少损失，作者分析了汉密尔顿-雅可比-艾萨克斯方程围绕导数未明确定义的奇异表面的粘度解。然后，他们在方程的这些奇异表面状态中引入了损失率分析。他们发现，当每个参与者将其损失率最小化时，他们在奇异表面上的行为就有明确的游戏策略。

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

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

Milutinovic和他的合著者有兴趣探索其他具有奇异表面的博弈论问题，在那里他们的新方法可以应用。这篇论文也是对研究界的公开呼吁，以同样的方式研究其他困境。