Hot off the Press: No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation
Per Kristian Lehre, Shishen Lin · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2025
Black-box optimisation is a central topic in optimisation theory, with the original No Free Lunch (NFL) theorems revealing fundamental limits of general-purpose algorithms. Understanding the implications of NFL in adversarial (maximin) optimisation has remained an open challenge [15, 16]. This paper establishes a rigorous NFL theorem for black-box adversarial optimisation under the Pure Strategy Nash Equilibrium (NE) solution concept. We highlight the role of the solution concept in defining optimality and show that, when performance is measured by the number of rows and columns queried in the payoff matrix, the average performance of all black-box adversarial optimisation algorithms is the same. We further develop a black-box complexity framework to analyse adversarial optimisation. By combining Yao's Principle with our NFL theorem, we derive general lower bounds on the query complexity for computing Nash Equilibria.