Algorithms, Games and Evolution

Abstract: 

Even the most seasoned students of evolution, starting with Darwin himself, have occasionally expressed amazement that the mechanism of natural selection has produced all of life as we see it around us. Or stated from a computational viewpoint, what algorithm could possibly achieve all this in about 10^12 generations (steps)? We demonstrate that in the regime of weak selection, the standard equations of population genetics describing natural selection in the presence of sex become identical to those of a repeated game between genes played according to multiplicative weight updates (MWUA), an algorithm known to be surprisingly powerful and versatile. MWUA maximizes a trade-off between cumulative performance and entropy, which suggests a new view on the maintenance of diversity in evolution.

Based on joint work with Erick Chastain, Adi Livnat and Christos Papadimitriou