William H. Sandholm

We consider a model of learning and evolution in games whose action sets are endowed with a partition-based similarity structure intended to capture exogenous similarities between strategies. In this model, revising agents have a higher probability of comparing their current strategy with other strategies that they deem similar, and they switch to the observed strategy with probability proportional to its payoff excess. Because of this implicit bias toward similar strategies, the resulting dynamics - which we call the nested replicator dynamics - do not satisfy any of the standard monotonicity postulates for imitative game dynamics; nonetheless, we show that they retain the main long-run rationality properties of the replicator dynamics, albeit at quantitatively different rates. We also show that the induced dynamics can be viewed as a stimulus-response model in the spirit of Erev & Roth (1998), with choice probabilities given by the nested logit choice rule of Ben-Akiva (1973) and McFadden (1978). This result generalizes an existing relation between the replicator dynamics and the exponential weights algorithm in online learning, and provides an additional layer of interpretation to our analysis and results.

We characterize solutions of a class of time-homogeneous optimal control problems with semilinear running costs and state constraints as maximal viscosity subsolutions to Hamilton-Jacobi equations and show that optimal solutions to these problems can be constructed explicitly. We present applications to large deviations problems arising in evolutionary game theory.

Schelling [13] introduces a seminal model of the dynamics of residential segregation in an isolated neighborhood. His model combines agent heterogeneity with explicit behavior dynamics; as such it is presented informally, and with the use of "semi-equilibrium" restrictions on out-of-equilibrium play. In this paper, we use recent techniques from evolutionary game theory to introduce a formal version of Schelling's model, one that dispenses with equilibrium restrictions on the adjustment process. We show that key properties of the resulting infinite-dimensional dynamic can be derived using a simple finite-dimensional dynamic that captures aggregate behavior. We determine conditions for the stability of integrated equilibria, and we derive a strong restriction on out-of-equilibrium dynamics that implies global convergence to equilibrium: along any solution trajectory, one population's aggregate behavior adjusts monotonically, while the other's changes direction at most once. We present a variety of examples, and we show how extensions of the basic model can be used to study both alternative specifications of agents' preferences and policies to promote integration.

We study a model of stochastic evolutionary game dynamics in which the probabilities that agents choose suboptimal actions are dependent on payoff consequences. We prove a sample path large deviation principle, characterizing the rate of decay of the probability that the sample path of the evolutionary process lies in a prespecified set as the population size approaches infinity. We use these results to describe excursion rates and stationary distribution asymptotics in settings where the mean dynamic admits a globally attracting state, and we compute these rates explicitly for the case of logit choice in potential games.

We study a class of evolutionary game dynamics defined by balancing a gain determined by the game's payoffs against a cost of motion that captures the difficulty with which the population moves between states. Costs of motion are represented by a Riemannian metric, i.e., a state-dependent inner product on the set of population states. The replicator dynamics and the (Euclidean) projection dynamics are the archetypal examples of the class we study. Like these representative dynamics, all Riemannian game dynamics satisfy certain basic desiderata, including positive correlation and global convergence in potential games. Moreover, when the underlying Riemannian metric satisfies a Hessian integrability condition, the resulting dynamics preserve many further properties of the replicator and projection dynamics. We examine the close connections between Hessian game dynamics and reinforcement learning in normal form games, extending and elucidating a well-known link between the replicator dynamics and exponential reinforcement learning.

We study a model of stochastic evolutionary game dynamics in which the probabilities that agents choose suboptimal actions are dependent on payoff consequences. We prove a sample path large deviation principle, characterizing the rate of decay of the probability that the sample path of the evolutionary process lies in a prespecified set as the population size approaches infinity. We use these results to describe excursion rates and stationary distribution asymptotics in settings where the mean dynamic admits a globally attracting state, and we compute these rates explicitly for the case of logit choice in potential games.