When Are We Near Nash? Certifying Solutions in General-Sum Games

Boning Li; Longbo Huang

cs.GTOct 21, 2026

When Are We Near Nash? Certifying Solutions in General-Sum Games

Authors: Boning Li, Longbo Huang

Organizations: Institute for Interdisciplinary Information Sciences, Tsinghua University

Abstract

Heuristic solvers for general-sum extensive-form games produce a stream of iterates, and practice reports the NashGap of the returned profile. We ask what a solver can know about its own iterates from the regret accumulators and the terminal-distribution accumulators its updates already maintain. In two-player games the NashGap of a weighted average strategy equals, at the maximizing player, the weighted external regret plus a signed value correction. Bounding the regret by the running counterfactual-regret accumulator gives an online certificate whose cost per checkpoint is linear in the number of terminal histories. The certificate stays sound under alternating updates and in games with three or more players. The mismatch between what alternation evaluates and what the averages record enters as one signed comparator term, maximized in a single backward pass per player whose comparator weight is nonzero. The bound is read off the regret state, with no best response against the average. Run a portfolio of training-free regret-matching solvers, output the iterate with the smallest certificate, and verify that iterate once. On the benchmark's biased Leduc family a pool of sixteen training-free solvers, seven original and nine recent variants, solves $89\%$ of the $64$ instances at threshold $10^{-5}$ this way, matching the trajectory-minimum union of the solvers. The same protocol solves $92\%$ of the $64$ pre-registered held-out instances and $89\%$ again on a third set of $64$ instances that no earlier stage used. The zero-best-response certificate certifies all $57$ in-sample solves and all $57$ fresh ones, and $58$ of the $59$ held-out ones. Its exact-comparator refinement certifies every solve in the three sets. The certificate states both and attributes its bound. Code is available at https://github.com/lbn187/CertNE.

Figures & tables

Figure 1: Two selection protocols on the same

K

solvers and

m

checkpoints per solver. a, Exact evaluation scores every candidate with

n

best-response (BR) passes, costing

Kmn

passes overall, and outputs the minimum-gap strategy with its exact gap. b, Online certification combines signed regret, value correction, and comparator terms (Proposition 9 ).

C^{0}

uses accumulators alone;

C^{1}

adds one signed backward pass per player with nonzero comparator weight at each checkpoint. Either certificate selects its own argmin across solvers and checkpoints and bounds the selected strategy’s NashGap. Optional verification evaluates only that strategy, with

n

BR passes (Corollary 10 ). Nodes, trees and policy glyphs are schematic; arrows on trees indicate backward traversal.

Reported
	fraction of games with NashGap $\leq$
Method	$10^{-2}$	$10^{-3}$	$10^{-4}$	$10^{-5}$
CFR +	$1$	$0$	$0$	$0$
PCFR +	$1$	$0.87$	$0.48$	$0.16$
NPCFR + (oracle)	$1$	$0.98$	$0.96$	$\mathbf{0.96}$
Controls (outside the pool)

Table 1: Biased Leduc, solved fractions at four thresholds on the

64

paired instances. Reported rows are figures of Sychrovský et al. (2026) ; the rest are our runs. Single-solver rows are trajectory-minimum oracles. Selection rows give exact gaps, and certified rows count certificates below the threshold. Control rows are outside both portfolios; the full names of the added solvers are in Appendix E .

Figure 2: Tightness over the

16\times 64\times 128

biased-Leduc checkpoints whose exact gap is above floating-point zero (excludes

3{,}223

checkpoints, all but

31

on HS-PCFR + ): an ECDF of certificate over true NashGap for

C^{1}

and

C^{0}

(Proposition 9 ), the aligned start-of-round certificate, and the unaligned shortcut of Corollary 5 under alternation. Sound certificates lie at ratio

\geq 1

. Iteration traces are in Figures 4 and 5 .

Added solvers
Solver	min NashGap	at $t$	$C^{1}$ at $T$	ratio	$C^{0}$	ratio	$MD$ form
PDCFR + , $p{=}5$	$\mathbf{1.17\times 10^{-6}}$	$59392$	$3.26\times 10^{-6}$	$2.41\times$	$1.73\times 10^{-5}$	$12.8\times$	$8.59\times 10^{-5}$
HS-PCFR +	$2.16\times 10^{-6}$	$T$	$\mathbf{2.83\times 10^{-6}}$	$1.31\times$	$2.83\times 10^{-6}$	$1.3\times$	$2.85\times 10^{-6}$
Stable PRM + , $p{=}2$	$1.59\times 10^{-5}$	$T$	$4.29\times 10^{-5}$	$2.70\times$	$3.76\times 10^{-4}$	$23.7\times$	$1.02\times 10^{-3}$
DCFR + , $p{=}4$	$7.68\times 10^{-5}$	$33792$	$3.25\times 10^{-4}$	$3.75\times$	$4.08\times 10^{-3}$	$47.1\times$	$1.57\times 10^{-2}$
DCFR, $p{=}2$	$1.11\times 10^{-4}$	$15360$	$7.68\times 10^{-4}$	$3.34\times$	$9.05\times 10^{-3}$	$39.4\times$	$3.60\times 10^{-2}$

Table 2: Three-player Leduc (

T=2^{16}

, deterministic single runs). The min NashGap column is the trajectory minimum with the checkpoint

t

at which it is attained;

C^{1}

C^{0}

and the

MD

relaxation are the certificates of Proposition 9 at

T

, with ratios to the true gap at

T

. All solvers use alternating updates. Reported rows are from Table 6 of Sychrovský et al. (2026) ; n/a marks quantities that study does not publish.

Figure 3: Slack attribution on three-player Leduc (PRM + ,

p{=}2

, alternating, log–log). The

MD_{-i}

form of the certificate sits

11.7

–

241\times

above the true NashGap over training; the zero-BR

C^{0}

replaces

MD_{-i}

\lVert w_{i}\rVert_{1}

and tightens it to

2.9

–

59\times

; the exact comparator

C^{1}

(one backward pass per player per checkpoint) reaches

1.39

–

5.2\times

Protocol	Exact-gap queries	Guarantee
Selection by $C^{0}$	$0$	Layer II bound
Selection by $C^{1}$	one signed backward pass per checkpoint under two-player alternation; $0$ for simultaneous updates	Layer II bound
One-shot verification	$1$	exact $\mathrm{NashGap}(\hat{\sigma})$
Trajectory minimum	per checkpoint	evaluation protocol

Table 3: Verification budgets (one gap evaluation equals

n

best-response passes).

C^{1}

spends one signed backward pass per player whose comparator weight is nonzero, the second mover alone under two-player alternation.

C^{1}

’s pass maximizes a logged linear functional, not a best response against the average; one-shot verification is exact for the selected snapshot. The oracle protocol uses about

19

evaluations on the reference schedule and

128

on our dense two-player grid.

C^{1}

costs nothing extra when the comparator weight vanishes, as it does for simultaneous updates in two-player games.

	Ours, $C^{0}$ / $C^{1}$	Ours, aligned	Reported
	(Prop. 9 )	(extra pass)	NPCFR +
Training trajectories	$16$ solvers	$16$ solvers	$1$
Instances	$64$ (paired)	$64$ (paired)	not stated
Iterations per run	$2^{18}$	$2^{18}$	$2^{18}$
Tree passes per iteration	$n{=}2$	$2n{=}4$	not reported
Candidate snapshots	$16\times 128{=}2048$	$16\times 128{=}2048$	$\approx 19$

Table 4: Compute budget behind Table 1 (biased Leduc). One gap evaluation equals

n{=}2

best-response passes, and the timed policy is PRM + ,

p{=}2

. The isolated block times each term alone on one core outside the training loop; the end-to-end and checkpoint-work blocks time full runs with three repeats per policy in shuffled order (

\mathrm{mean}\,[\min,\max]

). n/a marks a cell the measurement does not cover; “not reported” marks a value the reference does not publish. The bare solver, exact-gap selection row is a later re-measurement, with the uninstrumented baseline of its own batch at

81.9

Layer	BR cost	Status
I. Exact identity (2p)	exact $\bar{R}$	equality; not a deployment signal
II. $C^{0}$ , zero-BR certificate	$0$	theorem-backed upper bound, any update order and $n$
II. $C^{1}$ , exact comparator	$1$ signed pass per player with $w_{i}\neq 0$ , per ckpt.	theorem-backed upper bound; tighter
II. Aligned start-of-round bound	$1$ extra regret pass per player per iteration	theorem-backed upper bound; looser (ablation)
III. One-shot verification	$1$ gap	exact selected gap only
Trajectory minimum	per ckpt.	post-hoc evaluation protocol

Table 5: The three guarantee layers, with their best-response cost and status. One gap evaluation equals

n

best-response passes.

	$7$ solvers (Stage 1)		$16$ solvers (Stage 2)
Selector	seeds $0$ – $63$	seeds $64$ – $127$	seeds $0$ – $63$	seeds $64$ – $127$
$C^{1}$ selection	$54/64$ $[0.74,0.91]$	$56/64$ $[0.77,0.94]$	$57/64$ $[0.81,0.97]$	$59/64$ $[0.83,0.97]$
$C^{0}$ selection	$54/64$	$56/64$	$57/64$	$59/64$
Value-corrected $\max_{i}[\widehat{R}_{i}+\Delta^{(i)}_{i}]$	$54/64$	$56/64$	$57/64$	$59/64$
Exact-gap selection, same grid	$54/64$	$56/64$	$57/64$	$59/64$
Regret-only selection	$53/64$	$54/64$	$49/64$	$56/64$

Table 6: Solved counts at

10^{-5}

on the in-sample and held-out instance sets for the seven-solver pool of Stage 1 and the sixteen-solver pool of Stage 2, all from the stored checkpoint histories; brackets on the

C^{1}

rows are the frozen migration bands (in-sample) and

95\%

Wilson intervals (held-out). The

C^{0}

and value-corrected rows are diagnostic ablations; the frozen selectors are

C^{1}

, regret-only and exact-gap.

Selector	$7$ solvers	$16$ solvers
$C^{1}$ selection	$55/64$	$57/64$ $[0.81,0.97]$
$C^{0}$ selection	$54/64$	$57/64$
Value-corrected $\max_{i}[\widehat{R}_{i}+\Delta^{(i)}_{i}]$	$55/64$	$57/64$
Exact-gap selection, same grid	$55/64$	$57/64$
Regret-only selection	$55/64$	$53/64$
Certified $C^{1}$	$54/64$	$57/64$

Table 7: Solved counts at

10^{-5}

on the fresh instance set (seeds

128

–

191

, Stage 3) for the seven-solver pool and the sixteen-solver pool, from the stored checkpoint histories; the bracket on the

C^{1}

row is the frozen band and the row definitions are those of Table 6 .

Instance set	Median	$90$ th pct.	Max	Excluded
In-sample	$1.01$	$1.36$	$42.45$	$28$
Held-out	$1.01$	$2.67$	$33.11$	$26$
Fresh	$1.00$	$1.74$	$17.07$	$25$

Table 8: Selected gap relative to the exact trajectory minimum, per instance (sixteen-solver pool; in-sample seeds

0

–

63

, held-out

64

–

127

, fresh

128

–

191

). The ratio is reported over the instances whose minimum is above

10^{-12}

; “excluded” counts the remaining instances, on all of which the selected gap is also at or below

10^{-12}

Figure 4: Failure analysis (biased Leduc, sixteen-solver pool, threshold

10^{-5}

). (a) NashGap at the

C^{1}

-selected iterate versus tie-refund fraction

\beta

; the dotted line is the threshold, and the cluster at

10^{-15}

is floating-point zero, where HS-PCFR + is selected. (b) On the seven unsolved instances,

C^{1}

against the true gap, with the

1\times

and

2\times

lines.

Figure 5: Certificates over training (biased Leduc, PRM +

p{=}2

, median and interquartile band over

64

instances, log–log): the true NashGap,

C^{1}

C^{0}

, the aligned start-of-round certificate and the Pinsker bound of Proposition 3 .

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Pool	solvers	selection $C^{1}$	certified $C^{1}$	certified $C^{0}$	aligned	oracle union
PRM + -core	$3$	$0.80$	$0.72$	$0.70$	$0.77$	$0.80$
no DPRM +	$4$	$0.70$	$0.64$	$0.64$	$0.67$	$0.70$
original	$7$	$0.84$	$0.75$	$0.73$	$0.80$	$0.84$
$+$ discounting	$10$	$0.84$	$0.77$	$0.77$	$0.81$	$0.84$
$+$ schedules	$9$	$0.84$	$0.77$	$0.73$	$0.81$	$0.84$
$+$ stabilised RM +	$10$	$0.88$	$0.88$	$0.88$	$0.88$	$0.88$

Appendix

Table 9: Pool ablation at threshold

10^{-5}

(biased Leduc,

n{=}64

paired). PRM + -core contains PRM + with

p\in\{1,2\}

and DPRM + with

p=2,\lambda=0.3

; no DPRM + contains RM + and PRM + with

p\in\{1,2\}

; original contains the seven solvers of the first stage; the “

+

” rows add one family of the extension to them (discounting: DCFR, DCFR + , PDCFR + ; schedules: HS-PCFR + , HS-DCFR; stabilised: Smooth PRM + , Stable PRM + , ExRM + ); all contains the sixteen solvers. Selection is the exact gap at the cross-solver

C^{1}

argmin, certified columns count instances whose selected certificate is below the threshold, aligned is selection by the start-of-round certificate, and oracle union is the pool’s best trajectory minimum, which exact-gap selection on the same grid attains.

Threshold	$C^{1}$ selection	Oracle union	Aligned selection	Certified $C^{1}$	Certified $C^{0}$
$10^{-2}$	$64$ ( $64$ )	$64$ ( $64$ )	$64$ ( $64$ )	$64$ ( $64$ )	$64$ ( $64$ )
$10^{-3}$	$64$ ( $64$ )	$64$ ( $64$ )	$64$ ( $64$ )	$64$ ( $64$ )	$64$ ( $64$ )
$10^{-4}$	$62$ ( $58$ )	$62$ ( $58$ )	$62$ ( $58$ )	$62$ ( $57$ )	$62$ ( $56$ )
$10^{-5}$	$57$ ( $54$ )	$57$ ( $54$ )	$57$ ( $51$ )	$57$ ( $48$ )	$57$ ( $47$ )

Appendix

Table 10: Solved counts (of

64

paired biased-Leduc instances) at each threshold for

C^{1}

selection, the solvers’ trajectory-minimum union, selection by the aligned start-of-round certificate, and the certified counts; the sixteen-solver pool, with the seven-solver counts in parentheses.

Solver	$10^{-2}$	$10^{-3}$	$10^{-4}$	$10^{-5}$	select
RM + , $p{=}1$	$1.00$	$0.50$	$0.00$	$0.00$	$0.00$
RM + , $p{=}2$	$1.00$	$0.52$	$0.00$	$0.00$	$0.00$
PRM + , $p{=}1$	$1.00$	$1.00$	$0.88$	$0.67$	$0.67$
PRM + , $p{=}2$	$1.00$	$1.00$	$0.89$	$0.70$	$0.70$
DPRM + , $p{=}1$ , $\lambda{=}0.3$	$1.00$	$1.00$	$0.88$	$0.73$	$0.73$
DPRM + , $p{=}2$ , $\lambda{=}0.1$	$1.00$	$1.00$	$0.88$	$0.67$	$0.67$

Appendix

Table 11: Per-solver solved fractions, biased Leduc,

n{=}64

paired instances,

T=2^{18}

. The first four columns are the oracle trajectory-minimum protocol; the last column reports the

C^{1}

-argmin extractable fraction within that solver alone, at threshold

10^{-5}

( n/a on the two portfolio rows, which are not single solvers). All solvers use alternating updates except ExRM + (simultaneous).

Solver	$C^{1}$	aligned	regret-only	$\widehat{R}{+}\Delta^{(i)}$	final	random	oracle
RM + , $p{=}1$	$0.00$	$0.00$	$0.00$	$0.00$	$0.00$	$0.00$	$0.00$
RM + , $p{=}2$	$0.00$	$0.00$	$0.00$	$0.00$	$0.00$	$0.00$	$0.00$
PRM + , $p{=}1$	$0.67$	$0.67$	$0.67$	$0.67$	$0.66$	$0.57$	$0.67$
PRM + , $p{=}2$	$0.70$	$0.67$	$0.70$	$0.70$	$0.67$	$0.60$	$0.70$
DPRM + , $p{=}1$ , $\lambda{=}0.3$	$0.73$	$0.72$	$0.72$	$0.73$	$0.70$	$0.55$	$0.73$
DPRM + , $p{=}2$ , $\lambda{=}0.1$	$0.67$	$0.64$	$0.66$	$0.67$	$0.62$	$0.51$	$0.67$

Appendix

Table 12: Per-solver selection-policy ablation at threshold

10^{-5}

(computed from the stored checkpoint histories; see the text above for the policy definitions). Random values are expectations over one uniform checkpoint draw.

Game	pool	solver	$C^{1}$ select.	certified $C^{1}$	oracle	ratio
		best	portfolio
Sheriff	$7$ solvers	$1.00$	$1.00$	$1.00$	$1.00$	$11.4\times$
	$16$ solvers	$1.00$	$1.00$	$1.00$	$1.00$	n/a
Goofspiel GS( $5$ )	$7$ solvers	$0.50$	$0.56$	$0.45$	$0.58$	$8.3\times$
	$16$ solvers	$0.53$	$0.62$	$0.58$	$0.64$	$2.0\times$

Appendix

Table 13: External validity at threshold

10^{-5}

(

n=64

paired instances per game,

T=2^{16}

; the seven-solver pool of the first stage and the sixteen-solver pool). “Best solver” is the strongest solver’s oracle fraction; selection is the exact gap at the cross-solver

C^{1}

argmin; certified counts instances whose selected

C^{1}

is below the threshold; oracle is the pool union, attained by exact-gap selection on the same grid; ratio is the median of

C^{1}

over the exact gap at the selected iterate, over instances whose selected gap is above

10^{-12}

; n/a marks the Sheriff sixteen-solver cell, where every selection gap is below it. Table 14 gives all solvers.

Sheriff
Solver	oracle	$C^{1}$ select.	certified	ratio
RM + , $p{=}1$	$0.42$	$0.38$	$0.00$	$3.0\times$
RM + , $p{=}2$	$0.53$	$0.42$	$0.00$	$2.9\times$
PRM + , $p{=}1$	$1.00$	$1.00$	$1.00$	$17.2\times$
PRM + , $p{=}2$	$1.00$	$1.00$	$1.00$	$12.1\times$
DPRM + , $p{=}1$ , $\lambda{=}0.3$	$1.00$	$1.00$	$1.00$	$16.0\times$

Appendix

Table 14: Per-solver external-validity results at threshold

10^{-5}

(

n{=}64

paired instances per game,

T=2^{16}

, alternating updates except ExRM + ). Columns as in Table 13 ; per-solver “select.” picks that solver’s own

C^{1}

-argmin checkpoint, “certified” is the fraction whose selected

C^{1}

is below the threshold, and “ratio” is the median of

C^{1}

over the exact gap there; n/a marks a cell whose selected gaps are all below

10^{-12}

. The portfolio row selects across solvers, and its oracle column is the pool’s oracle union.

Nash Equilibrium Computation

Nash equilibrium computation develops algorithms for finding stable strategies in strategic, stochastic, and imperfect-information games.

See all 70 papers

Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes
Jun 26, 2026Luis LealNash Equilibrium Imperfect-Information Games
IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence
Oct 13, 2026Michael Sullins, Ian A. KashCounterfactual Regret Minimization Regret Minimization
University of Illinois Chicago, Chicago, Illinois, USA
Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
Sep 30, 2025Sam GanzfriedNash Equilibrium Imperfect-Information Games
Ganzfried Research

Jun 26, 2026J/K move · Enter open · S save

Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes

Luis Leal

Nash Equilibrium Imperfect-Information Games Zero-Sum Games Regret Minimization Nash Equilibrium Computation

Open paper AskPDF arXiv

Many two-player zero-sum games admit not a unique Nash equilibrium but a convex set of them: a polytope of profiles that all share the minimax value V* yet prescribe different behaviour. Standard solvers each converge to some equilibrium and are treated as interchangeable. We ask whether they instead select different members of the Nash set, systematically as a function of the algorithm rather than the seed. Using a tabular, exactly solvable testbed of six games with analytically known Nash sets -- including a two-dimensional Nash polytope and Kuhn poker -- we find that (i) selection is determined by the algorithm, not the seed, but families differ only on asymmetric Nash sets; (ii) regularized last-iterate methods (R-NaD, magnetic mirror descent) select the maximum-entropy member, the information projection of their uniform reference onto the Nash set -- exactly on the 2-D polytope and at 99.7% of maximum entropy in Kuhn -- while regret-averaging methods (CFR, CFR+, fictitious play) drift to a lower-entropy face; we confirm this on a randomized 180-game ensemble, where R-NaD attains the maximum-entropy member in 100% of converged games while CFR+ sits strictly below it in 94% (paired Wilcoxon p < 10^-27); (iii) the selected member has downstream consequences against sub-optimal opponents that scale with sequential/hidden-information structure but stay bounded -- in Kuhn the max-entropy member is a strictly better hedge, whereas on the matrix games the members differ without either dominating. We also report two negative results correcting common intuitions: removing CFR's positive-orthant (max(R,0)) projection does not eliminate boundary drift; and R-NaD's selection is anchor-following, not initialization-independent. We state the maximum-entropy / I-projection characterization as a strongly data-supported conjecture, checked throughout against analytic ground truth.

Abstract

Nash Equilibrium Computation

Explore similar work

Which Nash Equilibrium? Solver-Dependent Selection on Zero-Sum Nash Polytopes

IR-PRM+ with Previous-Utility Prediction: Constant Regret and Best-Iterate Convergence

Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games