From Verification to Discovery: The Query Complexity of Equilibrium Certification

Self-play can learn approximate Nash equilibria from noisy interactions, but does finding an equilibrium require more information than checking a supplied candidate? We study this gap between discovery and verification and how it depends on payoff structure. For bounded $k\times k$ zero-sum games with unit-variance Gaussian payoff queries, verification under a constant-factor accuracy margin uses $O(k)$ queries at fixed small accuracy and confidence, while discovery can require $\Omega (k\log \log k)$. The lower bound applies to arbitrary approximate equilibria because every valid mixed output reveals hidden action labels. By contrast, every fixed-rank class has minimax discovery complexity $\Theta (k)$ in the same regime. Our fixed-rank upper bounds use response compression to learn strategic responses directly from noisy payoffs without supplied factors or anchors. For nontrivial $n\times m$ rank-one games, we obtain the exact minimax law $\Theta ((n+m){\epsilon }^{-2}\log (1/\delta ))$. Rank two retains linear dependence on $n+m$ and the optimal ${\epsilon }^{-2}$ accuracy exponent up to logarithmic factors. Finally, combining structured search, generic self-play, and independent verification retains these gains without knowing the rank while preserving correctness on every bounded game.