论文标题
团队信念DAG：将序列形式概括为团队游戏，以快速计算相关的团队最高均衡，而遗憾最小化
Team Belief DAG: Generalizing the Sequence Form to Team Games for Fast Computation of Correlated Team Max-Min Equilibria via Regret Minimization
论文作者
论文摘要
广泛的游戏理论的一个经典结果断言，任何完美的唱片玩家可用的策略集在战略上等同于低维凸多角形，称为序列形式多层。在此多层上运行的在线凸优化工具是计算游戏中几个均衡概念的当前最新技术，并且在计算游戏理论的具有里程碑意义的应用中至关重要。但是，当优化一组球员的联合策略空间时，人们无法使用序列形式来获得对团队策略集的战略性等效凸描述。在本文中，我们为团队的最佳策略计算提供了新的复杂性结果，并提出了新的代表，即创建的团队信念DAG（TB-DAG），将团队策略描述为凸面集。 TB-DAG享有最先进的参数复杂性界限，同时享受有效的遗憾最小化技术的优势。我们表明，TB-DAG可以呈指数级，并且可以比所有其他已知表示形式更快地计算成指数的计算，并且相反从来都不是正确的。在实验上，我们表明，与学习技巧配对时，结核销钉可以在各种基准团队游戏中产生最新技术。
A classic result in the theory of extensive-form games asserts that the set of strategies available to any perfect-recall player is strategically equivalent to a low-dimensional convex polytope, called the sequence-form polytope. Online convex optimization tools operating on this polytope are the current state-of-the-art for computing several notions of equilibria in games, and have been crucial in landmark applications of computational game theory. However, when optimizing over the joint strategy space of a team of players, one cannot use the sequence form to obtain a strategically-equivalent convex description of the strategy set of the team. In this paper, we provide new complexity results on the computation of optimal strategies for teams, and propose a new representation, coined team belief DAG (TB-DAG), that describes team strategies as a convex set. The TB-DAG enjoys state-of-the-art parameterized complexity bounds, while at the same time enjoying the advantages of efficient regret minimization techniques. We show that TB-DAG can be exponentially smaller and can be computed exponentially faster than all other known representations, and that the converse is never true. Experimentally, we show that the TB-DAG, when paired with learning techniques, yields state of the art on a wide variety of benchmark team games.
