Computing Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games
Computing Team-Maxmin Equilibria in Zero-Sum Multiplayer Extensive-Form Games
复制标题
零和多人扩展型博弈中的计算团队最大最小均衡
DOI：
10.1609/aaai.v34i02.5610
复制
发表时间：
2020
期刊：
影响因子：
2.4
通讯作者：
Bo An
中科院分区：
文献类型：
--
作者：
Y. Zhang;Bo An
寻找多人游戏平衡的研究具有挑战性。本文重点介绍了零和多人游戏大型游戏（EFGS）中计算团队最大平衡（TMES），该游戏描述了共享相同目标但他们独立采取行动对抗对手的球员团队的最佳策略。 TME可以捕获许多现实的场景，包括：1）一组球员在扑克游戏中与目标玩家对抗； 2）国防资源计划和在安全游戏中独立巡逻。但是，在EFG中任何给定的准确性中有效查找TME的研究几乎完全没有探索。为了填补这一空白，我们首先研究了计算平衡引起的效率低下，在这种平衡中，团队参与者将其策略相关联，然后将其转换为团队的混合策略概况，并表明这种效率低下可能是任意的。其次，为了有效地求解直接查找TME的非convex程序，我们开发了相关的递归异步多参数分解技术（ARAMDT），以使用两种新技术中的程序中的多线性术语近似：1）通过使用不同的精度级别近似这些术语来近似的约束和变量； 2）一种相关的约束方法，是通过利用这些术语之间的关系来减少由ARAMDT产生的混合构成线性程序的可行解决方案空间。第三，我们开发了一种新型的迭代算法，以在基于ARAMDT的任何给定精度内有效计算TME。在实验评估中，我们的算法是比基线快的数量级。
The study of finding the equilibrium for multiplayer games is challenging. This paper focuses on computing Team-Maxmin Equilibria (TMEs) in zero-sum multiplayer Extensive-Form Games (EFGs), which describes the optimal strategies for a team of players who share the same goal but they take actions independently against an adversary. TMEs can capture many realistic scenarios, including: 1) a team of players play against a target player in poker games; and 2) defense resources schedule and patrol independently in security games. However, the study of efficiently finding TMEs within any given accuracy in EFGs is almost completely unexplored. To fill this gap, we first study the inefficiency caused by computing the equilibrium where team players correlate their strategies and then transforming it into the mixed strategy profile of the team and show that this inefficiency can be arbitrarily large. Second, to efficiently solve the non-convex program for finding TMEs directly, we develop the Associated Recursive Asynchronous Multiparametric Disaggregation Technique (ARAMDT) to approximate multilinear terms in the program with two novel techniques: 1) an asynchronous precision method to reduce the number of constraints and variables for approximation by using different precision levels to approximate these terms; and 2) an associated constraint method to reduce the feasible solution space of the mixed-integer linear program resulting from ARAMDT by exploiting the relation between these terms. Third, we develop a novel iterative algorithm to efficiently compute TMEs within any given accuracy based on ARAMDT. Our algorithm is orders of magnitude faster than baselines in the experimental evaluation.
影响因子：
56.9
作者：
Brown, Noam;Sandholm, Tuomas
通讯作者：
Sandholm, Tuomas