Imperfect-Recall Games: Equilibrium Concepts and Their Complexity

我们研究了在信息不完全回忆的情况下的最优决策制定，也就是说，当一个代理人忘记了它曾经拥有的信息时。一个例子是健忘的司机游戏，以及团队游戏中成员之间通信能力有限的情况。在具有不完全回忆的广义博弈框架下，我们分析了在多人设置中寻找均衡的计算复杂性，涉及三种不同的解决方案概念：纳什，基于证据决策理论（EDT）的多自体和基于因果决策理论（CDT）的多自体。我们对精确和近似解决方案的计算都感兴趣。作为特殊情况，我们考虑了（1）单人游戏，（2）两人零和游戏和最大最小值之间的关系，以及（3）没有外生随机性（机会节点）的游戏。我们将这些问题与复杂度类P、PPAD、PLS、$\Sigma_2^P$、$\exists$R和$\exists \forall$R相关联。

本论文旨在研究在不完全回忆情况下的最优决策问题，特别是多人游戏中的均衡解的计算复杂性，以及与计算复杂性相关的问题。

本论文提出了三种解决方案：Nash、基于证据决策理论（EDT）的多自身、基于因果决策理论（CDT）的多自身，并研究了精确和近似解的计算复杂性。此外，本论文还探讨了单人游戏、两人零和游戏以及没有外生随机性（机会节点）的游戏的特殊情况。

本论文的实验设计是值得关注的亮点，同时还使用了多个数据集。本论文的研究成果对于解决多人游戏中的最优决策问题具有重要的理论意义，并且为相关领域的研究提供了新的思路。

与本论文相关的研究还包括：《A survey of bounded rationality》、《Imperfect recall》、《Computational complexity of Nash equilibria in extensive-form games》等。