Memory loss can prevent chaos in games dynamics.

Recent studies have raised concerns on the inevitability of chaos in congestion games with large learning rates. We further investigate this phenomenon by exploring the learning dynamics in simple two-resource congestion games, where a continuum of agents learns according to a simplified experience-weighted attraction algorithm. The model is characterized by three key parameters: a population intensity of choice (learning rate), a discount factor (recency bias or exploration parameter), and the cost function asymmetry. The intensity of choice captures agents' economic rationality in their tendency to approximately best respond to the other agent's behavior. The discount factor captures a type of memory loss of agents, where past outcomes matter exponentially less than the recent ones. Our main findings reveal that while increasing the intensity of choice destabilizes the system for any discount factor, whether the resulting dynamics remains predictable or becomes unpredictable and chaotic depends on both the memory loss and the cost asymmetry. As memory loss increases, the chaotic regime gives place to a periodic orbit of period 2 that is globally attracting except for a countable set of points that lead to the equilibrium. Therefore, memory loss can suppress chaotic behaviors. The results highlight the crucial role of memory loss in mitigating chaos and promoting predictable outcomes in congestion games, providing insights into designing control strategies in resource allocation systems susceptible to chaotic behaviors.

An impossibility theorem in game dynamics.

The Nash equilibrium-a combination of choices by the players of a game from which no self-interested player would deviate-is the predominant solution concept in game theory. Even though every game has a Nash equilibrium, it is not known whether there are deterministic behaviors of the players who play a game repeatedly that are guaranteed to converge to a Nash equilibrium of the game from all starting points. If one assumes that the players' behavior is a discrete-time or continuous-time rule whereby the current mixed strategy profile is mapped to the next, this question becomes a problem in the theory of dynamical systems. We apply this theory, and in particular Conley index theory, to prove a general impossibility result: There exist games, for which all game dynamics fail to converge to Nash equilibria from all starting points. The games which help prove this impossibility result are degenerate, but we conjecture that the same result holds, under computational complexity assumptions, for nondegenerate games. We also prove a stronger impossibility result for the solution concept of approximate Nash equilibria: For a set of games of positive measure, no game dynamics can converge to the set of approximate Nash equilibria for a sufficiently small yet substantial approximation bound. Our results establish that, although the notions of Nash equilibrium and its computation-inspired approximations are universally applicable in all games, they are fundamentally incomplete as predictors of long-term player behavior.

Learning agents in Black-Scholes financial markets.

Black-Scholes (BS) is a remarkable quotation model for European option pricing in financial markets. Option prices are calculated using an analytical formula whose main inputs are strike (at which price to exercise) and volatility. The BS framework assumes that volatility remains constant across all strikes; however, in practice, it varies. How do traders come to learn these parameters? We introduce natural agent-based models, in which traders update their beliefs about the true implied volatility based on the opinions of other agents. We prove exponentially fast convergence of these opinion dynamics, using techniques from control theory and leader-follower models, thus providing a resolution between theory and market practices. We allow for two different models, one with feedback and one with an unknown leader.

α-Rank: Multi-Agent Evaluation by Evolution.

We introduce α-Rank, a principled evolutionary dynamics methodology, for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous-time and discrete-time evolutionary dynamical systems applied to empirical games, and scales tractably in the number of agents, in the type of interactions (beyond dyadic), and the type of empirical games (symmetric and asymmetric). Current models are fundamentally limited in one or more of these dimensions, and are not guaranteed to converge to the desired game-theoretic solution concept (typically the Nash equilibrium). α-Rank automatically provides a ranking over the set of agents under evaluation and provides insights into their strengths, weaknesses, and long-term dynamics in terms of basins of attraction and sink components. This is a direct consequence of the correspondence we establish to the dynamical MCC solution concept when the underlying evolutionary model's ranking-intensity parameter, α, is chosen to be large, which exactly forms the basis of α-Rank. In contrast to the Nash equilibrium, which is a static solution concept based solely on fixed points, MCCs are a dynamical solution concept based on the Markov chain formalism, Conley's Fundamental Theorem of Dynamical Systems, and the core ingredients of dynamical systems: fixed points, recurrent sets, periodic orbits, and limit cycles. Our α-Rank method runs in polynomial time with respect to the total number of pure strategy profiles, whereas computing a Nash equilibrium for a general-sum game is known to be intractable. We introduce mathematical proofs that not only provide an overarching and unifying perspective of existing continuous- and discrete-time evolutionary evaluation models, but also reveal the formal underpinnings of the α-Rank methodology. We illustrate the method in canonical games and empirically validate it in several domains, including AlphaGo, AlphaZero, MuJoCo Soccer, and Poker.

From Nash Equilibria to Chain Recurrent Sets: An Algorithmic Solution Concept for Game Theory.

In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer's (or, in another version Kakutani's) fixed point theorem, the most sophisticated result in his era's topology-in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept-this notion of "the outcome of the game"-every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games.

Modeling and analysis of modular structure in diverse biological networks.

Biological networks, like most engineered networks, are not the product of a singular design but rather are the result of a long process of refinement and optimization. Many large real-world networks are comprised of well-defined and meaningful smaller modules. While engineered networks are designed and refined by humans with particular goals in mind, biological networks are created by the selective pressures of evolution. In this paper, we seek to define aspects of network architecture that are shared among different types of evolved biological networks. First, we developed a new mathematical model, the Stochastic Block Model with Path Selection (SBM-PS) that simulates biological network formation based on the selection of edges that increase clustering. SBM-PS can produce modular networks whose properties resemble those of real networks. Second, we analyzed three real networks of very different types, and showed that all three can be fit well by the SBM-PS model. Third, we showed that modular elements within the three networks correspond to meaningful biological structures. The networks chosen for analysis were a proteomic network composed of all proteins required for mitochondrial function in budding yeast, a mesoscale anatomical network composed of axonal connections among regions of the mouse brain, and the connectome of individual neurons in the nematode C. elegans. We find that the three networks have common architectural features, and each can be divided into subnetworks with characteristic topologies that control specific phenotypic outputs.