Timezone: »

 
Poster
From Chaos to Order: Symmetry and Conservation Laws in Game Dynamics
Sai Ganesh Nagarajan · David Balduzzi · Georgios Piliouras

Wed Jul 15 04:00 PM -- 04:45 PM & Thu Jul 16 04:00 AM -- 04:45 AM (PDT) @ Virtual
in Poster Session 30 »

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.

Keywords: Game Theory and Mechanism Design · Learning Theory · Multiagent Learning · Online Learning / Bandits · Reinforcement Learning Theory
[ Slides] 

Author Information

Sai Ganesh Nagarajan (SUTD)
David Balduzzi (DeepMind)
Georgios Piliouras (Singapore University of Technology and Design)

More from the Same Authors