Research map / Learning theory and algorithms / Submodular and game algorithms
No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves a No Free Lunch theorem for black-box adversarial optimisation under the pure-strategy Nash equilibrium solution concept, and introduces black-box complexity lower bounds for finding unique Nash equilibria in two-player zero-sum games and bimatrix games.
Problem
Whether black-box adversarial (maximin) optimisation has a no-free-lunch property for general solution concepts, and how to characterise query complexity of finding Nash equilibria in zero-sum games for black-box algorithms.
Approach
Extends the classical permutation-closed NFL argument (induction on search-space size with sub-problem classes) to two-player zero-sum games with a unique pure NE, using game-theoretic lemmas to show isomorphism of sub-problems, and applies Yao's principle to derive unrestricted black-box complexity lower bounds for NE search.
Key results
- Theorem 3.1: under uniform distribution over permutation-closed zero-sum games with unique pure NE, all black-box adversarial algorithms have the same average query complexity.
- Theorem 4.1/4.2: black-box complexity lower bound of ceil(log_k |X x Y|) - 1, and expected query complexity at least (n+1)/2 for n x n bimatrix games with unique NE, a factor 4 sharper than prior bound.
- Theorem 4.4: DIAGONAL_n binary voting game class has black-box complexity Theta(n), while Theorem 4.5 shows PLATEAU_n has exp(Omega(n)) complexity.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the pure-strategy Nash equilibrium as the solution concept and count queries until reaching its row or column | Black-box algorithms on permutation-closed classes of two-player zero-sum games with a unique NE · Two-player zero-sum games with a unique pure NE | average expected query complexity: r(H, F) = r(H′, F) | No clear effect |
| Restrict the problem class to DIAGONAL instances | Unrestricted black-box algorithms for binary voting games · DIAGONALn | black-box complexity: eΩ(n) general class lower bound; Θ(n) for DIAGONALn | Helped |
| Use the PLATEAU instance class instead of the DIAGONAL instance class | Unrestricted black-box algorithms for binary voting games · PLATEAUn | black-box complexity lower bound: eΩ(n) | Hurt |
| Apply the general query-complexity analysis to games with a unique pure NE | Randomised black-box algorithms · n × n zero-sum bimatrix games | expected query complexity lower bound: (n + 1)/2 | Hurt |
Surprising findings
- Under the Nash equilibrium solution concept, the average performance of all black-box adversarial algorithms is identical, contrasting with prior free-lunch results for maximin and maximisation-over-all-test-cases concepts.
- Adding plateau structure to binary voting games makes them exponentially hard for black-box algorithms, so additional assumptions do not necessarily lower difficulty.
Limitations
- Results restricted to finite discrete search spaces, not countable or uncountable sets.
- NFL only covers two-player zero-sum games with unique pure Nash equilibrium, not mixed NE or multiple NE.
Experimental setup
Metrics: expected query complexity
Baselines: FINDPSNE fictitious play Maximin free lunch (Wolpert and Macready) Maximisation over all test cases free lunch (Service and Tauritz)
Builds on: No Free Lunch theorems (Wolpert and Macready) Droste et al. generalised NFL Yao's minimax principle Lehre-Fajardo FINDPSNE bimatrix NE lower bound
Closest papers by meaning
- Solving Neural Min-Max Games: The Role of Architecture, Initialization & Dynamics (NeurIPS 2025 · similarity 0.88)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
- The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games (NeurIPS 2025 · similarity 0.87)
- The Complexity of Two-Team Polymatrix Games with Independent Adversaries (ICLR 2025 · similarity 0.87)
- Towards Runtime Analysis of Population-Based Co-evolutionary Algorithms on Sparse Binary Zero-Sum Game (AAAI 2025 · similarity 0.86)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.