Evolution is exponentially more powerful with frequency-dependent selection

Abstract

Valiant [1] proposed to treat Darwinian evolution as a special kind of computational learning from statistical queries. The statistical queries represent a genotypes fitness over a distribution of challenges. And this distribution of challenges along with the best response to them specify a given abiotic environment or static fitness landscape. Valiants model distinguished families of environments that are "adaptable-to" from those that are not. But this model of evolution omits the vital ecological interactions between different evolving agents - it neglects the rich biotic environment that is central to the struggle for existence. In this article, I extend algorithmic Darwinism to include the ecological dynamics of frequency-dependent selection as a population-dependent bias to the distribution of challenges that specify an environment. Thus, extended algorithmic Darwinism suggests extended statistical queries rather than just statistical queries as the appropriate model for eco-evo dynamics. This extended algorithmic Darwinism replaces simple invasion of wild-type by a mutant-type of higher scalar fitness with an evolutionary game between wild-type and mutant-type based on their frequency-dependent fitness function. To analyze this model, I develop a game landscape view of evolution, as a generalization of the classic fitness landscape approach. I show that this model of eco-evo dynamics on game landscapes can provide an exponential speed-up over the purely evolutionary dynamics of the strict algorithmic Darwinism. In particular, I prove that the Parity environment - which is known to be not adaptable-to under strict algorithmic Darwinism - is adaptable-to by eco-evo dynamics. Thus, the ecology of frequency-dependent selection does not just increase the tempo of evolution, but fundamentally transforms its mode. This happens even if frequency-dependence is restricted to short-time scales - such short bursts of frequency-dependent selection can have a transformative effect on the ability of populations to adapt to their environments in the long-term. Unlike typical learning algorithms, the eco-evo dynamic for adapting to the Parity environment does not rely on Gaussian elimination. Instead, the dynamics proceed by simple isotropic mutations and selection in finite populations of just two types (the resident wild-type and invading mutant). The resultant process has two stages: (1) a quick stage of point-mutations that moves the population to one of exponentially many local fitness peaks; followed by (2) a slower stage where each step follows a double-mutation by a point-mutation. This second stage allows the population to hop between local fitness peaks to reach the unique global fitness peak in polynomial time. The evolutionary game dynamics of finite populations are essential for finding a short adaptive path to the global fitness peak during the second stage of the adaptation process. This highlights the rich interface between computational learning theory, analysis of algorithms, evolutionary games, and long-term evolution.