The game of survival: Sexual evolution in dynamic environments
Ruta Mehta, Ioannis Panageas, Georgios Piliouras, Prasad Tetali, Vijay V. Vazirani

Evolution is a complex algorithmic solution to life’s most pressing challenge, that of survival. It is a mixture of numerous textbook optimization techniques. Natural selection, the preferential replication ofthe fittest, encodes the multiplicative weights update algorithm, which in static environments is tantamount to exponential growth for the best solution. Sex can be interpreted as a game between different agents/genes with identical interests, maximizing the fitness of the individual. Mutation forces the exploration of consistently suboptimal solutions. Are all of these mechanisms necessary to ensure for survival? Also, how is it that despite their contradictory character (e.g., selection versus mutation) they do not cancel each other out? We address these questions by extending classic evolutionary models to allow for a dynamically changing environment. Sexual selection is well suited for static environments where we show that it converges polynomially fast to monomorphic populations. Mutations make the difference in dynamic environments. Without them species become extinct as they do not have the flexibility to recover fast given environmental change. On the other hand, we show that with mutation, as long as the rate of change of the environment is not too fast, long term survival is possible. Finally, mutation does not cancel the role of selection in static environments. Convergence remains guaranteed and only the level of polymorphism of the equilibria is affected. Our techniques quantify exploration-exploitation tradeoffs in time evolving non-convex optimization problems which could be of independent interest.