acceptodds
Under review as a conference paper at ICLR 2027

Certified Resolving at Every Seat: Constructive Safety Certificates for Multiplayer Subgame Resolving

Abstract

Exact solving of an imperfect-information game does not scale, so the standard recipe computes a blueprint offline by regret minimisation and recomputes the strategy inside the subgame play actually reaches. In two-player zero-sum games a gadget makes resolving safe: it lets the opponent cash in, at every entry, the counterfactual value it was guaranteed under the blueprint, so any equilibrium of it refines the blueprint without raising its exploitability. That guarantee rests on the zero-sum identity, which is gone as soon as a third seat is added: an unguarded update can leave the profile more exploitable than the blueprint. What survives is a per-player charge against the blueprint, anchored at the opponents' subgame best-response values. The charge is a maximum of affine functions of the resolver's sequence-form strategy, so the bound on the profile's Nash gap, the largest best-response gain over the players, is convex and piecewise linear; minimising it or maximising the resolver's own payoff under a Nash-gap budget is a linear program. The minimum-certificate program is the value of a two-player zero-sum gadget whose meta-adversary picks the victim, solvable by counterfactual regret minimisation. This gives a subgame-local resolver for independent strategies in multiplayer games whose every update carries an explicit certificate on the Nash gap of the whole profile. In constant-sum games the certified gain is at most plus the opponents' Nash-gap slack minus the shift of their best-response values, and three-player Kuhn instances attain it to six decimal places. A two-sided variant equals the exact safety constraint whenever no opponent acts before the subgame. Every seat can run the same program, and a ledger of certified gains keeps the joint bound monotone under round-robin certified resolving. Across 3-player Kuhn, 3-player Leduc, and random games with up to six players, certified updates never exceed their certificate beyond the solver tolerance of ; re-anchoring cuts the Nash gap by – on 3-player Kuhn. Unsafe resolving raises the Nash gap in – of configurations, by up to , while under the common clipped budget the certified gain matches or beats the unsafe gain in of the poker configurations. Safety becomes an objective a resolver can optimise against, priced by the cap identity and the gap decomposition.

Primary area:
reinforcement learning
Keywords:
game solving, game theory, subgame reolving

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_VbB5OpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies subgame resolving in multiplayer imperfect-information extensive-form games. The standard recipe computes a blueprint offline by regret minimisation and recomputes the strategy inside the reached subgame online. In two-player zero-sum games a gadget makes resolving safe (Burch et al., 2014): it lets the opponent cash in the counterfactual value guaranteed under the blueprint, so any equilibrium of the gadget refines the blueprint without raising exploitability. That guarantee rests on the zero-sum identity, which fails with three or more players: an unguarded update can leave the profile more exploitable than the blueprint, and Pluribus resolves with no guarantee at all. The paper turns the post-hoc bound on a single update into a constructive optimisation target. Anchored at the opponents' subgame best-response values against the blueprint, each deficit is a maximum of affine functions of the resolver's sequence-form strategy, so the certificate is convex and piecewise linear (Proposition 2); minimising it, or maximising the resolver's payoff under a Nash-gap budget, is a linear program confined to the subgame. The minimum-certificate program is the value of a two-player zero-sum gadget whose meta-adversary picks the victim (Theorem 1), solvable by counterfactual regret minimisation. For constant-sum games a cap identity prices certified safety exactly: a τ-safe update by one seat gains at most (n − 1)τ plus the opponents' slack minus the shift of their best-response values (Theorem 2). A two-sided certificate coincides with the exact whole-game safety constraint whenever no opponent acts before the subgame (Corollary 1), and the gap decomposition accounts for the three terms the one-sided certificate gives up (Proposition 4). Seats running the same program in turn produce a joint bound on the whole profile, with a ledger keeping it monotone under round-robin resolving (Section 6). Experiments on 3-player Kuhn (54 configurations), 3-player Leduc (160), and random stage games with three to six players (160), across six budgets, show that 2,244 certified updates never exceed their certificate beyond the solver tolerance of 10⁻⁹; unsafe resolving raises the Nash gap in 18–70% of configurations by up to 0.17; under a common clipped budget the certified gain matches or beats the unsafe gain in 176 of 214 poker configurations; and re-anchored round-robin resolving cuts the Nash gap by 41–57% on 3-player Kuhn.

Critical strengths

1.The central idea is a genuine step forward: the certificate is no longer a post-hoc check but an optimisation target. Proving convexity and piecewise linearity of the anchored certificate in the resolver's sequence-form strategy (Proposition 2) and showing the minimum-certificate program is the value of a two-player zero-sum gadget (Theorem 1) connects the safety problem to linear programming and regret minimisation in a clean and useful way. 2. The cap identity (Theorem 2) is elegant and exact: for constant-sum games it prices certified safety tightly, with equality conditions stated, and Corollary 2 gives the certified-cap bound; the constant-sum pricing is attained on Kuhn to 10⁻⁶. 3.The localisation analysis is careful: Proposition 3 and Corollary 1 characterise exactly when the one-sided certificate coincides with the whole-game safety constraint (no opponent acts before the subgame), and Proposition 4 decomposes the gap into clipping, reach, and re-optimisation terms — a genuinely informative account of what localisation costs. 4.The multi-seat extension is a valuable systems contribution: round-robin certified resolving with a monotone ledger gives a joint bound on the whole profile, and the stopping characterization (certificate-stable but not necessarily equilibrium) is stated honestly (Observation 1, Section 6). 5.The experiments are comprehensive for the scale used: 374 configurations, 2,244 certified updates with no certificate violation beyond 10⁻⁹, three families (Kuhn, Leduc, stage games up to six players), six budgets, exact full-tree scoring (no sampling error), and meaningful baselines (unsafe full-continuation CFR, a naïve robust gadget, and the blueprint), plus W/T/L comparisons under a common budget.

Critical weaknesses
  1. The relationship to very closely related concurrent work needs clarification. The paper's starting point is a post-hoc bound on a single update that is nearly identical to the main theorem of a closely related paper on multiplayer subgame-resolving safety (same anchored margins, same vulnerability/Nash-gap object, same four-channel structure). As an independent submission, the paper should state crisply what is novel relative to that line of work (constructive optimisation, gadget equivalence, cap identity, multi-seat ledger) and whether the two papers share authors; if they do, the overlap should be disclosed and the independent contribution of each made explicit. 2.The guarantee remains conditional and budget-dependent. Certified resolving controls the Nash gap only up to a user-chosen budget τ, and at τ = 0 a strictly positive certified gain exists in only 50–78% of configurations. The round-robin dynamics stops at certificate-stable profiles that need not be equilibria. The paper should help the reader understand when the method actually improves play in a deployed system, versus when it merely certifies a conservative non-improvement.
Questions for authors
  1. Can you demonstrate the certified-resolving pipeline on a realistic-scale multiplayer setting (e.g., a six-player poker-style subgame under abstraction), or provide a complexity/scaling analysis of the LP and CFR-on-gadget solvers as the subgame and opponent count grow?
  2. How does the cap identity and the certified gain degrade away from constant-sum structure? Please quantify the behaviour in non-constant-sum games (e.g., with rakes), where the exact pricing no longer applies.
3 comments

Thank you for your careful and accurate reading of our paper and your constructive questions.

Weakness 1

The relationship to very closely related concurrent work needs clarification. The paper's starting point is a post-hoc bound on a single update that is nearly identical to the main theorem of a closely related paper on multiplayer subgame-resolving safety (same anchored margins, same vulnerability/Nash-gap object, same four-channel structure). As an independent submission, the paper should state crisply what is novel relative to that line of work (constructive optimisation, gadget equivalence, cap identity, multi-seat ledger) and whether the two papers share authors; if they do, the overlap should be disclosed and the independent contribution of each made explicit.

The closely related paper is the ICLR submission "Safe Subgame Resolving in Multiplayer Games". A second related work is "Test-time Reinforcement Learning in Imperfect Information Games" (arXiv 2608.30635). We share no author with either. Both precede ours and we knew both when writing. The citation was missing because the first paper had no public version at that time, and we apologise for the confusion. The revision cites both in Section 1 (revised lines 59-60) and in the new paragraph "Closest work" of Section 2 (revised lines 148-156).

The first paper bounds an update after it is delivered, with margins anchored at counterfactual values. We anchor at best-response values, which certifies the blueprint itself, and we turn the bound into something a resolver optimises: a linear program (Proposition 2), a zero-sum gadget (Theorem 1), an exact price (Theorem 2) and a multi-seat ledger (Section 6).

The second work carries gadget safety to test-time reinforcement learning in two-player zero-sum games, where the two seats' gains cancel. Our certificate is for three or more seats, where that identity fails.

Weakness 2

The guarantee remains conditional and budget-dependent. Certified resolving controls the Nash gap only up to a user-chosen budget τ, and at τ = 0 a strictly positive certified gain exists in only 50–78% of configurations.

The budget τ\tau is the user's choice, and zero is a valid choice; none of the 2,244 certified updates in our main table exceeds its certificate, so at τ=0\tau=0 the Nash gap does not rise beyond solver tolerance. We added an experiment on small budgets. The shortfall at τ=0\tau=0 is specific to the zero budget, and a budget of τ=10−4\tau=10^{-4} already recovers most of the exact-safe gain.

τ=0\tau=0τ=10−4\tau=10^{-4}τ=5×10−4\tau=5\times10^{-4}τ=5×10−3\tau=5\times10^{-3}
Kuhn: median certified gain / exact-safe gain0.370.730.830.93
Kuhn: share of configurations with positive certified gain0.780.910.960.96
Leduc: median certified gain / exact-safe gain0.820.950.970.99
Leduc: share of configurations with positive certified gain0.710.850.860.86

The exact-safe gain is the best gain any whole-game-safe update can have, so the first row of each game says how much of it the certificate keeps (Appendix C of the revision, Table 12, line 1307).

The round-robin dynamics stops at certificate-stable profiles that need not be equilibria.

Observation 1 (Section 6, submitted lines 408-412, revised lines 465-469) states this, and Section 6 gives the reason: at budget 0 a certified gain has to be bought from a victim that holds slack. What the dynamics deliver is a monotone Nash-gap bound that holds at every step (Proposition 6) together with a lower Nash gap in practice. On 3-player Kuhn, re-anchored round-robin resolving lowers the full-game Nash gap from 0.037 to between 0.016 and 0.022 (a reduction of 41% to 57%).

The paper should help the reader understand when the method actually improves play in a deployed system, versus when it merely certifies a conservative non-improvement.

We added an analysis of when the method improves play. Two quantities read from the blueprint before play predict a positive certified gain at τ=0\tau=0: whether the resolver holds a largest best-response gain, and the victims' total slack.

FamilyResolver is not a largest-gain seatResolver is a largest-gain seat
Kuhn (3 players)0.75 (27 of 36)0.83 (15 of 18)
Leduc (3 players)0.62 (66 of 107)0.91 (48 of 53)
Stage games, n=3n=30.33 (9 of 27)1.00 (13 of 13)
Stage games, n=4n=40.41 (11 of 27)1.00 (13 of 13)
Stage games, n=5n=50.63 (20 of 32)1.00 (8 of 8)
Stage games, n=6n=60.43 (15 of 35)1.00 (5 of 5)

Across all 374 main-table configurations at τ=0\tau=0, a resolver at a largest-best-response-gain seat achieves a higher positive-gain share in all six families, reaching 1.00 on every stage-game family (n=3n=3 to 66) and 0.91 (48 of 53 configurations) on 3-player Leduc.

Victims' total slacklowest thirdmiddle thirdhighest third
Kuhn (3 players)0.670.720.94
Leduc (3 players)0.610.710.92

Sorting the 54 3-player Kuhn and 160 3-player Leduc configurations by the victims' total slack raises the positive-gain share monotonically from 0.67 and 0.61 in the lowest third to 0.94 and 0.92 in the highest third, matching Corollary 2 (submitted lines 364-366, revised lines 408-410): at τ=0\tau=0, a seat can only buy gain from victims that hold slack.

In our deployment view (Appendix C), each victim best-responds to the delivered profile and we record the resolver's payoff change against that best response, minimised over victims. At τ=0\tau=0, the certified update gains without raising the Nash gap far more often than the unsafe update, and its worst loss against a best-responding victim is smaller.

GameUpdateConfigurations where it gains and does not raise the Nash gapWorst payoff change against a best-responding victim
Kuhn (3 players)certified, τ=0\tau=042 of 54−0.085-0.085
Kuhn (3 players)unsafe8 of 54−0.17-0.17
Leduc (3 players)certified, τ=0\tau=0104 of 157−0.14-0.14
Leduc (3 players)unsafe63 of 157−0.24-0.24

These tables are in Appendix C of the revision (Table 11, line 1296, and the paragraph at lines 1295-1316).

Question 1

Can you demonstrate the certified-resolving pipeline on a realistic-scale multiplayer setting (e.g., a six-player poker-style subgame under abstraction), or provide a complexity/scaling analysis of the LP and CFR-on-gadget solvers as the subgame and opponent count grow?

We added this experiment and the scaling analysis. The pipeline runs exactly on six-player Kuhn subgames with no certificate violation, the LP stays small because the factorial number of entries enters only through the number of entry groups, and gadget CFR$^+$ reaches the LP value in every configuration.

n=3n=3n=4n=4n=5n=5n=6n=6
Configurations185615060
Certified updates that exceed their certificate0 of 1080 of 3360 of 9000 of 360
Share of configurations with positive certified gain at τ=0\tau=00.830.750.710.60
Entries per subgame, (n+1)!(n+1)!241207205,040
Entry groups, G=(n−1)(n+1)G=(n-1)(n+1)8152435
LP variables (median)365780104
LP solve time (median, seconds)0.0010.0020.0030.003
Gadget CFR$^+$ reaches the LP value to 10−410^{-4}18 of 1856 of 56150 of 15060 of 60
Gadget iterations (median)200200200200
Cost of one gadget iteration, in subgame traversals per victim2.602.362.252.20

Using 1,000-iteration CFR blueprints across 284 configurations for n=3n=3 to 66 (all configurations for n=3,4,5n=3,4,5, and 60 sampled of 372 at n=6n=6, where the tree has 1,940,401 nodes and 5,040 deals), 0 of 1,704 certified updates exceed their certificate. At τ=0\tau=0, no certified update raises the Nash gap by more than 10−410^{-4} at any nn, whereas unsafe resolving does so in 30% to 67% of configurations depending on nn.

In closed form, the LP has N=nx+∑g(∣Ij(ηg)∣+1)+G+1N = n_x + \sum_g(|I_j(\eta_g)|+1) + G + 1 variables for nxn_x resolver subgame sequences and G=(n−1)(n+1)G=(n-1)(n+1) entry groups, matching the built program on all 284 configurations. Because (n+1)!(n+1)! entries enter only via GG, median LP solve time stays at 0.002 to 0.004 seconds across nxn_x from 9 to 435; the costs that grow with nn are building the sequence index and computing exact certificate best responses, both linear in the size of the subgame tree. The gadget has M=2+3(n−1)+3G+(2n−1)∣S∣M = 2 + 3(n-1) + 3G + (2n-1)|S| nodes for entry-subtree size ∣S∣|S| (exact on all 284 configurations), costing (2n−1)/(n−1)(2n-1)/(n-1) subgame traversals per victim per iteration in the limit, and CFR$^+$ reaches the LP value within 10−410^{-4} in 284 of 284 configurations (median 200 iterations).

We avoided an abstracted six-player poker game because every number in our paper is an exact full-tree best response. A 4-player Leduc game (4 ranks, 2 suits, two rounds, two raises) already has 105,180,721 nodes, and under abstraction the certificate's own evaluation would carry estimation error. The six-player Kuhn subgames are six-player poker subgames evaluated exactly.

Question 2

How does the cap identity and the certified gain degrade away from constant-sum structure? Please quantify the behaviour in non-constant-sum games (e.g., with rakes), where the exact pricing no longer applies.

One clarification first. The certificate (Proposition 1), the linear program (Proposition 2), and the gadget (Theorem 1) need no constant-sum assumption: the 160 stage-game configurations in our main table are general-sum (Appendix B, submitted line 902, revised lines 966-967), and only Theorem 2 uses constant sum, in its last proof step. We added Corollary 4 and a rake experiment. In any game, adding the change of total payoff Δsum=∑pδp\Delta_{\mathrm{sum}}=\sum_p\delta_p gives the bound δi≤(n−1)τ+∑j≠isj−∑j≠iDj+Δsum\delta_i \le (n-1)\tau + \sum_{j\ne i}s_j - \sum_{j\ne i}D_j + \Delta_{\mathrm{sum}} (Corollary 4, revised lines 414-420), with zero violations across 3,600 exact test points.

FamilyExact test pointsTheorem 2 violatedCorollary 4 (corrected) violatedCorollary 2 violatedCorollary 2 with the same correction violated
Kuhn with rake1,08060510
Leduc with rake1,08010803110
Stage games, weight λ\lambda1,440260660
All3,60014004280

Under a rake charging the winner min⁡(ρ⋅pot,1)\min(\rho\cdot\text{pot},1) and in perturbed stage games, Theorem 2 fails at 140 of 3,600 exact test points (all at positive rake or perturbation weight, while all 576 zero-rake, zero-weight points satisfy both forms), whereas Corollary 4 and the similarly corrected Corollary 2 fail at none. Across all test points, Δsum\Delta_{\mathrm{sum}} is signed, with a median of 0 at τ=0\tau=0 and a range of −0.021-0.021 to +0.055+0.055.

As the rake grows, the certified gain and the exact-safe gain fall together on Kuhn because the rake removes safe gain from the game, while the certificate keeps its share of what remains.

GameBlueprint iterationsRake ρ\rhoMedian certified gain (τ=0\tau=0)Median exact-safe gain (τ=0\tau=0)Share with positive certified gain, τ=0\tau=0same share, τ=0.005\tau=0.005
Kuhn1,00008.0×10−58.0\times10^{-5}1.0×10−41.0\times10^{-4}0.831.00
Kuhn1,0000.0257.9×10−57.9\times10^{-5}2.9×10−42.9\times10^{-4}0.781.00
Kuhn1,0000.054.4×10−54.4\times10^{-5}1.6×10−41.6\times10^{-4}0.781.00
Kuhn1,0000.11.3×10−51.3\times10^{-5}8.7×10−58.7\times10^{-5}0.720.94
Kuhn1,0000.253.6×10−63.6\times10^{-6}4.7×10−64.7\times10^{-6}0.780.94
Leduc10002.7×10−22.7\times10^{-2}3.1×10−23.1\times10^{-2}0.931.00
Leduc1000.0252.3×10−22.3\times10^{-2}3.6×10−23.6\times10^{-2}1.001.00
Leduc1000.052.5×10−22.5\times10^{-2}3.0×10−23.0\times10^{-2}1.001.00
Leduc1000.12.2×10−22.2\times10^{-2}2.9×10−22.9\times10^{-2}1.001.00
Leduc1,00005.2×10−35.2\times10^{-3}8.1×10−38.1\times10^{-3}0.931.00
Leduc1,0000.055.7×10−35.7\times10^{-3}7.5×10−37.5\times10^{-3}1.001.00

On 3-player Kuhn with the 1,000-iteration blueprint at τ=0\tau=0, raising ρ\rho from 0 to 0.25 lowers the median exact-safe gain from 1.0×10−41.0\times10^{-4} to 4.7×10−64.7\times10^{-6} and the median certified gain from 8.0×10−58.0\times10^{-5} to 3.6×10−63.6\times10^{-6}, while on 3-player Leduc neither moves. With budget τ=0.005\tau=0.005, at least 94% of configurations keep a positive certified gain at every rake.


Thank you again for your supportive and precise review. We are glad to address any further concern.

Reviewer_C7WkOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper addresses the question of how to perform safe subgame solving beyond the usual setting of two-player zero-sum games. The authors propose an algorithm that is provably safe in theory (in the same sense that classical subgame solving methods are safe for two-player zero-sum games). In experiments, the authors verified the theoretical prediction of safety, and found that in most cases, their method decreases exploitability significantly.

Critical strengths

The paper addresses an interesting problem: how to perform safe subgame resolving in multi-player games. The method proposed by the authors seems to be effective in both theory and practice.

Critical weaknesses

The main reason for my score is the poor quality of writing. Like a lot of AI math writing, it is filled with confusing terms and notation, making it hard to parse without great effort.

Questions for authors

None

3 comments

Thank you for taking the time to review our paper and for finding that the method is sound and effective in theory and practice.

Weakness

The main reason for my score is the poor quality of writing.

We sincerely apologise for the effort that the submitted text demanded of you. We rewrote the exposition of Sections 1 to 6 for a first-time reader. We added Table 1 (revised line 134) as a notation table, placed a short opener at the start of each section saying what it does, and threaded a running 3-player Kuhn example from Section 2 (revised lines 167-168) through the gadget in Section 3 (revised lines 271-276). Before the main formal statements, we now give the plain reason why an opponent's own reach factors out of entry groups, why the best-response anchor makes the deficit zero at the blueprint, and why the resolver's own best-response value does not move. In Section 4, we also describe the dual variables in plain terms, give one sentence of arithmetic for the gadget's fair coin and doubled terminals, and explain why the shift is exact when no opponent acts before the subgame. Finally, we copy-edited the whole paper, writing shorter sentences, shortening captions, replacing the abstract's formula with words, and moving the three-program comparison table to Appendix B (Table 4).

Like a lot of AI math writing, it is filled with confusing terms and notation, making it hard to parse without great effort.

Our AI use statement (submitted lines 497-502, revised lines 551-556) discloses our use of AI tools. Among other uses, it notes that generative AI tools were used to edit the prose and that we read every passage for correctness. The research idea and paper structure are our own, and we checked and adjusted the text after the AI edits. Nevertheless, the first version left terms and notation that are hard for a reader who does not work on subgame solving every day. That is our responsibility, and we are sorry for the difficulty this caused. Below, we describe our revisions to terms and notation.

Terms and symbols are now defined at or before first use, and Table 1 (revised line 134) collects them. Terms such as blueprint, victim, profile cap, exploitability, the two-player gadget, and counterfactual regret minimisation are explained in plain language when they first appear. Entry groups in Section 2 are now defined in two steps: first the partition, and then the weight. In Section 2 (submitted lines 194-197, revised lines 152-153), we also fixed a typo in the Nash gap definition, replacing the undefined symbol Ap(σ)A_p(\sigma) with rp(σ)r_p(\sigma) so max⁡prp(σ)\max_p r_p(\sigma) gives the largest best-response gain. Later sections follow the same rule. Section 3 states the convention that quantities are evaluated at the resolved profile, and the penalised program is defined in Appendix A. Section 5 explains ledger saturation, identifies the per-step certificate BtB_t, and changes "when the cap is reached" to "at the 60-step limit", while Section 6 moves column definitions from the table caption into the text. The glossary below collects our main terms and where the revision defines them.

TermMeaning in one lineWhere the revision defines it
Nash gap Gap(σ)\mathsf{Gap}(\sigma)the largest best-response gain of any single playerSection 2, first paragraph; lines 152-153
Blueprint β\betathe full-game strategy profile computed offlineSection 2, "Resolving", line 170
Entry group η\etathe entries of the subgame that opponent jj cannot tell apart when play enters itSection 2, "Resolving", lines 178-185
Anchor CBVj0(η)\mathrm{CBV}^0_j(\eta)opponent jj's best-response value below η\eta against the blueprintSection 2, "Anchor and anchored deficit", lines 186-193
Anchored deficit KjK_jhow far the update lifts jj's best-response value above its anchor, summed over jj's entry groupsDefinition 1, line 195
Certificate CancC_{\mathrm{anc}}an upper bound, computed inside the subgame, on how much one seat's update raises the whole-game Nash gapProposition 1, lines 216-223
Victimthe opponent the meta-adversary picks to chargeSection 3, "The multi-victim gadget", lines 263-264
Budget τ\tau and capτ\tau is the allowed rise of the Nash gap; the cap is the level Gap(β)+τ\mathsf{Gap}(\beta)+\tauSection 2, "Resolving", lines 175-176
Slack sjs_jhow far opponent jj's gain sits below the blueprint's Nash gapSection 2, "Resolving", line 174
Meta-adversarythe second player of the gadget game, who picks which victim to chargeSection 3, "The multi-victim gadget", lines 263-264
Ledgera running upper bound on every seat's gain, updated without new best responsesSection 5, lines 398-399

Two passages from Sections 3 and 6 show the kind of change we made across the paper.

Nash gap (Section 3). Submitted (lines 194-197): "... and Gap(σ)=max⁡pAp(σ)\mathsf{Gap}(\sigma)=\max_p A_p(\sigma) for the profile's Nash gap, the smallest ε\varepsilon for which σ\sigma is an ε\varepsilon-Nash equilibrium." Revised (lines 152-153): "The Nash gap is Gap(σ)=max⁡prp(σ)\mathsf{Gap}(\sigma)=\max_p r_p(\sigma), which is the largest best-response gain of any single player."

Ledger saturation (Section 6). Submitted (lines 396-397): "The ledger is an upper bound, and the resolve exploits it: the entry of every binding victim reaches the cap while its true gain stays below it." Revised (lines 407-410): "Because Kj≥DjK_j\ge D_j, the ledger entry rˉjt\bar r^t_j drifts above the true best-response gain rj(βt)r_j(\beta^t). Each 00-certified resolve pushes the ledger value of every opponent whose constraint is tight up to the cap Φt\Phi_t while its true best-response gain stays below. Once every ledger entry sits at Φt\Phi_t, no update can gain under the ledger and the ledger saturates."


Thank you again for your careful review and candid feedback. If any term or passage in the revision still reads poorly, please let us know and we will gladly fix it during the discussion. Since writing quality was the only stated reason for your score, we kindly ask you to look at the blue text of the revised PDF and reconsider your rating. We are glad to address any further concern.

Here is the summary of revisions:

  • Abstract (lines 13-27): Rewritten in plain words, with the results stated as conclusions instead of numbers.
  • Section 1 (lines 35-96): The post-hoc bound is attributed to its source (lines 59-60); the introduction explains what a public subgame is, what safe means, and why the guarantee fails with three players; the contribution list states what is new (lines 80-96).
  • Section 2 (lines 101-230): Rewritten for a first-time reader: a short primer on the game tree and the Nash gap, a running 3-player Kuhn example introduced where the subgame is defined and used after each new definition (lines 167-168), the anchor in plain words (lines 186-193), and a reading of Proposition 1 before it is stated (lines 212-215); Table 1 (line 134) lists the notation.
  • Section 3 (lines 232-332): A new paragraph "The resolver in four steps" (lines 256-260) states what the resolver does; the gadget paragraph now gives the structure and points to Appendix A, where the construction moved; the running example is reused for the gadget (lines 271-276).
  • Section 4 (lines 335-377): Added a plain reading of Theorem 2 and the new Corollary 4 (General sum, lines 367-377) with its proof.
  • Section 5 (lines 380-445): Ledger saturation explained (lines 407-410); the round, the passing rule and equalised profiles defined (lines 417-421); the frugal variant moved to Appendix B.
  • Section 6 (lines 450-479): The main-table columns now use words and their definitions moved to Appendix B; a new paragraph "Scaling, rake and where the gain lives".
  • Section 7 (lines 488-523): Related work now comes after the experiments; a new paragraph "Closest work" (lines 503-511) cites and positions the two closest works.
  • Appendix D (lines 1351-1369): Three related-work paragraphs moved out of the main text.
  • Appendix C (lines 1223-1349): Added "Further Experiments" (Tables 8 to 12) covering nn-player Kuhn up to six players, the cap identity and certified gain under rake, where the certified gain lives, small budgets, anchor feasibility, and a numerical check of Theorem 1.

Thank you again for your careful review and candid feedback. If any term or passage in the revision still reads poorly, please let us know and we will gladly fix it during the discussion. Since writing quality was the only stated reason for your score, we kindly ask you to look at the blue text of the revised PDF and reconsider your rating. We are glad to address any further concern.

Reviewer_AbCFOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies subgame resolving in multiplayer imperfect-information extensive-form games. The authors propose a framework that allows each player to optimize its strategy within a subgame while avoiding exploitability of the resulting strategy profile. Specifically, the paper introduces the notion of anchored deficit and shows that the Nash gap could be bounded by this notion. The authors then establish the convexity of the proposed safety certificate and show that the constrained subgame resolving can be formulated as a linear program. Finally, numerical results are provided to validate the theoretical findings.

Critical strengths
  • Safe subgame resolving in multiplayer imperfect-information games is a well-motivated and practically important problem.
  • The proposed notion of anchored deficit is mathematically interesting and provides useful insights for the later design of resolving subgames.
  • Numerical experiments are provided to validate the theoretical results.
Critical weaknesses
  • My main concern with this manuscript is its presentation. The paper is difficult to follow, with several notations and definitions that are problematic (e.g., the definition of the Nash gap). Moreover, the authors provide insufficient intuition and explanation for some of the mathematical arguments, making it hard to fully understand and evaluate the technical contributions.
  • While the convex characterization of the safety certificate is useful for developing efficient subgame resolving algorithms, the underlying argument appears relatively straightforward. In particular, convexity follows naturally from the multilinearity nature of the utility functions. Therefore, this characterization alone provides limited new technical insights.
Questions for authors

See weaknesses.

4 comments

Thank you for your careful reading and constructive feedback.

Weakness 1

My main concern with this manuscript is its presentation. The paper is difficult to follow, with several notations and definitions that are problematic (e.g., the definition of the Nash gap).

We apologise for the unclear notation and definitions in the submitted draft. In Section 3 (submitted lines 194-197), the Nash-gap formula had a typo: it wrote max⁡pAp(σ)\max_p A_p(\sigma) with ApA_p undefined. The revision (lines 209-213) corrects it to max⁡prp(σ)\max_p r_p(\sigma), the largest best-response gain of any single player. Section 3 now adds Table 1 (revised line 162) for notation across Sections 3 to 6, defines profile cap, victim, exploitability, the two-player gadget, and counterfactual regret minimisation (revised lines 209-281), and defines entry groups in two steps: first the partition, then the weight, with the reason an opponent's own reach factors out (revised lines 231-237).

Moreover, the authors provide insufficient intuition and explanation for some of the mathematical arguments, making it hard to fully understand and evaluate the technical contributions.

We added concrete intuition across Sections 3, 4, and 6:

  • Section 3 (revised lines 248-253 and lines 267-268): Why the anchor is the best-response value (with the two-player anchor, the deficit is already positive at the blueprint) and why the resolver's own best-response value does not move.
  • Sections 3 and 4 (revised lines 254-260 and lines 328-331): A running 3-player Kuhn example introduced in Section 3 and reused in Section 4 for the gadget.
  • Section 4 (revised lines 323-325, lines 355-359 and lines 373-374): One sentence of arithmetic for the gadget's fair coin and doubled terminals, why the certificate credits no fall when a victim acts before the subgame, and when the shift is exact (when no opponent acts before the subgame).
  • Section 6 (revised lines 451-454): Ledger saturation, alongside the per-step certificate BtB_t and clarified phrasing at the 60-step limit.

The main formal steps now come with a plain-language reason, and one worked example runs through Sections 3 and 4.

Weakness 2

While the convex characterization of the safety certificate is useful for developing efficient subgame resolving algorithms, the underlying argument appears relatively straightforward. In particular, convexity follows naturally from the multilinearity nature of the utility functions. Therefore, this characterization alone provides limited new technical insights.

While the convexity step in Proposition 2 (submitted lines 260-263, revised lines 299-303) is short and the revised contribution list in Section 1 (revised lines 84-102) names convexity as the entry point, the paper's technical content lies beyond that step. The contribution list of the submitted version (Section 1, submitted lines 86-107) names these results, and we point to each below:

(i) Anchoring (Lemma 1, submitted line 230, revised line 262). A maximum of affine functions is convex under any anchor, yet only the best-response anchor gives a valid upper bound on the rise of an opponent's full-game best-response value that is zero at the blueprint. We added an experiment on this. With the two-player counterfactual-value anchor in place of ours, the zero-budget program is infeasible in half of the tested poker configurations, whereas our anchor is always feasible.

GameConfigurationsτ=0\tau=0 program infeasible with the two-player anchor (CFV)infeasible with our anchor (CBV)
3-player Kuhn54270
3-player Leduc58280

Our anchor is always feasible because it certifies the blueprint itself (Appendix C of the revision, lines 1319-1323).

(ii) Gadget (Theorem 1, submitted lines 286-288, revised lines 333-335). Turning the minimum-certificate program into the value of a two-player zero-sum game in which a meta-adversary picks the victim so counterfactual regret minimisation solves it does not follow from multilinearity. We also checked Theorem 1 numerically. CFR$^+$ on the gadget reaches the linear program value within 10−410^{-4} across all 284 tested nn-player Kuhn configurations from 3 to 6 players.

Players nn3456
Configurations185615060
Gadget CFR$^+$ reaches the LP value to 10−410^{-4}185615060
Median iterations200200200200

The gadget and the linear program agree in all 284 configurations, at a median of 200 iterations (Appendix C of the revision, Table 8 and lines 1325-1327).

(iii) Cap identity (Theorem 2, submitted lines 352-357, revised lines 398-404; new Corollary 4, revised lines 414-420). Theorem 2 bounds a seat's gain in constant-sum games under budget τ\tau by (n−1)τ(n-1)\tau plus the opponents' slack minus the shift of their best-response values, with equality exactly when every opponent sits on the cap; Corollary 4 extends this identity to general-sum games via the total payoff change Δsum\Delta_{\mathrm{sum}}.

(iv) Localisation gap (Proposition 3 and Corollary 1, submitted lines 318-325, revised lines 367-378; Proposition 4, submitted lines 330-332, revised lines 382-384). Proposition 3 and Corollary 1 prove that when no opponent acts before the subgame, the two-sided certificate equals the exact whole-game safety constraint, and Proposition 4 decomposes any gap into clipping, reach, and re-optimisation.

(v) Multi-seat ledger (Section 6, submitted lines 377-419, revised lines 431-474). Propositions 5 and 6 and Observation 1 establish a joint certificate and monotone ledger across seats; re-anchored round-robin resolving lowers the Nash gap on 3-player Kuhn from 0.037 to between 0.016 and 0.022 (41% to 57%).

As a whole, the paper builds a constructive framework for multiplayer resolving: a blueprint-valid anchor, a zero-sum gadget for regret minimisation, exact localisation and gain-cap identities, and a multi-seat ledger.


Thank you again for your time and thoughtful review. We are glad to address any further concern, and we kindly ask you to reconsider your assessment in light of the revised exposition and the added experimental evidence.

I thank the authors for their response. The rebuttal has addressed my concerns, and I would like to raise my score accordingly. I encourage the authors to further improve the clarity of the manuscript.

Thank you for your follow-up message and for encouraging us to further improve the clarity of our manuscript.

We have again gone through the paper carefully from beginning to end and improved it, and every change in our second uploaded revision is marked in blue:

  • Abstract (lines 13-27): Rewritten in plain words, with the results stated as direct conclusions and numerical details left to the main text.
  • Introduction (lines 35-96): Now explains what a public subgame is, what "safe" means, and why the guarantee fails with three or more players; the contribution list states what is new.
  • Preliminaries (lines 101-230): Adds a short primer on the game tree and the Nash gap; introduces a running 3-player Kuhn example where the subgame is defined and uses it after each new definition (lines 167-168); explains the anchor in plain words (lines 186-193); gives a plain reading of the certificate before Proposition 1 (lines 213-215); provides the notation table on line 134.
  • Method (lines 232-332): Adds a new paragraph, "The resolver in four steps" (lines 256-260); the gadget paragraph gives the structure and points to Appendix A for the construction, which moved there; reuses the running example for the gadget (lines 271-276).
  • Price of certified safety (lines 335-377): Adds a plain reading of the cap identity after its proof.
  • Every seat (lines 380-445): Explains ledger saturation (lines 407-410) and defines the round, the passing rule, and equalised profiles (lines 417-421).
  • Experiments (lines 450-479): The main-table columns now use words, replacing the previous symbols, and their definitions moved to Appendix B.
  • Related work (lines 488-523): Now comes after the experiments and is shorter, with three paragraphs moved to the new Appendix D (lines 1351-1369).
  • Conclusion (lines 526-537): Rewritten to follow the revised paper.

Thank you again for your feedback, and we are glad to make any further adjustment.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of revisions

We thank all reviewers for their time and careful reading of our paper. Your feedback helped us make the exposition clearer, position the closest related work, and expand our theoretical and empirical results.

In the revised manuscript, (i) we rewrote the exposition of Sections 3 to 6 for a first-time reader, which was the main concern of Reviewers AbCF and C7Wk; (ii) we added the experiments and the general-sum corollary that Reviewer VbB5 asked for; and (iii) we now cite and position the two closest works.

Every change in the revised PDF is marked in blue. Line numbers below refer to the revised PDF.

  • Abstract (lines 13-27): Rewritten in plain words, with the results stated as conclusions instead of numbers.
  • Section 1 (lines 35-96): The post-hoc bound is attributed to its source (lines 59-60); the introduction explains what a public subgame is, what safe means, and why the guarantee fails with three players; the contribution list states what is new (lines 80-96).
  • Section 2 (lines 101-230): Rewritten for a first-time reader: a short primer on the game tree and the Nash gap, a running 3-player Kuhn example introduced where the subgame is defined and used after each new definition (lines 167-168), the anchor in plain words (lines 186-193), and a reading of Proposition 1 before it is stated (lines 212-215); Table 1 (line 134) lists the notation.
  • Section 3 (lines 232-332): A new paragraph "The resolver in four steps" (lines 256-260) states what the resolver does; the gadget paragraph now gives the structure and points to Appendix A, where the construction moved; the running example is reused for the gadget (lines 271-276).
  • Section 4 (lines 335-377): Added a plain reading of Theorem 2 and the new Corollary 4 (General sum, lines 367-377) with its proof.
  • Section 5 (lines 380-445): Ledger saturation explained (lines 407-410); the round, the passing rule and equalised profiles defined (lines 417-421); the frugal variant moved to Appendix B.
  • Section 6 (lines 450-479): The main-table columns now use words and their definitions moved to Appendix B; a new paragraph "Scaling, rake and where the gain lives".
  • Section 7 (lines 488-523): Related work now comes after the experiments; a new paragraph "Closest work" (lines 503-511) cites and positions the two closest works.
  • Appendix D (lines 1351-1369): Three related-work paragraphs moved out of the main text.
  • Appendix C (lines 1223-1349): Added "Further Experiments" (Tables 8 to 12) covering nn-player Kuhn up to six players, the cap identity and certified gain under rake, where the certified gain lives, small budgets, anchor feasibility, and a numerical check of Theorem 1.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.