Population Games and Evolutionary Dynamics

by William H. Sandholm

To be published by MIT Press.

Overview

Population games provide a general model of strategic interactions among large numbers of agents; highway congestion, multilateral externalities, and natural selection are among their many applications. As the direct assumption of equilibrium play seems difficult to justify in these games, behavior is most naturally modeled as a dynamic adjustment processes. To accomplish this, one can begin with an explicit stochastic description of how individual agents make decisions. When the number of agents is large enough and the time horizon of interest not too long, the evolution of aggregate behavior is well approximated by solutions to ordinary differential equations. We discuss various classes of population games in which these deterministic evolutionary dynamics lead to equilibrium play, and also consider simple examples in which more complicated limit behavior occurs. If one is interested in behavior over very long time spans, one studies the stochastic evolutionary processes directly, focusing on their ergodic and large deviations properties.

Many of the mathematical techniques used in evolutionary game theory are not part of the standard economics curriculum. To make evolution more accessible to graduate students in economics and other fields, the book includes detailed appendices on topics in multivariate calculus, convex analysis, dynamical systems, and stochastic processes that are essential for understanding evolutionary models. The book also includes many color figures, created using the shareware program Dynamo, to present population games and evolutionary dynamics in an intuitive, geometric fashion.

Current draft: 4/29/08

Since the last posting in May 2007, I have added a new chapter (7) on local stability analysis and made many additions and corrections to the other chapters. The remaining two chapters (0 and 10) are well underway.

• With figures (16.3 MB)
• Without figures (1.2 MB)

Table of Contents

Chapter 0: Introduction (to be added)

Part I: Population Games

Chapter 1: Population Games

0. Introduction
1. Population Games
2. Examples
3. The Geometry of Population Games and Nash Equilibria
1. Affine Spaces, Tangent Spaces, and Orthogonal Projections
2. The Moreau Decomposition Theorem

Chapter 2: Potential Games, Stable Games, and Supermodular Games

0. Introduction
1. Full Potential Games
2. Potential Games
3. Stable Games
4. Supermodular Games
1. Multivariate Calculus
2. Affine Calculus

Part II: Deterministic Evolutionary Dynamics

Chapter 3: Revision Protocols and Evolutionary Dynamics

0. Introduction
1. Revision Protocols and Mean Dynamics
2. Examples
3. Evolutionary Dynamics
1. Ordinary Differential Equations

Chapter 4: Deterministic Dynamics: Families and Properties

0. Introduction
1. Principles for Evolutionary Modeling
2. Desiderata for Revision Protocols and Evolutionary Dynamics
3. Families of Evolutionary Dynamics
4. Imitative Dynamics
5. Excess Payoff Dynamics
6. Pairwise Comparison Dynamics
7. Multiple Revision Protocols and Combined Dynamics

Chapter 5: Best Response and Projection Dynamics

0. Introduction
1. The Best Response Dynamic
2. Perturbed Best Response Dynamics
3. The Projection Dynamic
1. Differential Inclusions
2. The Legendre Transform
3. Perturbed Optimization

Part III: Convergence and Nonconvergence

Chapter 6: Global Convergence of Evolutionary Dynamics

0. Introduction
1. Potential Games
2. Stable Games
3. Supermodular Games
4. Dominance Solvable Games
1. Limit and Stability Notions for Deterministic Dynamics
2. Stability Analysis via Lyapunov Functions
3. Cooperative Differential Equations

Chapter 7: Local Stability under Evolutionary Dynamics

0. Introduction
1. Non-Nash Rest Points of Imitative Dynamics
2. Local Stability in Potential Games
3. Evolutionarily Stable States
4. Local Stability via Lyapunov Functions
5. Linearization of Imitative Dynamics
6. Linearization of Perturbed Best Response Dynamics
1. Matrix Analysis
2. Linear Differential Equations
3. Linearization of Nonlinear Differential Equations

Chapter 8: Nonconvergence of Evolutionary Dynamics

0. Introduction
1. Conservative Properties of Evolutionary Dynamics
2. Games with Nonconvergent Evolutionary Dynamics
3. Chaotic Evolutionary Dynamics
4. Survival of Dominated Strategies
1. Three Classical Theorems on Nonconvergent Dynamics
2. Attractors and Continuation

Part IV: Stochastic Evolutionary Models

Chapter 9: Stochastic Evolution and Deterministic Approximation

0. Introduction
1. The Stochastic Evolutionary Process
2. Finite Horizon Deterministic Approximation
3. Extensions
1. The Exponential and Poisson Distributions
2. Countable State Markov Processes
3. Kurtz's Theorem in Discrete Time

Chapter 10: Infinite Horizon Behavior and Equilibrium Selection (to be added)

Back to my homepage.