Poker and other games with hidden information are too large to solve in one pass. Strong systems compute a complete blueprint strategy offline and refine it in real time inside the reached subgame. In 2p0s games, a safety theorem guarantees that subgame resolving never increases how much an adversary can gain by exploiting the resolved strategy relative to the blueprint strategy. With three or more players acting independently, no such guarantee exists yet, and heuristic resolving can increase the profile's best-response gap. We prove the first conditional safety theorem for uncorrelated multiplayer subgame resolving, a post-hoc certificate for any delivered update. The best-response gap of the resolved profile exceeds that of the blueprint by at most four terms. Two concern the resolver: the subgame value the blueprint promised without realizing (AiS) and the resolver's subgame solve error (εi). The other two are the opponents' best-response gains inside the subgame over their promised values (∑qMq) and a structural tax (Θ), which measures how much the players' total utility can change. The tax is zero in constant-sum games, including every rake-free poker variant. Constructions attain each term with equality. On three-player Leduc poker and on Kuhn poker with up to six players, resolving without a certificate raises the gap beyond a small tolerance in 12% to 100% of the updates. The certificate flags every such update and accepts 41% (Kuhn) and 86% (Leduc) of the standard resolving updates. A resolver that keeps the blueprint whenever the certificate exceeds the tolerance delivers no harmful update. The certificate needs only one best-response pass per opponent inside the subgame, so real-time multiplayer solvers that refine a blueprint can attach it as a safety check. Code is available at https://github.com/lbn187/MultiPlayerSolver
Figures & tables
Figure 1: Subgame resolving and its certified guarantee. (a) Three-player game tree. The diamond is the chance node, squares and small circles are decision nodes of the opponents j and k , and dots are terminals. The blueprint σ0 (CFR) is kept outside the public state pub∗ . The resolver i updates it to σ1 inside the subgame S , where the entries E are grouped into entry information sets ιq . With two players, j ’s gain inside S is i ’s loss. With three, value can move between j and k ( Example 2 ). (b) The certificate on the same subgame. Thick edges are the actions the resolver plays, grey under σ0 and blue under σ1 . The blueprint leaves the value AiS(σ0) unrealized in S (orange). The gadget solve, where each opponent may terminate (T) for its blueprint value, has error εi (dark). The opponents’ best responses to σ1 (purple) give ∑qMq , and the terminals’ total utility (teal) gives Θ . These four terms bound the rise of the gap, ΔGap . The resolver plays σ1 when the bound is within the tolerance and keeps σ0 otherwise.
Game
Resolver
Median ΔGap
Harmful updates
Accepted at 0
Accepted at 0.02
Resolver gain
Max ΔGap after gating
Kuhn
best response
+0.0620
80%
0%
5%
+0.0164
+0.0068
Kuhn
standard gadget
+0.0096
29%
0%
41%
+0.0082
+0.0182
Kuhn
belief-corrected gadget
+0.0016
20%
0%
43%
+0.0087
+0.0170
Leduc
best response
+0.0000
12%
53%
80%
+0.0063
+0.0094
Leduc
standard gadget
+0.0000
2%
47%
86%
+0.0031
+0.0135
Leduc
belief-corrected gadget
-0.0000
2%
52%
87%
+0.0034
+0.0083
Table 1: Resolving outcomes on three-player Kuhn and Leduc poker, pooled over blueprints.
n
Resolver
Median ΔGap
Harmful updates
Accepted at 0.02
Resolve (s)
Certificate (s)
Exact evaluation (s)
3
best response
+0.0509
80%
0%
0.010
0.004
0.003
3
standard gadget
+0.0097
40%
40%
0.340
0.004
0.004
3
belief-corrected gadget
+0.0043
20%
60%
0.340
0.004
0.004
4
best response
+0.0489
100%
0%
0.080
0.048
0.048
4
standard gadget
+0.0221
57%
43%
9.82
0.062
0.057
4
belief-corrected gadget
+0.0028
43%
57%
9.56
0.062
0.058
Table 2: Kuhn poker with n=3,…,6 players: resolving outcomes and median wall-clock time per update.
Game
Activation term (s)
Margin pass (s)
Full certificate / exact evaluation
Margin pass / exact evaluation
3-player Kuhn
0.003–0.003
0.001–0.002
1.34–1.52
0.46–0.65
3-player Leduc
0.450–0.493
0.065–0.075
1.01–1.11
0.13–0.15
4-player Kuhn
0.030–0.041
0.015–0.031
1.17–1.26
0.32–0.64
5-player Kuhn
0.745–0.787
0.241–0.694
0.86–1.12
0.20–0.54
6-player Kuhn
15.1–17.9
4.48–16.5
0.76–1.24
0.17–0.59
Table 3: Cost of the certificate’s two parts, with ratios to the exact full-game evaluation (range over public states).
Game
Rake
Max Θ
Max Θ / utility scale
Max ∣Λ∣
Kuhn
0.0%
0.0000
0.0%
0.0000
Kuhn
2.5%
0.0702
1.8%
0.0010
Kuhn
5.0%
0.1381
3.7%
0.0008
Kuhn
10.0%
0.2858
8.4%
0.0010
Leduc
0.0%
0.0000
0.0%
0.0000
Leduc
2.5%
0.0730
0.5%
0.0012
Table 4: Structural tax Θ and realized leak ∣Λ∣ under a rake on three-player Kuhn and Leduc.
K
Cached exact (ms)
Local / cached
1
2.1
0.96×
4
8.1
0.25×
16
32.8
0.061×
64
145
0.014×
Table 5: Trunk scaling, median wall-clock time over six seeds with the subgame fixed at 6 information sets.
Certificate
Acc. 0
Acc. 0.02
Bdir ( Eq. 1 )
2
73
Bcache ( Corollary 3 )
37
104
X=Λ (realized leak)
0
72
X=Li (confined bound)
0
45
X=Θ (sharp tax)
0
19
X=2nδ∞ ( Corollary 6 )
0
2
Table 6: Acceptance of the 162 delivered campaign updates. Acc. t counts updates with B≤t .
Appendix figures & tables11 assets
Supplementary material from the paper’s appendix.
Appendix
j (trunk)
i (inside S )
ui
uj
d
⋅
−1
+1
enter
a′
0
0
enter
a
+1
−1
Appendix
Table 7: Payoffs of the activation construction ( Example 1 ).
i
j
ui
uj
uk
a′
stay
0
0
0
a′
d
0
0
0
a
stay
0
−1
+1
a
d
−1
0
+1
Appendix
Table 8: Total payoffs induced by Eq. 22 ( Example 2 ), where k has no action.
Game
Claimed bound
δ∞ convention
Relative scale
3-player Kuhn (deck 4)
δ∞≥1.0
restricted-support lower bound
≥0.250
blind Goofspiel K=3
δ∞=2.5
exact (216 profiles)
0.500
blind Goofspiel K=4
δ∞=4.625
exact (13,824 profiles)
0.514
observed Goofspiel K=3
δ∞≥3.0
restricted-support lower bound
≥0.500
Appendix
Table 9: Lower bounds on δ∞ certified by LP dual solutions.
blueprint
pub
i
ceπi
ce∏pπp
ceπ−q , opp. 1
ceπ−q , opp. 2
cfr200
b
2
-0.432 / -1.097
-0.386 / -0.102
-0.432 / -1.097
-0.386 / -0.102
cfr200
b
3
-0.433 / -0.688
-0.404 / -0.032
-0.433 / -0.688
-0.404 / -0.032
cfr200
k
1
-0.025 / -0.016
-0.025 / -0.016
-0.025 / -0.016
-0.025 / -0.016
cfr200
k
2
-0.023 / -0.027
-0.037 / -0.006
-0.023 / -0.027
-0.037 / -0.006
cfr200
k
3
+0.004 / -0.014
+0.004 / -0.016
+0.004 / -0.014
+0.004 / -0.016
cfr1000
b
2
-0.422 / -0.991
-0.015 / -0.029
-0.422 / -0.991
-0.015 / -0.029
Appendix
Table 10: Minimum gadget margin v(T)−v(F) of the two opponents (separated by a slash) on three-player Kuhn under four root measures.
Game
λ
#matched
mean ΔGap
harmful
mean gi
Kuhn
0.25
56
+0.0001
2%
+0.0020
Kuhn
0.50
56
+0.0038
9%
+0.0040
Kuhn
0.75
56
+0.0092
18%
+0.0061
Kuhn
1.00
56
+0.0159
29%
+0.0082
Leduc
0.25
540
-0.0007
0%
+0.0007
Leduc
0.50
540
-0.0010
1%
+0.0015
Appendix
Table 11: Shrinking the standard-gadget update toward the blueprint, (1−λ)σi0+λσi1 .
Quantity
count
replayed updates
162
violations of ΔNashConv≤∑qMq+Λ
0
violations of ΔNashConv≤∑qMq+Θ
0
updates with ΔGap≤0
53
updates with ΔNashConv≤0
119
ΔGap≤0 but ΔNashConv>0
0
Appendix
Table 12: NashConv replay of the 162 random-game updates.
Tier
Margin condition
δ∞ condition
Hits ( ΔGap>0.02 )
1 (strict)
margin≥0
δ∞≤0.10
0
2
margin≥−0.05
δ∞≤0.10
0
3
margin≥−0.05
δ∞≤0.15
0
4 (very loose)
margin≥−0.10
δ∞≤0.30
3 (each with δ∞≥0.05 or margin ≤−0.09 )
Appendix
Table 13: Counterexample filter tiers on the 433 screened points.
Source
Condition
c1
c2
Corollary 6
coefficients of δ∞ , ∑qMq ( n=3 )
6
1
Fitted (LP)
tol=0.02
1.76
0.31
Fitted (LP)
tol=0
2.35
0.17
Fitted (LP)
c2=0 pinned
≥2.64
0
Fitted (LP)
c1=0 pinned (margin-only)
infeasible
Appendix
Table 14: Minimum feasible constants of the two-term ablation on the 162 -instance attack set ( n=3 ).
Form
Cover
Slack med. / q90
Acc. 0 / 0.02 / 0.05 / 0.10
Time (ratio)
Bdir ( Eq. 1 )
162/162
0.018 / 0.22
2 / 73 / 85 / 113
1.3 ms ( 0.57× )
Bcache ( Corollary 3 )
162/162
0.020 / 0.22
37 / 104 / 122 / 143
1.2 ms ( 1.0×Bdir )
X=Λ (realized leak)
162/162
0.031 / 0.31
0 / 72 / 82 / 105
2.3 ms ( 1.05× )
X=Li (confined bound)
162/162
0.094 / 0.55
0 / 45 / 57 / 78
3.7 ms ( 1.6× )
X=Θ (sharp tax)
162/162
0.273 / 1.22
0 / 19 / 29 / 42
123 ms ( 28× )
X=2nδ∞ ( Corollary 6 )
162/162
1.007 / 2.34
0 / 2 / 3 / 6
2.16 s ( 381× )
Appendix
Table 15: Certificate usefulness on the 162 nominal updates.
K
Infosets
Full
Cached exact
Bdir , whole tree
Bdir , local
Whole tree / cached
Local / cached
1
12
5.5 ms
2.1 ms
2.8 ms
2.0 ms
1.35×
0.96×
2
24
11.1 ms
4.1 ms
4.3 ms
2.0 ms
1.06×
0.49×
4
48
22.4 ms
8.1 ms
7.6 ms
2.0 ms
0.93×
0.25×
8
96
46.4 ms
17.1 ms
13.8 ms
2.0 ms
0.83×
0.12×
16
192
90.9 ms
32.8 ms
27.6 ms
2.0 ms
0.82×
0.061×
32
384
189 ms
70.6 ms
54.4 ms
2.0 ms
0.77×
0.029×
Appendix
Table 16: Trunk scaling, median wall-clock time over six seeds for four evaluation methods.
ID
Implementation
Theorem convention
Consequence
D-a
Counterfactual action values normalized by the weight sum
Mq aggregates with unnormalized weights Wˉq(ι)
Per-infoset margin signs agree, while cross-infoset aggregation differs
D-b
Margin’s Follow-branch valued under the opponent’s own average strategy
Margin m^ valued against the exact subgame best response
Implementation margin optimistic on 33/40 infosets, worst overestimate +1.667
D-c
Follow-branch evaluated under the gadget-internal measure, which depends on the opponent ordering in the gadget chain (opponents’ gadgets nested one inside the next)
Both branches evaluated under the game-side measure ceπ−jσ0(e) and environment (σi1,σ−ij0)
Measures coincide only when entries follow a public chance node with no trunk actions and the other opponents play Terminate purely (the benchmark families)
D-d
Zero-denominator entry infosets fall back to a raw mean (flagged)
Assumes Wˉq(ι)>0
Such ι carry weight 0 in Mq
D-e
δ∞ LP defined on the reduced pure-strategy profile table
Same
A literal terminal-history-dependent witness would force δ∞≡0 on all zero-sum games, contradicting the Kuhn bound
D-f
LP constraint is per-edge constant-sum : upq(a,b)+uqp(b,a)=cpq
Same (constant-sum)
Proofs use only that ∑pup is constant on the class
Appendix
Table 17: Definitional conventions of the implementation and of the theorem.
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.
Boning Li, Longbo Huang
Institute for Interdisciplinary Information Sciences, Tsinghua University
The standard game-theoretic solution concept, Nash equilibrium, assumes that all players behave rationally. If we follow a Nash equilibrium and opponents are irrational (or follow strategies from a different Nash equilibrium), then we may obtain an extremely low payoff. On the other hand, a maximin strategy assumes that all opposing agents are playing to minimize our payoff (even if it is not in their best interest), and ensures the maximal possible worst-case payoff, but results in exceedingly conservative play. We propose a new solution concept called safe equilibrium that models opponents as behaving rationally with a specified probability and behaving potentially arbitrarily with the remaining probability. We prove that a safe equilibrium exists in all strategic-form games (for all possible values of the rationality parameters), and prove that its computation is PPAD-hard. We present exact algorithms for computing a safe equilibrium in both 2 and n-player games, as well as scalable approximation algorithms.
Many important games have more than two players and imperfect information. Existing approaches for computing Nash equilibrium, the central game-theoretic solution concept, in such games either lack scalability or obtain poor performance. In this paper we introduce a new algorithm called projected exploitability descent (PED) for approximating Nash equilibria in multiplayer games of imperfect information. The algorithm works by running projected subgradient descent minimizing a proxy for the multiplayer generalized exploitability function. The objective is nonconvex and nonsmooth, but can be represented as the sum of the maxima of linear functions, for which a subgradient can easily be computed and projected to the polytope of feasible sequence-form strategies. We explore performance of PED on a generalized version of the well-studied benchmark game three-player Kuhn poker. No prior exact algorithms scale to the version of the game with deck size larger than 4, and we compare performance to the popular algorithms of fictitious play (FP) and counterfactual regret minimization (CFR). We find that PED obtains a consistent near-monotonic improvement throughout all runs, though both FP and CFR perform significantly better in the initial iterations. This inspires a hybrid algorithm FP-PED that runs FP for an initial burn-in period before switching to PED for stable long-run refinement. We can alternatively view this as a multi-step algorithm that runs FP as a pre-processing step to obtain a strong initialization for PED.