牛津大学《多智能体影响图的均衡优化: 理论和实践》，Equilibrium Refinements for Multi-Agent Influence Diagrams: Theory and Practice

摘要

多智能体影响图 (MAID) 是一种流行的图形模型形式，对于某些类别的博弈，与传统的扩展形式博弈 (EFG) 表示相比，它已被证明具有关键的复杂性和可解释性优势。在本文中，我们扩展了先前关于 MAID 的工作，通过引入 MAID 子博弈的概念，以及子博弈完美和颤抖手完美均衡进行改进。然后，我们证明了 MAID 和 EFG 之间的几个等价结果。最后，我们描述了一个用于推理 MAID 和计算它们的均衡的开源实现。

引言

多智能体影响图 (MAID) 是非合作博弈的紧凑且富有表现力的图形表示。由 Koller 和 Milch（以下称为 K&M）[14, 19] 介绍，与经典的广泛形式博弈 (EFG) 表示相比，它们提供了三个关键优势。首先，MAID 可以比 EFG 更简洁地描述许多博弈，尤其是那些信息不完整的博弈。其次，MAID 对变量之间的条件独立性进行编码。这意味着大型 MAID 通常可以分解为几个较小的 MAID，从而可能会以指数级速度加速寻找纳什均衡 [14]。第三，MAID 通常可以明确表示在 EFG 中模糊的博弈结构方面。虽然可以将任何 EFG 转换为最多相同大小的 MAID（第 3.3.2 节），但确实 EFG 有时更适合建模非对称决策问题。话虽如此，每个模型都有其弱点，特定表示的有用程度取决于其优势。我们进一步开发了 MAID 的理论和实践工具，以使研究人员和从业人员都能充分发挥他们的优势。

以前关于 MAID 的工作集中在纳什均衡作为核心解决方案概念 [20]。虽然这可以说是非合作博弈论中最重要的解决方案概念，但如果有许多纳什均衡，我们通常希望删除一些不太“理性”的。已经提出了对纳什均衡的许多改进[17]，其中最重要的两个是子博弈完美纳什均衡[26]和颤抖手完美均衡[27]。第一个排除“不可信”的威胁，第二个要求每个玩家在其他玩家犯小错误时仍然在做出最佳反应。在实际方面，虽然有很多软件用于普通或扩展形式的博弈，但没有这样的实现来推理表示为 MAID 的博弈，尽管它们具有计算优势。

贡献

在本文中，我们做出以下贡献。首先，我们通过引入 MAID 子博弈的概念（第 3.1 节）来扩展 MAID 的适用性，并在此概念的基础上引入子博弈完美和颤抖手完美平衡改进（第 3.2 节）。其次，我们证明了 MAID 和 EFG 之间的几个等价结果，证明了在将 EFG 表示为 MAID 时保留了上述关键博弈论概念，从而进一步证明了使用该模型的合理性。这些证明是建设性的，并且基于 EFG 和 MAID 之间的转换程序，其全部细节包含在附录 A.1 和 A.2 中。第三，我们报告了我们的开源代码库，用于计算我们在 MAID 中的平衡改进（第 4 节）。