License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2017.16
URN: urn:nbn:de:0030-drops-81655
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8165/
Go to the corresponding LIPIcs Volume Portal

Mehta, Ruta ; Panageas, Ioannis ; Piliouras, Georgios ; Tetali, Prasad ; Vazirani, Vijay V.

Mutation, Sexual Reproduction and Survival in Dynamic Environments

pdf-format:
LIPIcs-ITCS-2017-16.pdf (0.7 MB)

Abstract

A new approach to understanding evolution [Valiant, JACM 2009], namely viewing it through the lens of computation,
has already started yielding new insights, e.g., natural selection under sexual reproduction can be interpreted
as the Multiplicative Weight Update (MWU) Algorithm in coordination games played among genes [Chastain, Livnat, Papadimitriou, Vazirani, PNAS 2014]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [Wolf, Vazirani, Arkin, J. Theor. Biology], we model changing environments via a Markov chain, with the states representing environments, each with its own fitness matrix. In this setting, we show that in the absence of mutation, the population goes extinct, but in the presence of mutation, the population survives with positive probability.

On the way to proving the above theorem, we need to establish some facts about dynamics in games. We provide the first, to our knowledge, polynomial convergence bound for noisy MWU in a coordination game.
Finally, we also show that in static environments, sexual evolution with mutation converges, for any level of mutation.

BibTeX - Entry

@InProceedings{mehta_et_al:LIPIcs:2017:8165,
  author =	{Ruta Mehta and Ioannis Panageas and Georgios Piliouras and Prasad Tetali and Vijay V. Vazirani},
  title =	{{Mutation, Sexual Reproduction and Survival in Dynamic Environments}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{16:1--16:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Christos H. Papadimitriou},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8165},
  URN =		{urn:nbn:de:0030-drops-81655},
  doi =		{10.4230/LIPIcs.ITCS.2017.16},
  annote =	{Keywords: Evolution, Non-linear dynamics, Mutation}
}

Keywords: Evolution, Non-linear dynamics, Mutation
Collection: 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Issue Date: 2017
Date of publication: 28.11.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI