From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics
From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics
复制标题
从混沌到有序：博弈动力学中的对称性和守恒定律
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
G. Piliouras
中科院分区：
文献类型：
--
作者：
Sai Ganesh Nagarajan;D. Balduzzi;G. Piliouras
游戏是训练和测试学习算法的一个越来越有用的工具。最近的例子包括GANs、AlphaZero和AlphaStar联赛。然而，多智能体学习非常难以预测和控制。即使是在简单的游戏中学习动态也会产生混乱的行为。本文提出了构建具有可预测和可控动力学的博弈的基本机制设计工具。我们展示了任意大型和复杂的网络游戏，编码合作（团队游戏）和竞争（零和互动），当代理使用被称为跟随规则化领导者的标准后悔最小化动态时，表现出守恒定律。当不同的代理使用不同的动态和编码代理行为之间的长期相关性时，即使代理可能不直接交互，这些定律仍然存在。此外，我们还提供了动力学具有多个线性无关守恒律的充分条件。增加守恒定律的数量导致更可预测的动力学，最终使混沌行为在某些情况下在形式上不可能。
Games are an increasingly useful tool for training and testing learning algorithms. Recent examples include GANs, AlphaZero and the AlphaStar league. However, multi-agent learning can be extremely difficult to predict and control. Learning dynamics even in simple games can yield chaotic behavior. In this paper, we present basic mechanism design tools for constructing games with predictable and controllable dynamics. We show that arbitrarily large and complex network games, encoding both cooperation (team play) and competition (zero-sum interaction), exhibit conservation laws when agents use the standard regret-minimizing dynamics known as Follow-the-Regularized-Leader. These laws persist when different agents use different dynamics and encode long-range correlations between agents’ behavior, even though the agents may not interact directly. Moreover, we provide sufficient conditions under which the dynamics have multiple, linearly independent, conservation laws. Increasing the number of conservation laws results in more predictable dynamics, eventually making chaotic behavior formally impossible in some cases.
DOI：
--
发表时间：
2018-07
期刊：
--
影响因子：
--
作者：
C. Daskalakis;Ioannis Panageas
通讯作者：
C. Daskalakis;Ioannis Panageas