Algorithms, Games and Evolution

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 perspective, what algorithm could possibly achieve Nature's solution to the problems of robotics, vision and theorem proving 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 recombination 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. A dual description of MWUA shows that it 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).