Description
Title: Dynamical Systems, Games, and Topology: a relationship in formation
Abstract: A basic question that has arisen ever since the genesis of the concept of the Nash Equilibrium [Nash, 1951] is whether it can adequately capture the long-term behavior of players who play a game repeatedly. Considering the case where the players’ behavior is represented by a rule/map from the current mixed strategy to the next, this becomes a problem in the realm of dynamical systems. In this context, we will ponder to what extent we might (or might not) expect Nash Equilibria to be attractors of dynamical systems. At the same time, we will wonder: What does it even mean for a dynamical system to converge, when one might observe chaotic-like behavior? Our journey will include an expansive introduction to some notions of the mathematical field of Algebraic Topology, and we will showcase the power of topological arguments in our effort to understand the limits of Nash Equilibria. The culmination of that discussion will be a general impossibility result: there exist games for which no game dynamics’ long-term behavior can be described by Nash Equilibria in a satisfactory way. A similar, but even stronger, result holds, if we had desired that approximate Nash Equilibria be the entire "set of fate" of any game dynamics; there, there is a positive-measure set of games for which the set of approximate Nash Equilibria cannot accurately characterize the fate of the dynamical system. Nonetheless, complexity will also manifest itself in our discussion, since we will show that for non-degenerate games in particular, we can construct such game dynamics, albeit with complexity-wise obstacles this time, and we will end our exploration with our conjecture that constructing such a game dynamics for non-degenerate games is PPAD-complete.
The talk is based on recent submitted joint work with Christos Papadimitriou (Columbia University), Georgios Piliouras (Singapore University of Technology and Design), and Kelly Spendlove (University of Oxford).
Bio: Jason Milionis is a first-year Ph.D. student in the Computer Science Department at Columbia University, advised by Christos Papadimitriou and Tim Roughgarden. He is broadly interested in Game Theory, especially in combination with Machine Learning. Previously, he graduated with a bachelor's degree in Electrical and Computer Engineering with a major in Computer Science from the National Technical University of Athens (NTUA).
All scheduled dates:
Upcoming
No Upcoming activities yet