Many multi-agent machine learning settings can be modeled as games, from social or economic systems with algorithmic decision-makers to popular learning architectures such as generative adversarial networks (GANs). Desired outcomes in these settings are often encoded as equilibrium concepts, and therefore a primary goal is identifying machine learning algorithms with provable convergence to these equilibria. However, a growing body of negative results casts doubt on this goal by uncovering games exhibiting non-convergence, chaos, and even essentially arbitrary behaviour [Andrade et al. 2021; Benaïm et al. 2012; Cheung and Piliouras 2019; Chotibut et al. 2020; Flokas et al. 2020; Letcher 2021; Milionis et al. 2022; Wibisono et al. 2022].

Many multi-agent systems with strategic interactions have their desired functionality encoded as the Nash equilibrium of a game, e.g. machine learning architectures such as Generative Adversarial Networks. Directly computing a Nash equilibrium of these games is often impractical or impossible in practice, which has led to the development of numerous learning algorithms with the goal of iteratively converging on a Nash equilibrium. Unfortunately, the dynamics generated by the learning process can be very intricate and instances failing to converge become hard to interpret. In this paper we show that, in a strong sense, this dynamic complexity is inherent to games. Specifically, we prove that replicator dynamics, the continuous-time analogue of Multiplicative Weights Update, even when applied in a very restricted class of games–known as finite matrix games–is rich enough to be able to approximate arbitrary dynamical systems. In the context of machine learning, our results are positive in the sense that they show the nearly boundless dynamic modelling capabilities of current machine learning practices, but also negative in implying that these capabilities may come at the cost of interpretability. As a concrete example, we show how replicator dynamics can effectively reproduce the well-known strange attractor of Lonrenz dynamics (the “butterfly effect") while achieving no regret.

Kakade, Kearns, and Ortiz (KKO) introduce a graph-theoretic generalization of the classic Arrow--Debreu (AD) exchange economy. Despite its appeal as a networked version of AD, we argue that the KKO model is too local, in the sense that goods cannot travel more than one hop through the network. We introduce an alternative model in which agents may purchase goods on credit in order to resell them. In contrast to KKO, our model allows for long-range trade, and yields equilibria in more settings than KKO, including sparse endowments. Our model smoothly interpolates between the KKO and AD equilibrium concepts: we recover KKO when the resale capacity is zero, and recover AD when it is sufficiently large. We give general equilibrium existence results, and an auction-based algorithm to compute approximate equilibria when agent utilities satisfy the weak gross-substitutes property.

Recent advances in brain imaging techniques require the development of advanced models of brain networks and graphs. Previous work on percolation on lattices and random graphs demonstrated emergent dynamical regimes, including zero- and non-zero fixed points, and limit cycle oscillations. Here we introduce graph processes using lattices with excitatory and inhibitory nodes, and study conditions leading to spatio-temporal oscillations. Rigorous mathematical analysis provides insights on the possible dynamics and, of particular concern to this work, conditions producing cycles with very long periods. A systematic parameter study demonstrates the presence of phase transitions between various regimes, including oscillations with emergent metastable patterns. We studied the impact of external stimuli on the dynamic patterns, which can be used for encoding and recall in robust associative memories.