AAAI 2021 | 稀疏胜负多智能体博弈中的纳什均衡解计算
关键词：算法博弈论，计算复杂性
导 读
本文是第三十五届人工智能大会（AAAI 2021）入选论文《On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games》的解读。
Polymatrix Game 是一类重要的多人博弈模型。这一模型最主要的特点是能拆成多对双人博弈，如下图所示。每人的收益为所有他参与的二人博弈的收益和。另外值得强调的一点是每人在所有的二人博弈中都只能使用同一个策略。整个游戏可以用一个 的收益矩阵表示下来。
本文研究了纳什均衡计算在一类非常特殊的 Polymatrix Game 下的计算复杂度。我们定义了 -Sparse Win-Lose Polymatrix Game (SWLP)，其中：
-Sparse 表示收益矩阵每行最多有 个非零元素，每列最多有 个非零元素；
Win-Lose 表示收益矩阵每个元素为 0 或 1。
本文的主要结论为：
求解 -SWLP 的多项式近似纳什均衡点是 PPAD-Complete 的；
给出了求解 -SWLP 或 -SWLP 的精确纳什均衡解的高效（多项式）算法。
本文的主要结论通过改进前人证明框架得到，由于需要较多预备知识，请感兴趣的读者阅读原论文。
本文的主要贡献在于：
证明了即使在极度简化的多人博弈下，纳什均衡解计算仍然是困难的。这进一步质疑了纳什均衡解在多人情境下的预测能力；该结论对于基于纳什均衡解的多智能体增强学习（MARL）算法有引导作用；
SWLP game 可以作为证明其他问题 PPAD-hard 结果的有用的规约起点。
最后，一个重要的尚未解决的问题是 constant sparse win-lose bimatrix game 的纳什均衡解计算复杂度。这一问题目前的最优结果由 Zhengyang Liu 与 Ying Sheng 在2018年得到，他们证明了 logarithmic sparse win-lose bimatrix game 的纳什均衡解是 PPAD-Complete 的。然而，得到更强的常数稀疏可能需要新的证明技巧。
图文 | Jiawei Li
Distributed and Automated Games and Managerial Economics (daGAME)
AAAI
AAAI（AAAI Conference on Artificial Intelligence）是人工智能领域的国际顶级会议，早期由计算机科学和人工智能创始人 Allen Newell, Marvin Minsky 和 John McCarthy 等人首创，被中国计算机学会（CCF）推荐为A类会议。第35届AAAI（AAAI-21）将于2021年2月2日-9日在线举行。
算法博弈论实验室
Distributed and Automated Games and Managerial Economics Lab
算法博弈论实验室由邓小铁教授于2019年创立，研究方向为算法博弈论、互联网和区块链经济学、多智能体及强化深度学习理论。科研兴趣聚焦在人和智能体在互联网、物联网和区块链交互环境下多方博弈的理论与方法论建立，包括数据信息的认识论刻画、均衡和动力学分析、计算复杂性和算法设计。对在计算与通讯技术兴起中应用领域问题特别关注互联网广告机制设计，共享经济中的激励分析和合作竞争，以及区块链的高效共识、声誉机制和跨链机制设计。
近期科研动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点击“阅读原文”跳转论文