- 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
- 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
- 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?
- 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
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 : whether the resolver holds a largest best-response gain, and the victims' total slack.
| Family | Resolver is not a largest-gain seat | Resolver 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, | 0.33 (9 of 27) | 1.00 (13 of 13) |
| Stage games, | 0.41 (11 of 27) | 1.00 (13 of 13) |
| Stage games, | 0.63 (20 of 32) | 1.00 (8 of 8) |
| Stage games, | 0.43 (15 of 35) | 1.00 (5 of 5) |
Across all 374 main-table configurations at , 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 ( to ) and 0.91 (48 of 53 configurations) on 3-player Leduc.
| Victims' total slack | lowest third | middle third | highest third |
|---|---|---|---|
| Kuhn (3 players) | 0.67 | 0.72 | 0.94 |
| Leduc (3 players) | 0.61 | 0.71 | 0.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 , 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 , 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.
| Game | Update | Configurations where it gains and does not raise the Nash gap | Worst payoff change against a best-responding victim |
|---|---|---|---|
| Kuhn (3 players) | certified, | 42 of 54 | |
| Kuhn (3 players) | unsafe | 8 of 54 | |
| Leduc (3 players) | certified, | 104 of 157 | |
| Leduc (3 players) | unsafe | 63 of 157 |
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.
| Configurations | 18 | 56 | 150 | 60 |
| Certified updates that exceed their certificate | 0 of 108 | 0 of 336 | 0 of 900 | 0 of 360 |
| Share of configurations with positive certified gain at | 0.83 | 0.75 | 0.71 | 0.60 |
| Entries per subgame, | 24 | 120 | 720 | 5,040 |
| Entry groups, | 8 | 15 | 24 | 35 |
| LP variables (median) | 36 | 57 | 80 | 104 |
| LP solve time (median, seconds) | 0.001 | 0.002 | 0.003 | 0.003 |
| Gadget CFR$^+$ reaches the LP value to | 18 of 18 | 56 of 56 | 150 of 150 | 60 of 60 |
| Gadget iterations (median) | 200 | 200 | 200 | 200 |
| Cost of one gadget iteration, in subgame traversals per victim | 2.60 | 2.36 | 2.25 | 2.20 |
Using 1,000-iteration CFR blueprints across 284 configurations for to (all configurations for , and 60 sampled of 372 at , where the tree has 1,940,401 nodes and 5,040 deals), 0 of 1,704 certified updates exceed their certificate. At , no certified update raises the Nash gap by more than at any , whereas unsafe resolving does so in 30% to 67% of configurations depending on .
In closed form, the LP has variables for resolver subgame sequences and entry groups, matching the built program on all 284 configurations. Because entries enter only via , median LP solve time stays at 0.002 to 0.004 seconds across from 9 to 435; the costs that grow with are building the sequence index and computing exact certificate best responses, both linear in the size of the subgame tree. The gadget has nodes for entry-subtree size (exact on all 284 configurations), costing subgame traversals per victim per iteration in the limit, and CFR$^+$ reaches the LP value within 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 gives the bound (Corollary 4, revised lines 414-420), with zero violations across 3,600 exact test points.
| Family | Exact test points | Theorem 2 violated | Corollary 4 (corrected) violated | Corollary 2 violated | Corollary 2 with the same correction violated |
|---|---|---|---|---|---|
| Kuhn with rake | 1,080 | 6 | 0 | 51 | 0 |
| Leduc with rake | 1,080 | 108 | 0 | 311 | 0 |
| Stage games, weight | 1,440 | 26 | 0 | 66 | 0 |
| All | 3,600 | 140 | 0 | 428 | 0 |
Under a rake charging the winner 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, is signed, with a median of 0 at and a range of to .
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.
| Game | Blueprint iterations | Rake | Median certified gain () | Median exact-safe gain () | Share with positive certified gain, | same share, |
|---|---|---|---|---|---|---|
| Kuhn | 1,000 | 0 | 0.83 | 1.00 | ||
| Kuhn | 1,000 | 0.025 | 0.78 | 1.00 | ||
| Kuhn | 1,000 | 0.05 | 0.78 | 1.00 | ||
| Kuhn | 1,000 | 0.1 | 0.72 | 0.94 | ||
| Kuhn | 1,000 | 0.25 | 0.78 | 0.94 | ||
| Leduc | 100 | 0 | 0.93 | 1.00 | ||
| Leduc | 100 | 0.025 | 1.00 | 1.00 | ||
| Leduc | 100 | 0.05 | 1.00 | 1.00 | ||
| Leduc | 100 | 0.1 | 1.00 | 1.00 | ||
| Leduc | 1,000 | 0 | 0.93 | 1.00 | ||
| Leduc | 1,000 | 0.05 | 1.00 | 1.00 |
On 3-player Kuhn with the 1,000-iteration blueprint at , raising from 0 to 0.25 lowers the median exact-safe gain from to and the median certified gain from to , while on 3-player Leduc neither moves. With budget , 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.
Thank you for your careful and accurate reading of our paper and your constructive questions.
Weakness 1
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 budget τ 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 the Nash gap does not rise beyond solver tolerance. We added an experiment on small budgets. The shortfall at τ=0 is specific to the zero budget, and a budget of τ=10−4 already recovers most of the exact-safe gain.
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).
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%).