AAAI 2021 | 稀疏胜负多智能体博弈中的纳什均衡解计算

Polymatrix Game 是一类重要的多人博弈模型。本文的主要贡献在于：

证明了即使在极度简化的多人博弈下，纳什均衡解计算仍然是困难的。这进一步质疑了纳什均衡解在多人情境下的预测能力；该结论对于基于纳什均衡解的多智能体增强学习（MARL）算法有引导作用；

SWLP game 可以作为证明其他问题 PPAD-hard 结果的有用的规约起点。