From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics

Sai Ganesh Nagarajan, David Balduzzi, Georgios Piliouras
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:7186-7196, 2020.

Abstract

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 \emph{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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-nagarajan20a, title = {From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics}, author = {Nagarajan, Sai Ganesh and Balduzzi, David and Piliouras, Georgios}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {7186--7196}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/nagarajan20a/nagarajan20a.pdf}, url = {https://proceedings.mlr.press/v119/nagarajan20a.html}, abstract = {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 \emph{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.} }
Endnote
%0 Conference Paper %T From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics %A Sai Ganesh Nagarajan %A David Balduzzi %A Georgios Piliouras %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-nagarajan20a %I PMLR %P 7186--7196 %U https://proceedings.mlr.press/v119/nagarajan20a.html %V 119 %X 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 \emph{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.
APA
Nagarajan, S.G., Balduzzi, D. & Piliouras, G.. (2020). From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:7186-7196 Available from https://proceedings.mlr.press/v119/nagarajan20a.html.

Related Material