Runtime Analysis of Coevolutionary Algorithms on a Class of Symmetric Zero-Sum Games

A standard aim in game theory is to find a pure or mixed Nash equilibrium. For strategy spaces too large for a Nash equilibrium to be computed classically, this can instead be approached using a coevolutionary algorithm. How to design coevolutionary algorithms which avoid pathological behaviours (such as cycling or forgetting) on challenging games is then a crucial open problem.

We argue that runtime analysis can provide insight and inform the design of more powerful and reliable algorithms for this purpose. To this end, we consider a class of symmetric zero-sum games for which the role of population diversity is pivotal to an algorithm's success. We prove that a broad class of algorithms which do not utilise a population have superpolynomial runtime for this class. In the other direction we prove that, with high probability, a coevolutionary instance of the univariate marginal distribution algorithm finds the unique Nash equilibrium in time $O(n(\log{n})^2)$.

Together, these results demonstrate the importance of generating diverse search points for evolving better strategies. The corresponding proofs develop several techniques that may benefit future analysis of estimation-of-distribution and coevolutionary algorithms.