Replicator dynamics and the simplex as a vector space

Over the years of TheEGG, I’ve chronicled a number of nice properties of the replicator equation and its wide range of applications. From a theoretical perspective, I showed how the differential version can serve as the generator for the action that is the finite difference version of replicator dynamics. And how measurements of replicator dynamics can correspond to log-odds. From an application perspective, I talked about how replicator dynamics can be realized in many different ways. This includes a correspondance to idealized replating experiments and a representation of populations growing toward carrying capacity via fictitious free-space strategies. These fictitious strategies are made apparent by using a trick to factor and nest the replicator dynamics. The same trick can also help us to use the symmetries of the fitness functions for dimensionality reduction and to prove closed orbits in the dynamics. And, of course, I discussed countless heuristic models and some abductions that use replicator dynamics.

But whenever some object becomes so familiar and easy to handle, I get worried that I am missing out on some more foundational and simple structure underlying it. In the case of replicator dynamics, Tom Leinster’s post last year on the n-Category Cafe pointed me to the simple structure that I was missing: the vector space structure of the simplex. This allows us to use linear algebra — the friendliest tool in the mathematician’s toolbox — in a new way to better understand evolutionary dynamics.

A 2-simplex with some of its 1-dimensional linear subspaces drawn by Greg Egan.

Given my interest in operationalization of replicator dynamics, I will use some of the terminology and order of presentation from Aitchison’s (1986) statistical analysis of compositional data. We will see that a number of operations that we define will have clear experimental and evolutionary interpretations.

I can’t draw any real conclusions from this, but I found it worth jotting down for later reference. If you can think of a way to make these observations useful then please let me know.

Given a list of arbitrary positive numbers N_1, N_2, ... , N_D \in \mathbb{R}_+ — say the population sizes of D types — we will define their closure as

\mathit{C}[N_1, N_2, ... , N_D] = [\frac{N_1}{N}, \frac{N_2}{N} ... , \frac{N_D}{N}]

where N = \sum_{i = 1}^D N_i is the total of the numbers. The closure operator also takes us from \mathbb{R}^D_+ to the simplex interior \Delta^D. Dynamically and experimentally, we can think of this — as we did before — as replating.

To make \Delta^D into a vector space over \mathbb{R}, we need to define addition of vectors \oplus: \Delta^D \times \Delta^D \rightarrow \Delta^D and multiplication by scalars \otimes: \mathbb{R} \times \Delta^D \rightarrow \Delta^D. Given \alpha \in \mathbb{R} and \mathbf{x}, \mathbf{y} \in \Delta^D, we can do this as:

\begin{aligned}  \mathbf{x} \oplus \mathbf{y} & = \mathit{C}[x_1 y_1, x_2 y_2, ..., x_D y_D] \\  \alpha \otimes \mathbf{x} & = \mathit{C}[x_1^\alpha, x_2^\alpha, ..., x_D^\alpha]  \end{aligned}

I encourage you, dear reader, to check that these two operations satisfy the axioms of a vector space, with zero element given by the uniform distribution \mathbf{u} = [\frac{1}{D},\frac{1}{D},...,\frac{1}{D}].

This vector addition has a straightforward evolutionary interpretation. To notice this, we just need to look at the suggestively labelled \mathbf{y} = \mathbf{w} \oplus \mathbf{x} and see what each entry in the vector \mathbf{y} expands to:

\begin{aligned}  y_i & = [\mathbf{w} \oplus \mathbf{x}]_i \\  & = \mathit{C}[w_1x_1, w_2x_2, ..., w_Dx_D]_i \\  & = \frac{w_ix_i}{\langle w \rangle}  \end{aligned}

where \langle w \rangle = \sum_{i = 1}^D x_i w_i.

In other words, in this vector space, the discrete time replicator equation is just the addition of the fitness vector to the population distribution.

If the fitness vector w is constant then starting with a population distribution x and iterating forward n times gives us n\otimes \mathbf{w} \;\oplus\; \mathbf{x}. In the limit as n \rightarrow \infty, this dynamic forgets the initial distribution and takes us to the boundry of the simplex, giving us a uniform distribution over the maximum elements of w and setting all other elements to zero. Survival of the fittest.

We can also search for friendly faces among the linear operators \Delta^D \rightarrow \mathbb{R} on this vector space. One of the nicest ones is the cross entropy:

\begin{aligned}  h_\mathbf{x}(\mathbf{y}) = -\sum_{i = 1}^D x_i \ln (y_i)  \end{aligned}

It is not difficult to check that this is indeed linear:

\begin{aligned}  h_\mathbf{x}(\mathbf{y} \oplus \mathbf{z}) & = -\sum_{i = 1}^D x_i \ln (y_iz_i) \\  & = (-\sum_{i = 1}^D x_i \ln (y_i)) + (-\sum_{i = 1}^D x_i \ln (z_i)) \\  & = h_\mathbf{x}(\mathbf{y}) + h_\mathbf{x}(\mathbf{z})  \end{aligned}

With this observation in mind, we could define a dual space over the elements h_\mathbf{x} with the normal addition and multiplication on x. The dual pairs would have a natural interpretation, but wouldn’t form an inner-product.

But linear algebra is nicer for inner-product spaces. And in compositional data analysis, it is customary to turn the simplex into an inner-product space by defining the Aitchison inner-product as:

\langle \mathbf{x},\mathbf{y} \rangle = \frac{1}{2D} \sum_{i, j = 1}^D (\ln \frac{x_i}{x_j})(\ln \frac{y_i}{y_j})

Unfortunately, I don’t know an intuitive interpretation for this inner-product or what aspect of typical evolutionary experimental set-ups it would be capturing. Do you have ideas?

With these observations hanging out right near information theoretic constructs like entropy (and also linear algebra) suggests that there should be some ways to use this to push for better algorithms for learning replicator dynamics or measuring effective games. Maybe a way to push forward on estimating reductive games and spacial structure together. Things I’ll continue to think about in the future. Even if I have no new ideas right now.

References

Aitchison J. (1986), The Statistical Analysis of Compositional Data, Chapman & Hall

Advertisements

About Artem Kaznatcheev
From the Department of Computer Science at Oxford University and Department of Translational Hematology & Oncology Research at Cleveland Clinic, I marvel at the world through algorithmic lenses. My mind is drawn to evolutionary dynamics, theoretical computer science, mathematical oncology, computational learning theory, and philosophy of science. Previously I was at the Department of Integrated Mathematical Oncology at Moffitt Cancer Center, and the School of Computer Science and Department of Psychology at McGill University. In a past life, I worried about quantum queries at the Institute for Quantum Computing and Department of Combinatorics & Optimization at University of Waterloo and as a visitor to the Centre for Quantum Technologies at National University of Singapore. Meander with me on Google+ and Twitter.

One Response to Replicator dynamics and the simplex as a vector space

  1. Pingback: Cataloging a sparse year of blogging: IMO workshop and preprints | Theory, Evolution, and Games Group

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s