Towards Runtime Analysis of Population-Based Co-evolutionary Algorithms on Sparse Binary Zero-Sum Game

Abstract:
Runtime analysis serves as a critical framework within the theory of AI to understand how algorithm design and problem structure influence the number of iterations needed to find solutions. This paper delves into population-based co-evolutionary algorithms applied to sparse binary zero-sum games, which serve as an essential benchmark in adversarial optimisation scenarios. We provide a novel theoretical perspective on how these algorithms navigate sparsity and adversarial dynamics effectively.

Our analysis introduces refined mathematical tools for understanding population diversity and its role in convergence. Notably, we explore the interaction of populations in achieving Nash equilibria and present the first runtime bounds for such co-evolutionary algorithms under sparse binary constraints. The work also examines critical challenges posed by these algorithms, including premature convergence and drift dynamics in adversarial landscapes.

This study contributes to the broader goal of improving the reliability and efficiency of co-evolutionary algorithms in competitive and game-theoretic settings, paving the way for future advancements in algorithm design for adversarial optimisation.