多智能体影响图 (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 节)。