TY - GEN
T1 - Mutation, sexual reproduction and survival in dynamic environments
AU - Mehta, Ruta
AU - Panageas, Ioannis
AU - Piliouras, Georgios
AU - Tetali, Prasad
AU - Vazirani, Vijay V.
N1 - Funding Information:
Acknowledgements. We are grateful to Yuri Lyubich for helpful discussions. This work was completed while Ioannis Panageas was a PhD student at Georgia Institute of Technology. Ioannis Panageas would like to acknowledge NSF EAGER award grants CCF-1415496, CCF-1415498 and a MIT-SUTD postdoctoral fellowship. Georgios Piliouras would like to acknowledge SUTD grant SRG ESD 2015 097 and MOE AcRF Tier 2 Grant 2016-T2-1-170. Part of the work was completed while Ruta Mehta, Ioannis Panageas and Georgios Piliouras were visiting scientists at the Simons Institute for the Theory of Computing. Part of the work was completed while Ruta Mehta and Georgios Piliouras were visiting scientists at the Hausdorff Research Institute for Mathematics (HIM) during the Trimester Program on Combinatorial Optimization. Vijay Vazirani was supported by NSF Grant CCF-1216019.
PY - 2017/11/1
Y1 - 2017/11/1
N2 - A new approach to understanding evolution [34], 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 [8]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [35], 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.
AB - A new approach to understanding evolution [34], 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 [8]. Using this machinery, we study the role of mutation in changing environments in the presence of sexual reproduction. Following [35], 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.
KW - Evolution
KW - Mutation
KW - Non-linear dynamics
UR - http://www.scopus.com/inward/record.url?scp=85027263643&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027263643&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2017.16
DO - 10.4230/LIPIcs.ITCS.2017.16
M3 - Conference contribution
AN - SCOPUS:85027263643
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017
A2 - Papadimitriou, Christos H.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017
Y2 - 9 January 2017 through 11 January 2017
ER -