2014/11/24 by Ruta Mehta, Mehta, Ruta, Ioannis Panageas +5
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · Mathematics · Social Sciences · #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Dynamical Systems (math.DS) #Evolution and Genetic Dynamics #Evolutionary Game Theory and Cooperation #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Populations and Evolution (q-bio.PE) #Spectral Theory (math.SP) #cs.CC #cs.GT #math.DS #math.SP #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1411.6322
24 pages, 2 figues
openalex publication_date 2014/11/24 · arxiv created 2015/10/22 · arxiv updated 2015/10/23 · openalex created_date 2019/07/30 · openalex updated_date 2026/07/28
A key question in biological systems is whether genetic diversity persists in the long run under evolutionary competition or whether a single dominant genotype emerges. Classic work by Kalmus in 1945 has established that even in simple diploid species (species with two chromosomes) diversity can be guaranteed as long as the heterozygote individuals enjoy a selective advantage. Despite the classic nature of the problem, as we move towards increasingly polymorphic traits (e.g. human blood types) predicting diversity and understanding its implications is still not fully understood. Our key contribution is to establish complexity theoretic hardness results implying that even in the textbook case of single locus diploid models predicting whether diversity survives or not given its fitness landscape is algorithmically intractable. We complement our results by establishing that under randomly chosen fitness landscapes diversity survives with significant probability. Our results are structurally robust along several dimensions (e.g., choice of parameter distribution, different definitions of stability/persistence, restriction to typical subclasses of fitness landscapes). Technically, our results exploit connections between game theory, nonlinear dynamical systems, complexity theory and biology and establish hardness results for predicting the evolution of a deterministic variant of the well known multiplicative weights update algorithm in symmetric coordination games which could be of independent interest.