科学家解决了将近 60 年的博弈论难题
博弈论是数学的一个分支，研究个人或群体之间的决策制定和战略互动。 它用于分析参与者必须做出影响游戏或情况结果的选择的情况。 博弈论提供了一个框架，用于理解个人或团体如何在考虑他人的行为和反应的情况下做出决策。 它被用于经济学、政治学、心理学和生物学等各个领域，以分析现实世界的场景，包括谈判、拍卖、市场竞争，甚至军事战略。 通过了解每个参与者的动机、激励和约束，博弈论有助于预测一种情况下最有可能的结果。
为了理解自动驾驶汽车在复杂道路上行驶的能力，科学家们经常求助于博弈论——数学的一个分支，致力于对代理人努力实现目标时的理性行为进行建模。
多年来，加州大学圣克鲁斯分校电气和计算机工程教授德扬·米卢蒂诺维奇 (Dejan Milutinovic) 一直与其他研究人员合作研究博弈论的复杂子集，即微分博弈。 这个领域与运动中的球员有关。 这些游戏中有追墙游戏，它提供了一个相对简单的框架，适用于速度较快的追逐者旨在捕获速度较慢且只能沿墙移动的逃避者的场景。
自从近 60 年前首次描述这个游戏以来，游戏中一直存在一个困境——一组被认为不存在游戏最优解的位置。 但现在，米卢蒂诺维奇和他的同事们在该杂志发表的一篇新论文中证明了 IEEE 自动控制汇刊 这个长期存在的困境实际上并不存在，并引入了一种新的分析方法，证明追墙游戏总有一个确定性的解决方案。 这一发现为解决微分博弈领域中存在的其他类似挑战打开了大门，并能够更好地推理无人驾驶汽车等自主系统。
博弈论用于推理广泛领域的行为，例如经济学、政治学、计算机科学和工程学。 在博弈论中，纳什均衡是最普遍认可的概念之一。 这个概念是由数学家约翰纳什提出的，它定义了游戏中所有玩家以最少的遗憾完成游戏的游戏最优策略。 任何选择不执行他们博弈最优策略的玩家最终都会有更多的遗憾，因此，理性的玩家都有动力去执行他们的均衡策略。
这个概念适用于追墙游戏——追逐者和逃避者这两个玩家的经典纳什均衡策略对，描述了他们在几乎所有位置上的最佳策略。 然而，在追击者和逃避者之间存在一组位置，经典分析无法得出博弈最优策略，并得出两难困境存在的结论。 这组位置被称为奇异曲面——多年来，研究界已经接受了这一困境作为事实。
但米卢蒂诺维奇和他的合著者不愿意接受这一点。
Milutinovic 说：“这让我们感到困扰，因为我们认为，如果逃避者知道有一个单一的表面，那么逃避者就有可能进入单一表面并滥用它。” “逃避者会迫使你去到一个你不知道如何采取最佳行动的奇异表面——然后我们就不知道在更复杂的游戏中这意味着什么。”
因此，米卢蒂诺维奇和他的合著者提出了一种解决该问题的新方法，使用了最初构思追墙游戏时不存在的数学概念。 通过使用 Hamilton-Jacobi-Isaacs 方程的粘性解并引入损失率分析来求解奇异曲面，他们能够发现可以在博弈的所有情况下确定博弈最优解并解决困境。
偏微分方程的粘度解是一个直到 1980 年代才存在的数学概念，它提供了关于 Hamilton-Jacobi-Isaacs 方程解的独特推理路线。 现在众所周知，这个概念与最优控制和博弈论问题的推理有关。
使用作为函数的粘性解来解决博弈论问题涉及使用微积分来找到这些函数的导数。 当与游戏相关的粘度解具有明确定义的导数时，找到游戏最优解相对容易。 追墙游戏的情况并非如此，缺乏明确定义的衍生品造成了困境。
通常当存在困境时，一种实用的方法是玩家随机选择一种可能的行动并接受这些决定造成的损失。 但这里有一个陷阱：如果有损失，每个理性的玩家都会希望将损失降到最低。
因此，为了找到玩家如何最大限度地减少损失，作者分析了 Hamilton-Jacobi-Isaacs 方程在导数未明确定义的奇异曲面周围的粘性解。 然后，他们对方程的这些奇异表面状态引入了损失率分析。 他们发现，当每个参与者将其损失率降至最低时，他们在奇异表面上的行动就有明确的博弈策略。
作者发现，这种损失率最小化不仅定义了奇异表面的游戏最优动作，而且还与经典分析也能够找到这些动作的每种可能状态下的游戏最优动作一致。
“当我们采用损失率分析并将其应用于其他地方时，经典分析中的游戏最佳行动不会受到影响，”米卢蒂诺维奇说。 “我们采用经典理论，并通过损失率分析对其进行扩充，因此解决方案无处不在。 这是一个重要的结果，表明增强不仅是在奇异曲面上找到解决方案的方法，而且是对博弈论的基本贡献。
Milutinovic 和他的合著者有兴趣探索可以应用他们的新方法的奇异曲面的其他博弈论问题。 该论文还公开呼吁研究界对其他困境进行类似的研究。
“现在的问题是，我们还能解决什么样的其他困境？” 米卢蒂诺维奇说。
参考：Dejan Milutinović、David W. Casbeer、Alexander Von Moll、Meir Pachter 和 Eloy Garcia 撰写的“解决追墙游戏解决方案困境的损失率表征”，2023 年 1 月， IEEE 自动控制汇刊.
DOI：10.1109/TAC.2021.3137786