Certifying Exploitability at Learned Equilibria in Multi-player Games

We develop an amortized exploitability certificate for fixed points of learned response maps in games with compact convex product action sets and costs convex in each player's own action. We certify the exploitability of arbitrary strategy profiles with playerwise envelopes without requiring contraction, monotonicity, or uniqueness of equilibrium. Its two game-dependent quantities are each player's own-gradient norm and the consistency error between the learned response operator and the pseudo-gradient. Both are enveloped once by cost-oracle probes on a finite $\eta$-covering of the certified region $\Omega$. Subsequent profiles require only a forward pass. Two results delimit the scheme. Amortization is necessary: at a profile where every player's projection is inactive, a single probe cannot improve the model-free bound. Amortization is also costly: coverings at fixed accuracy grow exponentially with the dimension of $\Omega$. Across the two product-set games and seven response families, the certificate is valid in all $280$ theorem-supported cells; we report $140$ coupled-constraint cells separately as an out-of-scope stress diagnostic. Small-gain contraction certification is neither necessary nor sufficient for low exploitability in the models tested. Finally, on a nonconvex game the natural residual vanishes analytically at a profile of exploitability $1/4$, so that playerwise convexity cannot be dropped.