Research map / Learning theory and algorithms / Submodular and game algorithms
Towards Runtime Analysis of Population-Based Co-evolutionary Algorithms on Sparse Binary Zero-Sum Game
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.
Provides the first rigorous runtime analysis of population-based co-evolutionary algorithms with pairwise dominance on the binary DIAGONAL zero-sum game, showing PDCoEA finds the optimum in polynomial time while RLS-PD and (1+1)-CoEA take exponential time.
Problem
Discrete binary two-player zero-sum games (maximin optimisation) with sparse binary payoffs, where gradient methods are inapplicable and the theory of co-evolutionary algorithms is limited.
Approach
Adapts the level-based theorem to co-evolution with an initialisation-aware variant and applies it to PDCoEA (population-based pairwise-dominance CoEA) on the DIAGONAL game, contrasting it with single-pair CoEAs that suffer negative drift.
Key results
- PDCoEA finds the DIAGONAL optimum in polynomial runtime w.h.p. with low constant mutation rate and population size lambda = Omega(log n), with runtime bound O(lambda n (lambda^2 + n^2)) roughly per the theorem.
- RLS-PD and (1+1)-CoEA require runtime e^{Omega(n)} with probability at least 1 - e^{-Omega(n)} on DIAGONAL.
- Empirically, best mean runtime for PDCoEA at chi=0.3 is about 0.12e6, 1.05e6 and 2.71e6 for n=100, 500, 1000; high mutation rates above chi=0.5 make PDCoEA inefficient.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use population-based PDCoEA with a low constant mutation rate and large population | CoEA on DIAGONAL · DIAGONAL | runtime: at most rdλn(λ² + n²) | Helped |
| Use a single-pair RLS-PD instead of population-based PDCoEA | CoEA on DIAGONAL · DIAGONAL | runtime: at least eΩ(n) | Hurt |
| Use single-pair (1+1)-CoEA instead of population-based PDCoEA | CoEA on DIAGONAL · DIAGONAL | runtime: at least eΩ(n) | Hurt |
| Increase the mutation rate above χ = 0.5 (ablation) | PDCoEA · DIAGONAL | runtime: χ = 0.5 | Hurt |
| Use population size below λ ≥ 0.4n (ablation) | PDCoEA · DIAGONAL (n = 100) | runtime: λ ≥ 0.4n | Hurt |
| Use population size below λ ≥ 0.2n (ablation) | PDCoEA · DIAGONAL (n = 500, 1000) | runtime: λ ≥ 0.2n | Hurt |
| Use bit-wise mutation instead of local mutation (ablation) | single-pair CoEA with pairwise dominance · DIAGONAL | runtime: at least eΩ(n) | No clear effect |
| Use χ = 0.3 with the tested configurations (ablation) | PDCoEA · DIAGONAL (n = 100) | empirical mean runtime: 0.12 × 106 | Helped |
| Use χ = 0.3 with the tested configurations (ablation) | PDCoEA · DIAGONAL (n = 500) | empirical mean runtime: 1.05 × 106 | Helped |
| Use χ = 0.3 with the tested configurations (ablation) | PDCoEA · DIAGONAL (n = 1000) | empirical mean runtime: 2.71 × 106 | Helped |
| Initialize both populations at Hamming weight n/2 (ablation) | PDCoEA · DIAGONAL | runtime | Helped |
Surprising findings
- Single-pair CoEAs with pairwise dominance fail on DIAGONAL despite succeeding on BILINEAR, due to flat binary payoff landscape and genetic drift.
- Empirical runtimes suggest the theoretical bound may not be tight; the authors conjecture O(lambda n log n) runtime.
Limitations
- Analysis of PDCoEA requires initialisation at level n/2 (near diagonal); random initialisation left open.
- Requires assumption (A|G2a) on fraction of population in A_j x B_j, which is only partially justified.
- Theoretical bound not tight compared to empirical results.
Experimental setup
Benchmarks: DIAGONAL game
Metrics: runtime (function evaluations) empirical mean runtime Wilcoxon rank-sum p-values
Baselines: RLS-PD (1+1)-CoEA
Builds on: Level-Based Theorem (Lehre 2022) PDCoEA (Lehre 2022) RLS-PD (Hevia Fajardo, Lehre, and Lin 2023) Negative Drift Theorem
Closest papers by meaning
- Why Playing Against Diverse and Challenging Opponents Speeds Up Coevolution: A Theoretical Analysis on Combinatorial Games (NeurIPS 2025 · similarity 0.90)
- On the $O(1/T)$ Convergence of Alternating Gradient Descent–Ascent in Bilinear Games (ICLR 2026 · similarity 0.89)
- No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation (NeurIPS 2024 · similarity 0.86)
- Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.86)
- Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms (NeurIPS 2024 · similarity 0.86)
- Convergence of $\text{log}(1/\epsilon)$ for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis (NeurIPS 2024 · similarity 0.86)
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.