acceptodds
Under review as a conference paper at ICLR 2027

Safe Subgame Resolving in Multiplayer Games

Abstract

Poker and other games with hidden information are too large to solve in one pass. Systems that play them at a superhuman level instead compute a complete strategy offline, the *blueprint*, and then re-solve the part of the game actually reached during play, refining the blueprint in real time inside that *subgame*. For two players in a zero-sum game this second stage, subgame resolving, comes with a safety theorem: refinement never increases how much an adversary can gain by exploiting the strategy. With three or more players acting independently (uncorrelated profiles) no such guarantee exists. Multiplayer systems resolve heuristically, and resolving can increase a profile's vulnerability, the largest gain any single player obtains by deviating. We prove the first conditional safety theorem for uncorrelated multiplayer subgame resolving, a post-hoc certificate for any delivered update. The vulnerability of the resolved profile exceeds that of the blueprint by at most four terms. The first is the activation term , the subgame value the blueprint promised but did not realize. The other three are the structural tax , the summed best-response margin deficits \sum_q M_q}, and the resolver's blueprint-relative subgame suboptimality . The tax is an oscillation of the total utility, bounded by times the distance to the class of constant-sum polymatrix (CSP) games, whose payoffs decompose into pairwise constant-sum interactions. Constructions attain each term, and both branches of the maximum in the sharper bound, with equality; a certified adversarial search over 162 instances finds no violation. Every rake-free poker variant is pointwise constant-sum, so the sharp structural tax vanishes there.

Primary area:
reinforcement learning
Keywords:
Imperfect Information Games, Multi Player, Subgame Solving

Reviews

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

The paper addresses the safety of subgame resolving in multiplayer imperfect-information extensive-form games (IIEFGs). Large games such as poker are solved offline under abstraction to produce a blueprint strategy, which is then refined in real time inside the reached subgame. For two-player zero-sum games this second stage is provably safe: refinement never increases exploitability (Burch et al., 2014; Brown & Sandholm, 2017). With three or more players acting independently no such guarantee exists, and systems such as Pluribus resolve heuristically. The paper proves the first conditional safety theorem for uncorrelated multiplayer subgame resolving. For any resolving update σ1 of a blueprint σ0 by resolver i in a subgame S, the vulnerability of the resolved profile exceeds that of the blueprint by at most four terms: the activation term ASi(σ0) (the subgame value the blueprint promised but did not realize), the structural tax Θ ≤ 2nδ∞ (an oscillation of the total utility bounded by 2n times the distance to the class of constant-sum polymatrix games), the summed best-response margin deficits ΣMq, and the resolver's blueprint-relative subgame suboptimality εi (Theorem 1). A sharper form of the structural tax vanishes on pointwise constant-sum games, which include every rake-free poker variant (Corollary 4). Constructions attain each term with equality (Examples 1–3), and a certified adversarial search over 162 small three-player instances finds no theorem-level violation, with a two-term ablation and an n-sweep (n = 3, 4, 5) as additional instruments. The certificate is also presented as a decision rule: a baseline-aware form accepts 37 of 162 delivered updates at zero tolerance (versus 2 for the direct form) at 1.5× the cost of a cached exact evaluation.

Critical strengths

1.The problem is important and the gap is real: multiplayer subgame resolving is used in practice (Pluribus) without any safety guarantee, and the two-player identity (one player's gain is the other's loss) fails beyond n = 2. The paper is the first to give a formal, conditional safety statement for this setting (Sec. 1, 2). 2.The main bound is clean and decomposable: the four terms (activation, structural tax, margin deficits, solve error) correspond to distinct channels of harm, each with a natural interpretation, and the per-player form (Theorem 1(ii)) gives more granularity than a single aggregate bound. 3. The theory is supported by tightness constructions: Example 1 shows the activation term is unavoidable even in two-player zero-sum games, Example 2 pins the per-player granularity of the margin term, and Example 3 covers the leak and self-harm channels. All four terms of the bound and both branches of the maximum are attained with equality (Sec. 5). 4.The evaluation is unusually rigorous for a theory paper: a certified cutting-plane best-response search over 162 instances with no theorem-level counterexample, LP dual certificates for the δ∞ lower bounds, numerical regression checks for every inequality, a two-term ablation, and an n-sweep (Sec. 7, Appendices E–F, I). 5.The paper is honest about the limits of the result: the guarantee is conditional and post-hoc, the n factor of the transfer lemma is not proved tight end-to-end, and Proposition 5 documents that implementation-caliber margins misreport near equilibrium — the authors point at the failure rather than hiding it (Sec. 6–8).

Critical weaknesses

1.The guarantee is conditional and post-hoc rather than unconditional safety. In the general case Theorem 1 bounds the vulnerability increase by a sum of computable terms, but it does not guarantee safety: the bound can be large, and safety (VulG(σ1) ≤ VulG(σ0)) requires extra conditions (margin-certified updates, small εi, small structural tax). In contrast, the two-player literature offers an unconditional guarantee. The practical question — does resolving hurt in multiplayer games, and by how much in realistic settings — is therefore only partially answered. 2.The empirical evaluation is limited to 162 small three-player instances; no realistic-scale demonstration. All experiments use small n = 3 EFGs, and the adversarial search, ablations, and n-sweep are verification of the theorem's form rather than an end-to-end application. There is no demonstration on a realistic multiplayer setting (e.g., a six-player poker-style game with abstraction) showing that the certificate is computable at the intended cost and that the bound is informative (not vacuous) where it matters. 3.The bound can be vacuous in the very games that motivate the work. For poker-style games δ∞ ≥ 1 (Proposition 2), so the plain 2nδ∞ term exceeds the utility scale; the sharper Θ-form vanishes only on pointwise constant-sum games, and the paper does not quantify Θ for realistic multiplayer poker with rakes or non-constant-sum structure. The margin deficits also require one best-response pass per opponent per entry set, whose cost in a large game is not assessed. 4.The n factor of the transfer lemma is not proved tight. The paper states that the end-to-end response of ΔVul to δ∞ is not proved tight in n and that the structural n factor is only attained on screening instances (Sec. 8, Appendix C). Given that the 2nδ∞ term is a central object of the bound, a tighter dependence would materially strengthen the result. 5.Accessibility and measure justification. The paper is 38 pages of dense theory (including a 97-item numerical regression check), which will be hard for practitioners to verify and use. Also, VulG (the largest single-player best-response gain) is one of several possible generalizations of exploitability to n > 2; the paper motivates it but does not discuss alternative multiplayer measures in depth (e.g., the correlated or team-based notions it cites).

Questions for authors
  1. Can you state precisely the conditions under which multiplayer resolving is unconditionally safe (i.e., VulG(σ1) ≤ VulG(σ0)) rather than merely bounded by a computable post-hoc quantity, and how often these conditions hold in realistic resolving pipelines?
  2. Can you demonstrate the certificate on a realistic-scale setting (e.g., a six-player poker-style game under abstraction), including the wall-clock cost of the per-opponent best-response passes needed for the BR-certified margins?
  3. The plain 2nδ∞ term is vacuous for poker-style games (δ∞ ≥ 1). Can you quantify Θ for realistic multiplayer poker with rakes or non-constant-sum structure, where the sharp form does not automatically vanish?
5 comments

Thank you for the precise summary of our theoretical decomposition and for your three targeted questions. They identify the exact empirical evidence needed to evaluate the bound: how often the safety conditions hold in practice, how the certificate scales with player count and tree size, and how the structural tax behaves under a rake. We have added all of these experiments to Section 6 and Appendix J, and we have uploaded the revised PDF with changed words marked in red. We respond to each point below.

W1 and Q1. Conditional and post-hoc guarantee; when is resolving safe outright, and how often

In short: On three-player Leduc, Bcache≤0B_{\mathrm{cache}} \le 0 holds on 47% to 53% of updates and Bcache≤0.02B_{\mathrm{cache}} \le 0.02 holds on 80% to 87%. Gating at 0.02 antes accepts 0 harmful updates across all 1,788 Kuhn and Leduc updates while preserving positive payoff gains.

Let GapG\mathrm{Gap}_G denote the profile's best-response gap (Definition 3), which is the largest gain any single player obtains by deviating (called vulnerability in the submission).

In a game GG with nn players, as updates change a blueprint σ0\sigma^0 to a resolved profile σ1\sigma^1 for resolver ii inside a subgame SS, the checkable condition for GapG(σ1)≤GapG(σ0)\mathrm{Gap}_G(\sigma^1) \le \mathrm{Gap}_G(\sigma^0) is Bcache≤0B_{\mathrm{cache}} \le 0 (Corollary 3), where BcacheB_{\mathrm{cache}} is the baseline-aware certificate.

Evaluating BcacheB_{\mathrm{cache}} requires one best-response pass per opponent inside the subgame plus the blueprint's stored best-response gains. The stricter condition in the two-player style requires every BR-certified margin to be nonnegative alongside a solve error εi=0\varepsilon_i = 0 and a structural tax Θ=0\Theta = 0.

This stricter condition guarantees GapG(σ1)≤GapG(σ0)+AiS(σ0)\mathrm{Gap}_G(\sigma^1) \le \mathrm{Gap}_G(\sigma^0) + A_i^S(\sigma^0), where the activation term AiS(σ0)A_i^S(\sigma^0) measures the subgame value the blueprint promised to the resolver yet failed to realize.

Because AiS(σ0)A_i^S(\sigma^0) is unavoidable even in two-player zero-sum games (Example 1), we use BcacheB_{\mathrm{cache}} as our operational decision rule.

Three-player Kuhn and Leduc poker, pooled over blueprints

GameResolverMedian ΔGapHarmful updatesAccepted at 0Accepted at 0.02Resolver gainMax ΔGap after gating
Kuhnbest response+0.062080%0%5%+0.0164+0.0068
Kuhnstandard gadget+0.009629%0%41%+0.0082+0.0182
Kuhnbelief-corrected gadget+0.001620%0%43%+0.0087+0.0170
Leducbest response+0.000012%53%80%+0.0063+0.0094
Leducstandard gadget+0.00002%47%86%+0.0031+0.0135
Leducbelief-corrected gadget-0.00002%52%87%+0.0034+0.0083

Legend: ΔGap\Delta\mathrm{Gap} is the change in the profile's best-response gap caused by an update, in antes. Harmful updates is the share of updates with ΔGap>0.02\Delta\mathrm{Gap} > 0.02, Accepted at tt is the share with Bcache≤tB_{\mathrm{cache}} \le t, Resolver gain is the resolver's mean realized payoff gain, and Max ΔGap\Delta\mathrm{Gap} after gating is the worst gap increase when keeping the blueprint whenever Bcache>0.02B_{\mathrm{cache}} > 0.02.

On three-player Leduc across 1,620 updates, the certificate BcacheB_{\mathrm{cache}} satisfies Bcache≤0B_{\mathrm{cache}} \le 0 antes on 47%47\% to 53%53\% of updates across the tested resolvers. At a tolerance of 0.020.02 antes, Bcache≤0.02B_{\mathrm{cache}} \le 0.02 holds on 80%80\% to 87%87\% of Leduc updates (Section 6, Table 1). On three-player Kuhn, subgames are small enough that every update shifts some opponent's margin. Consequently, Bcache≤0B_{\mathrm{cache}} \le 0 antes holds on 0%0\% of Kuhn updates, while Bcache≤0.02B_{\mathrm{cache}} \le 0.02 antes holds on 41%41\% to 43%43\% of gadget updates. Across all 1,788 updates on both games, gating with the certificate at a tolerance of 0.020.02 antes accepts 00 harmful updates. The strict margin-certified condition alone is rare in practice because exact best-response margins against an approximate equilibrium blueprint are slightly negative almost everywhere. We conclude that the certificate is informative in practice. It accepts most updates on Leduc and accepts no harmful update on either game.

Using Bcache≤0.02B_{\mathrm{cache}} \le 0.02 as a safety gate eliminates harmful updates while preserving positive mean realized payoff gains for both gadgets. Without gating, the standard gadget produces harmful updates on 29% of Kuhn updates and 2% of Leduc updates, while best-response resolving produces harmful updates on 80% of Kuhn updates and 12% of Leduc updates. With the gate active, the harmful update rate drops to 0% on both games, and the worst gap increase after gating is bounded by +0.0182+0.0182 antes on Kuhn and +0.0135+0.0135 antes on Leduc. We conclude that the method has clear practical value: ungated multiplayer resolving is unsafe, and gating with our certificate prevents all harmful updates while keeping a positive payoff gain. Because the certificate applies to any update using only best responses inside the subgame, it attaches directly as a safety check to real-time multiplayer solvers that refine a blueprint (our third contribution).

Minimum gadget margin of the two opponents under four root measures (three-player Kuhn)

blueprintpubresolverc_e·π_ic_e·Π_p π_pc_e·π_{-q}, opp. 1c_e·π_{-q}, opp. 2
cfr200b2-0.432 / -1.097-0.386 / -0.102-0.432 / -1.097-0.386 / -0.102
cfr200b3-0.433 / -0.688-0.404 / -0.032-0.433 / -0.688-0.404 / -0.032
cfr200k1-0.025 / -0.016-0.025 / -0.016-0.025 / -0.016-0.025 / -0.016
cfr200k2-0.023 / -0.027-0.037 / -0.006-0.023 / -0.027-0.037 / -0.006
cfr200k3+0.004 / -0.014+0.004 / -0.016+0.004 / -0.014+0.004 / -0.016
cfr1000b2-0.422 / -0.991-0.015 / -0.029-0.422 / -0.991-0.015 / -0.029
cfr1000b3-0.423 / -0.669-0.040 / -0.016-0.423 / -0.669-0.040 / -0.016
cfr1000k1-0.026 / -0.011-0.026 / -0.011-0.026 / -0.011-0.026 / -0.011
cfr1000k2-0.034 / -0.072-0.011 / -0.076-0.034 / -0.072-0.011 / -0.076
cfr1000k3-0.021 / -0.007-0.002 / -0.004-0.021 / -0.007-0.002 / -0.004

Legend: pub is the public subgame root (b for bet, k for check), and each cell reports the minimum gadget margin for opponent 1 followed by opponent 2. The four root measures weight entry histories ee by the chance reach cec_e times the resolver reach πi\pi_i, the product of all players' reaches ∏pπp\prod_p \pi_p, or the counterfactual reach π−q\pi_{-q} excluding opponent qq.

Section 5 explains structurally why unconditional two-player safety cannot hold for n>2n > 2 players. In a resolving gadget, the Terminate option prices each opponent qq using qq's own counterfactual reach probability π−q\pi_{-q}. For n>2n > 2, these reach weights differ from one opponent to another. Consequently, no single root probability measure can price the gadget for all opponents simultaneously: across the 40 cells of Table 8 in Appendix J (shown above, ten blueprint, subgame and resolver configurations under four root measures), no cell has nonnegative margins for both opponents at once.


W2 and Q2. Empirical scale and wall-clock cost of the best-response passes

In short: Across 1,884 updates on three-player Kuhn, three-player Leduc, and Kuhn with 3 to 6 players, the bounds have 0 violations. At n=6n = 6 players, the certificate takes 26.2 to 28.5 seconds versus 10,181 to 10,258 seconds for gadget resolving, and accepts 64% of gadget updates.

We expanded our empirical evaluation in Section 6 to cover three-player Kuhn poker (168 updates across seven blueprints), three-player Leduc poker with 38,641 decision nodes and 1,134 information sets (1,620 updates across five blueprints, including noisy blueprints and a card-abstracted blueprint lifted to the full game), and Kuhn poker scaling from n=3n = 3 to n=6n = 6 players (96 updates). Across all 1,884 poker updates and the 162 random-game updates (kept in full in Appendix K), Theorem 1 and the certificates have 0 violations.

Kuhn poker with n = 3 to 6 players

nResolverMedian ΔGapHarmful updatesAccepted at 0.02Resolve (s)Certificate (s)Exact evaluation (s)
3best response+0.050980%0%0.0100.0040.003
3standard gadget+0.009740%40%0.3400.0040.004
3belief-corrected gadget+0.004320%60%0.3400.0040.004
4best response+0.0489100%0%0.0800.0480.048
4standard gadget+0.022157%43%9.820.0620.057
4belief-corrected gadget+0.002843%57%9.560.0620.058
5best response+0.023256%33%1.891.041.07
5standard gadget+0.00220%56%3001.301.31
5belief-corrected gadget+0.000011%78%3011.271.40
6best response+0.0370100%0%47.130.124.4
6standard gadget+0.012536%64%1025826.232.2
6belief-corrected gadget+0.011236%64%1018128.528.2

Legend: Resolve, Certificate, and Exact evaluation report median wall-clock times in seconds on a single CPU core for the subgame resolve, the local certificate BcacheB_{\mathrm{cache}}, and the exact full-game evaluation of ΔGap\Delta\mathrm{Gap}. The remaining columns follow the definitions from the first table.

Cost of the certificate

GameActivation term (s)Margin pass (s)Full certificate / exact evaluationMargin pass / exact evaluation
3-player Kuhn0.003 to 0.0030.001 to 0.0021.34 to 1.520.46 to 0.65
3-player Leduc0.450 to 0.4930.065 to 0.0751.01 to 1.110.13 to 0.15
4-player Kuhn0.030 to 0.0410.015 to 0.0311.17 to 1.260.32 to 0.64
5-player Kuhn0.745 to 0.7870.241 to 0.6940.86 to 1.120.20 to 0.54
6-player Kuhn15.1 to 17.94.48 to 16.50.76 to 1.240.17 to 0.59

Legend: Activation term and Margin pass give the wall-clock times in seconds for the two parts of the certificate across resolvers. The last two columns divide the full certificate time and the online margin-pass time by the exact full-game evaluation time.

Tables 2 and 3 in Section 6 (shown above) demonstrate that the certificate is fast and non-vacuous up to n=6n = 6 players, where nn is the number of players. At n=6n = 6 players, running the gadget solver takes 10,181 to 10,258 seconds (about 170170 minutes). Computing the full certificate on gadget updates takes 26.226.2 to 28.528.5 seconds and accepts 64%64\% of updates at a tolerance of 0.020.02 antes. The activation term AiS(σ0)A_i^S(\sigma^0) depends only on the blueprint and the subgame, so a resolving pipeline can precompute it offline. The online per-update overhead then reduces to the opponent margin passes, which cost between 0.130.13 and 0.650.65 of an exact full-game evaluation across all five games. Specifically, this online pass costs 0.130.13 to 0.150.15 of a full-game evaluation on three-player Leduc and 0.170.17 to 0.590.59 of a full-game evaluation on six-player Kuhn. These results show that the certificate is cheap enough to run after every resolve, taking seconds where resolving takes hours at six players, so the safety check adds minimal cost to a real-time multiplayer solver as the player count grows.

We tested multi-street betting with abstraction on three-player Leduc and player scaling up to n=6n = 6 on Kuhn as two complementary axes. We did not run six-player Leduc because a four-player Leduc tree already exceeds four million nodes, and our verification protocol requires exact full-game best responses to compute the ground-truth ΔGap\Delta\mathrm{Gap}. On three-player Leduc, the standard gadget has a 2% harmful update rate and the certificate accepts 86% of its updates at tolerance 0.020.02. The bound is therefore small on most updates and large on the harmful ones.

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

This paper studies safe subgame resolving in multiplayer imperfect-information extensive-form games. The authors propose a post-hoc safety certificate to bound the increase in vulnerability after updating a player's strategy within a subgame. The bound consists of four terms: an activation term, a structural tax, best-response margin deficits, and the resolver's suboptimality. The authors establish a conditional safety guarantee based on these terms and analyze its tightness through several examples. Experiments on multiplayer games are conducted to validate the theoretical bounds and evaluate the effectiveness of the proposed methods.

Critical strengths
  1. The presentation of this paper is complete.
  2. The topic of this work is interesting and useful for the game field, especially imperfect-information games.
  3. The paper seems to provide a set of solid mathematical proofs.
Critical weaknesses
  1. Figure 1(a) does not clearly convey the information. What is the difference between two-player subgame resolving and multi-player subgame resolving? In addition, what do the square, circular, and diamond-shaped nodes in the diagram represent? Figure 1(b) mainly repeats the bound in Theorem 1 without explaining how the four terms contribute to the safety guarantee.
  2. Section 3 does not explain the value of the BR-certified margin and margin deficit. What is the motivation behind CSP? Why is CSP important in this paper?
  3. Seciton 4-6 is difficult to follow. After reading these sections, I felt completely confused and unable to grasp the core structure of the article. The organization of these sections is not good.
  4. What are the applications of the method proposed in this paper? Although five experiments are presented in Section 7, the specific application direction of this paper remains unclear.
Questions for authors

Please review my weaknesses.

6 comments

Thank you for your thoughtful review and for noting the completeness of our mathematical proofs and the relevance of the topic to imperfect-information games. We apologize that parts of the submitted manuscript were difficult to follow. We have revised Figure 1, clarified the definitions in Section 3, reorganized Sections 4 to 6, and expanded Section 6 with poker experiments that demonstrate the method in its target application. Changed words appear in red in the revised PDF. We address each of your points below.

W1. Figure 1: two-player versus multiplayer resolving, node shapes, and the four terms of the bound

We apologize that Figure 1 did not explain its visual elements or the contrast with two-player resolving clearly enough. We revised Panel (a) and the caption to address all three parts of your comment.

First, on the difference between two-player and multiplayer subgame resolving, the caption now explains why the two-player guarantee fails to transfer. With two players, whatever the single opponent gains from the resolver's update inside the subgame is the resolver's direct loss, so the opponent's margin at the subgame entry detects every harm. With three or more players, value can shift from one opponent to another while the resolver's own payoff remains unchanged, leaving the harmed opponent's margin silent. Example 2, which now precedes Theorem 1 in Section 4, works through this mechanism on a concrete three-player game.

Second, Panel (a) now carries an explicit legend for every node shape. The diamond represents the chance node, and the squares and small circles represent the decision nodes of the two opponents. The ringed circles on the boundary of the shaded box mark the entry information sets into the subgame. The large dark circles represent the resolver's decision nodes, the solid dots represent terminal nodes, and the dashed vertical line marks the public state where the subgame is cut.

Third, the caption for Panel (b) now explains what each of the four terms in Theorem 1 charges. Each term retains its distinct color in the bound. The solve error bounds the resolver's own unrealized gain inside the subgame, and the activation term measures the subgame value that the blueprint left unrealized before the update. The margin deficits sum the opponents' best-response gains inside the subgame, and the structural tax Θ\Theta captures the maximum change in total utility across players, which vanishes in constant-sum games.


W2. The value of the BR-certified margin and margin deficit; the motivation for CSP

We apologize that Section 3 introduced the margin and deficit formally before explaining their meaning in words. Section 3 now explains what both quantities measure before stating their definitions, and every technical term is defined at first appearance.

In a resolving gadget, each opponent at an entry information set chooses between terminating to collect the counterfactual value promised by the blueprint, or entering the subgame to exploit the updated strategy. The best-response-certified (BR-certified) margin measures how much an opponent can gain by entering the subgame and best-responding to the updated strategy, relative to that promised blueprint value. A nonnegative margin certifies that the opponent cannot improve over the blueprint promise at that entry, while a negative margin records the exact shortfall. The margin deficit aggregates these shortfalls across all entry information sets, weighting each entry by its counterfactual reach probability so that rarely reached entries contribute proportionally little. Theorem 1 charges the sum of the opponents' margin deficits.

Regarding constant-sum polymatrix (CSP) games, the submission introduced this class in the main text to bound the structural tax Θ\Theta via the game's distance δ∞\delta_\infty to the nearest constant-sum polymatrix game. In the revised paper, we define the structural tax Θ\Theta directly in Section 4 as the oscillation of total utility across the players. By Corollary 5, this tax is identically zero for every constant-sum game, including rake-free poker. All material on the distance δ∞\delta_\infty to constant-sum polymatrix games now resides in Appendix E, which shows why δ∞\delta_\infty gives an a priori bound on Θ\Theta and why that bound is loose on poker trees. A reader of the main text no longer needs the constant-sum polymatrix class to follow the definitions, Theorem 1, or the proofs.

W3. Organization and readability of Sections 4 to 6

We apologize that the organization of Sections 4 to 6 made the core structure hard to grasp. We have reorganized the paper into a linear progression, removed all internal working vocabulary and instance identifiers from the entire manuscript, and added a reader's guide at the end of Section 1.

Section 3 now defines the best-response gap GapG\mathrm{Gap}_G (Definition 3, replacing the term "vulnerability"), which is the largest gain any single player obtains by deviating, and compares it directly with NashConv.

Section 4 now opens by defining the three remaining quantities of the bound: the structural tax Θ\Theta, the activation term, and the solve error. Immediately after these definitions, Examples 1 to 3 illustrate the three distinct channels through which a subgame update can increase GapG\mathrm{Gap}_G, with one small example per channel, before Theorem 1 is stated. Section 4 then presents Theorem 1 using the structural tax Θ\Theta only, followed by five corollaries in a logical sequence, including the new Corollary 4 for the NashConv form (proved in Appendix C.5) and Corollary 5 for constant-sum games. Section 4 closes with dedicated Scope and Cost paragraphs.

Section 5 contains the proof of Theorem 1 (built on Lemma 1 for constant total utility) and establishes tightness on realized instances in Propositions 1 to 3.

Section 6 is now a unified Experiments section presenting Tables 1 to 4 on multiplayer poker, with the submission's random-game checks summarized at the end of the section and preserved in full in Appendices K and L.


W4. Applications of the proposed method

Our method is a safety check for real-time multiplayer solvers that refine a blueprint strategy by subgame resolving, which is the third contribution of our revised paper. We thank you for this question, as it led us to state the application plainly, and we apologize that the original text left it unclear. Beyond two players, subgame resolving has no safety guarantee and can raise the profile's best-response gap. In practice, a solver first resolves the subgame at a reached state. Next, it runs one subgame best-response pass per opponent to obtain the certificate BcacheB_{\mathrm{cache}}, which is a baseline-aware upper bound on the best-response gap change ΔGap\Delta\mathrm{Gap}. The agent plays the update if BcacheB_{\mathrm{cache}} is within a chosen safety tolerance tt. It keeps the blueprint otherwise, a mechanism we call gating.

We ran new experiments on this exact gating pipeline in multiplayer poker games, and the results are reported below and in Section 6 of the revised paper. The evaluation covers 168 updates on three-player Kuhn poker and 1,620 updates on three-player Leduc poker, which has 38,641 decision nodes and 1,134 information sets. It also tests 96 updates on Kuhn poker with the number of players nn ranging from n=3n = 3 to 66 players. Across all experiments, there are zero violations of Theorem 1 and zero harmful updates accepted by the certificate.

Three-player Kuhn and Leduc poker, pooled over blueprints

GameResolverMedian ΔGapHarmful updatesAccepted at 0Accepted at 0.02Resolver gainMax ΔGap after gating
Kuhnbest response+0.062080%0%5%+0.0164+0.0068
Kuhnstandard gadget+0.009629%0%41%+0.0082+0.0182
Kuhnbelief-corrected gadget+0.001620%0%43%+0.0087+0.0170
Leducbest response+0.000012%53%80%+0.0063+0.0094
Leducstandard gadget+0.00002%47%86%+0.0031+0.0135
Leducbelief-corrected gadget-0.00002%52%87%+0.0034+0.0083

Column legend (Table 1). Here ΔGap\Delta\mathrm{Gap} is the change in the profile's best-response gap in antes, "Harmful updates" is the share of updates with ΔGap\Delta\mathrm{Gap} above 0.020.02 antes, and "Accepted at tt" is the share of updates whose certificate BcacheB_{\mathrm{cache}} is at most tt. "Resolver gain" is the resolver's mean realized payoff gain in antes, and "Max ΔGap\Delta\mathrm{Gap} after gating" is the worst gap increase when the blueprint is kept whenever BcacheB_{\mathrm{cache}} exceeds 0.020.02 antes.

The table shows that ungated resolving frequently degrades the blueprint in three-player Kuhn poker. In particular, 80%80\% of subgame best-response updates, 29%29\% of standard CFR-D gadget updates, and 20%20\% of belief-corrected gadget updates are harmful updates that raise the best-response gap by more than 0.020.02 antes (ΔGap>0.02\Delta\mathrm{Gap} > 0.02 antes). Gating with our certificate at a tolerance of 0.020.02 antes blocks every harmful update across both games. This gating caps the worst-case best-response gap increase at +0.0182+0.0182 antes on Kuhn and +0.0135+0.0135 antes on Leduc. The gated resolver keeps a positive mean payoff gain with both gadgets. With the belief-corrected gadget, the certificate accepts 43%43\% of the updates on Kuhn and 87%87\% on Leduc. For the application, this means a solver can refine a blueprint during play and retain positive payoff gains while preventing harmful updates.

Kuhn poker with n = 3 to 6 players

nResolverMedian ΔGapHarmful updatesAccepted at 0.02Resolve (s)Certificate (s)Exact evaluation (s)
3best response+0.050980%0%0.0100.0040.003
3standard gadget+0.009740%40%0.3400.0040.004
3belief-corrected gadget+0.004320%60%0.3400.0040.004
4best response+0.0489100%0%0.0800.0480.048
4standard gadget+0.022157%43%9.820.0620.057
4belief-corrected gadget+0.002843%57%9.560.0620.058
5best response+0.023256%33%1.891.041.07
5standard gadget+0.00220%56%3001.301.31
5belief-corrected gadget+0.000011%78%3011.271.40
6best response+0.0370100%0%47.130.124.4
6standard gadget+0.012536%64%1025826.232.2
6belief-corrected gadget+0.011236%64%1018128.528.2

Column legend (Table 2). Here nn is the number of players, and "Resolve (s)", "Certificate (s)", and "Exact evaluation (s)" report the median wall-clock time in seconds for the subgame resolve, the local certificate BcacheB_{\mathrm{cache}}, and the exact full-game evaluation of ΔGap\Delta\mathrm{Gap}. The remaining columns carry the same definitions as in the first table.

As the number of players nn grows from n=3n = 3 to n=6n = 6, ungated gadget resolving continues to produce harmful updates. At n=6n = 6 players, 36%36\% of updates under both gadget resolvers are harmful updates that raise the best-response gap by more than the 0.020.02 ante tolerance. In this setting, gating with the certificate safely accepts 64%64\% of gadget updates and rejects all harmful updates. For n=6n = 6 players, computing the certificate takes a median of 26.226.2 seconds for the standard gadget and 28.528.5 seconds for the belief-corrected gadget. By contrast, the subgame resolves themselves take 10,258 seconds for the standard gadget and 10,181 seconds for the belief-corrected gadget. For the application, these runtime results show that the safety check adds little overhead as the number of players grows.

In summary, a multiplayer solver can attach our certificate after each resolve to gate subgame updates during play. The check is accurate, as it accepted no harmful update in any experiment, and useful, because the gated resolver keeps a positive payoff gain. It is also efficient at n=6n = 6 players, taking a median of 26.226.2 to 28.528.5 seconds compared to 10,181 to 10,258 seconds for the resolve itself. The abstract, introduction, and conclusion of the revised paper now state this application as our third contribution.

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

The paper proposes a safe method for subgame solving in games with more than two players. Here, "safe" means the same thing that it does in the more traditional two-player zero-sum setting: running the subgame solving algorithm will be no worse, exploitability-wise, than not running it.

Critical strengths

Subgame solving in multi-player games is an interesting problem. The method seems to be theoretically sound.

Critical weaknesses

The experimental evaluation seems to only evaluate whether the theory is sound (which is strange, given that the theorems are proven formally), not the empirical performance of the subgame solving algorithm. I would like to see empirical results that demonstrate that the algorithm reduces exploitability significantly on practical instances.

But the more important point is the writing quality. The paper has many of the common weaknesses of AI-generated writing. For example, terms are often used without formal definition and "expecting the reader to already be in the writer's head". Notation is introduced unnecessarily. And so on. This renders the paper essentially unreadable; indeed, I gave up parsing before I could understand the main technical ideas. I vote to reject on writing quality alone.

Questions for authors

None.

4 comments

Thank you for reading our submission carefully and for recognizing that safe subgame solving in multiplayer games is an interesting problem with a sound theoretical solution here. We appreciate your candid critique of the writing and the experimental design. We have rewritten the main text to make the exposition self-contained and linear, and the experiments now centre on an empirical evaluation on multiplayer Kuhn and Leduc poker. Changed text is marked in red in the revised PDF.

W1. "The experimental evaluation seems to only evaluate whether the theory is sound... I would like to see empirical results that demonstrate that the algorithm reduces exploitability significantly on practical instances."

In short: Section 6 now evaluates multiplayer Kuhn (3 to 6 players) and three-player Leduc poker. The standard gadget produces harmful updates on up to 57% of updates, whereas gating with our local certificate BcacheB_{\mathrm{cache}} accepts zero harmful updates while preserving positive payoff gains.

Testing a proven bound for counterexamples on random games verifies the implementation. We condensed those checks into the closing paragraphs of Section 6 (lines 512 to 523) and kept the full study in Appendix K (with protocol details in Appendix L). Section 6 now evaluates empirical performance on three-player Kuhn poker (168 updates), three-player Leduc poker (1,620 updates on a tree with 38,641 decision nodes and 1,134 information sets), and Kuhn poker with n=3n = 3 to 66 players (96 updates), with the results in Tables 1 and 2 on page 9.

We apologize for not stating the operational goal of our method plainly in the submission. Subgame resolving refines a blueprint strategy inside a subgame so the resolving player earns a higher payoff against opponents. In two-player zero-sum games, standard gadget resolving does this safely. With three or more players, resolving can increase the profile's exploitability without warning. Our method attaches a local certificate BcacheB_{\mathrm{cache}}, which is an upper bound on the increase of exploitability, computed from the blueprint's stored best-response gains and one subgame best-response pass per opponent. A gating rule keeps the blueprint whenever BcacheB_{\mathrm{cache}} exceeds a tolerance tt. The empirical question is whether standard resolvers cause harmful exploitability increases on poker benchmarks, and whether gating with BcacheB_{\mathrm{cache}} blocks those harmful updates while preserving the resolver's payoff gains.

Three-player Kuhn and Leduc poker, pooled over blueprints

GameResolverMedian ΔGapHarmful updatesAccepted at 0Accepted at 0.02Resolver gainMax ΔGap after gating
Kuhnbest response+0.062080%0%5%+0.0164+0.0068
Kuhnstandard gadget+0.009629%0%41%+0.0082+0.0182
Kuhnbelief-corrected gadget+0.001620%0%43%+0.0087+0.0170
Leducbest response+0.000012%53%80%+0.0063+0.0094
Leducstandard gadget+0.00002%47%86%+0.0031+0.0135
Leducbelief-corrected gadget-0.00002%52%87%+0.0034+0.0083

Kuhn poker with n = 3 to 6 players

nResolverMedian ΔGapHarmful updatesAccepted at 0.02Resolve (s)Certificate (s)Exact evaluation (s)
3best response+0.050980%0%0.0100.0040.003
3standard gadget+0.009740%40%0.3400.0040.004
3belief-corrected gadget+0.004320%60%0.3400.0040.004
4best response+0.0489100%0%0.0800.0480.048
4standard gadget+0.022157%43%9.820.0620.057
4belief-corrected gadget+0.002843%57%9.560.0620.058
5best response+0.023256%33%1.891.041.07
5standard gadget+0.00220%56%3001.301.31
5belief-corrected gadget+0.000011%78%3011.271.40
6best response+0.0370100%0%47.130.124.4
6standard gadget+0.012536%64%1025826.232.2
6belief-corrected gadget+0.011236%64%1018128.528.2

Column legend: ΔGap\Delta\mathrm{Gap} is the change in the profile's best-response gap GapG\mathrm{Gap}_G

(the largest gain any single player obtains by deviating) caused by an update, in antes, where "Harmful updates" is the share with ΔGap>0.02\Delta\mathrm{Gap} > 0.02 antes and "Accepted at tt" is the share with certificate Bcache≤tB_{\mathrm{cache}} \le t. "Resolver gain" is the resolver's mean realized payoff gain, "Max ΔGap\Delta\mathrm{Gap} after gating" is the worst gap increase when retaining the blueprint whenever Bcache>0.02B_{\mathrm{cache}} > 0.02, and the final three columns report median wall-clock seconds for the subgame resolve, the local certificate, and the exact full-game evaluation of ΔGap\Delta\mathrm{Gap}.

We evaluated 168168 updates on three-player Kuhn, 1,620 updates on three-player Leduc, and 9696 updates on nn-player Kuhn, where nn is the number of players. Across these tests, the standard two-player CFR-D gadget produces harmful updates on 29%29\% of three-player Kuhn updates, 2%2\% of Leduc updates, and 36%36\% of six-player Kuhn updates. Using a belief-corrected root measure cuts the share of harmful updates on three-player Kuhn from 29%29\% to 20%20\%. It also reduces the median best-response gap change ΔGap\Delta\mathrm{Gap} from +0.0096+0.0096 antes to +0.0016+0.0016 antes. Gating with the certificate BcacheB_{\mathrm{cache}} accepts zero harmful updates across all games and resolvers, keeping the worst post-gating ΔGap\Delta\mathrm{Gap} below the 0.020.02 ante tolerance. The gated resolver keeps a positive mean payoff gain with both gadgets. In six-player Kuhn, computing the certificate takes 26.226.2 seconds, whereas the gadget resolve takes 10,258 seconds. We conclude that our method has direct practical value: ungated multiplayer resolving is unsafe, while gating with the certificate eliminates harmful updates and preserves a positive payoff gain. Because the certificate checks any update using only subgame best responses, it attaches directly as a safety check to real-time multiplayer solvers that refine a blueprint (our third contribution, lines 119 to 124).


W2. "The paper has many of the common weaknesses of AI-generated writing. For example, terms are often used without formal definition... Notation is introduced unnecessarily."

In short: We rewrote the main text to remove all internal jargon, define every technical concept in words at first use, move excess notation to the appendix, and present concrete examples before stating our main theorem. A roadmap now ends Section 1, and Figure 1 is redrawn as pictures.

The language of our submission was indeed polished with AI assistance, as disclosed in the paper's AI use statement. The technical content, proofs, and experiments are our own, and we checked the text line by line. That polishing nevertheless left our internal working vocabulary undefined and assumed immediate familiarity with terms from the two-player safe subgame solving literature (such as gadget games, margins, and counterfactual values). We are sorry for the reading difficulty this caused.

We revised the whole main text to fix both issues:

  • Every technical term is defined at first use, and internal jargon is gone. We removed all internal working vocabulary from the paper (words such as caliber, arm, pilot, screening, M1, and instance identifiers such as gid78). Every technical concept is now defined in words where it first appears: entry information set, root measure, best-response-certified (BR-certified) margin, margin deficit, activation term, solve error, margin-certified, and trunk. Section 3 explains in plain language what the two core objects measure before giving any formulas (lines 186 to 206). The BR-certified margin measures how much an opponent can gain by exploiting the updated strategy inside the subgame relative to the blueprint value. The margin deficit sums these violations across entry information sets, weighted by how often each entry set is reached. Profile exploitability is defined once as the best-response gap GapG\mathrm{Gap}_G (Definition 3, line 207), which is the largest payoff gain any single player can achieve by deviating, and Section 3 compares GapG\mathrm{Gap}_G in one paragraph with NashConv\mathrm{NashConv} (the sum of single-player deviation gains across all players, lines 209 to 215).
  • Unnecessary notation is removed from the main text. Constant-sum polymatrix games and the distance δ∞\delta_\infty to them no longer appear in the main text, which keeps a single pointer to Appendix E (line 335). The random-game sweep notation is in Appendix K. Lemma 1 is stated directly for games with constant total utility (lines 347 to 358), and Lemma 2 states only the bound on the change of total utility. Theorem 1 uses only the structural tax Θ\Theta, which measures how much the players' total utility can change (lines 277 to 290). The main text now contains one theorem and five corollaries.
  • Each term is explained in words, and examples precede the theorem. Section 4 opens by stating its role (lines 226 to 227). It defines the structural tax, the activation term, and the solve error in three labeled paragraphs. Each paragraph describes what the term measures before providing the formula (lines 228 to 244). Examples 1 to 3 follow (lines 245 to 276), so the reader meets each cause of harm on its own small game before reaching Theorem 1 (line 277). In particular, Example 2 shows why the two-player safety proof breaks with three players: an update can shift payoff from one opponent to another while leaving the resolver's payoff unchanged, so the harmed opponent's subgame margin stays zero while full-game exploitability rises.
  • Navigation and Figure 1. Section 1 now ends with a roadmap. It follows the argument and explains the order of the sections (lines 125 to 133). Sections 3, 4, and 5 each open with a statement of their role (lines 161, 226, and 341). Figure 1 is redrawn and now sits on page 2. Panel (a) includes a legend for the node shapes. Panel (b) no longer shows a formula. It shows the subgame of panel (a) three times to represent the blueprint, the resolve, and the certification, and thick edges mark the actions played by the resolver. Colored arrows carry the four terms of the bound from these pictures into one bar. A decision tree below the bar shows the resolver playing the update when the bound is within the tolerance and keeping the blueprint otherwise.

We sincerely thank you for your candid feedback on the presentation, which helped us make the paper much easier to read. We would be grateful if you could take another look at Figure 1 and Sections 3 and 4 in the revised draft. If the revision resolves your concerns, we kindly and respectfully ask you to consider raising your score, and we remain very happy to answer any remaining questions.

Dear Reviewer,

Thanks for your time and effort in reviewing our paper.

We hope our response has adequately addressed your concerns. If you feel that our rebuttal has clarified the issues raised, we kindly ask you to consider adjusting your score accordingly. Should you have any further questions or need additional clarification, we would be more than happy to discuss them with you.

Thanks once again for your valuable feedback.

Best regards,

Authors

Reviewer_HcA8OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper consider subgame resolving in nn-player imperfect-information extensive-form games (IIEFG). Games like poker are too large to be solved in one pass. Instead, one first computes a blueprint -- a complete strategy profile σ0\sigma^0 for the whole game, typically computed offline by running CFR on an abstraction of the game. Then, during play, the part of game actually reached is re-solved in real time and the blueprint is refined only inside that subgame (subgame resolving). In two-player zero-sum games resolving is known to be safe, i.e., it never increases exploitability (Burch et al 2014, Moravcik et al 2016, Brown and Sandholm 2017). For three or more players no such guarantee exists and systems like Pluribus resolve heuristically. The authors target this gap.

In Section 3, the authors set up the problem. A single player ii, the resolver, changes their own strategy only inside a public subgame SS while all other players keep playing σ0\sigma^0. The quantity they want to control is the vulnerability of a profile, Vul(σ)=max⁡pAp(σ)\mathrm{Vul}(\sigma) = \max_p A_p(\sigma), where ApA_p is the gain of player pp from best-responding.

In Section 4, the main result (Theorem 1) states that for any such update σ1\sigma^1, Vul(σ1)−Vul(σ0)≤max⁡(εi,  AiS(σ0)−εi+∑q∈OMq+Θ),\mathrm{Vul}(\sigma^1)-\mathrm{Vul}(\sigma^0)\le\max\Big(\varepsilon_i,\;A^S_i(\sigma^0)-\varepsilon_i+\sum_{q\in O}M_q+\Theta\Big), where

  • AiS(σ0)A^S_i(\sigma^0) is the "activation" term, i.e., the value in the subgame that the blueprint did not realize for the resolver,
  • εi\varepsilon_i is how far the resolver falls short of that value (the authors call it "solve error"),
  • MqM_q is the (mass-weighted) amount by which the best-response-certified margins of opponent qq are negative,
  • Θ\Theta is a "structural tax" that measures how much the total utility can change. It is zero on constant-sum games and is upper bounded by 2nδ∞2n\delta_\infty, where δ∞\delta_\infty is the distance of the game from the class of constant-sum polymatrix (CSP) games.

In Sections 5 and 6, the authors give the proof and a number of variants of the bound, and they construct small games where each term is attained with equality (Examples 1-3). They also make the obsevation that the standard gadget weights the beliefs of the opponents incorrectly when n>2n>2 (Prop. 5), and they show with LP dual certificates that poker-like games are far from CSP (Prop. 2).

In Section 7, the authors run experiments on 162 random three-player game trees. No counterexample to the theorem is found and they report how many updates each version of the bound accepts.

Critical strengths
  • The question is natural and well-motivated. Multiplayer resolving is used in practice (Pluribus) without any guarantee, and a certificate that can be computed after resolving is a reasonable first step.
  • I went through Lemma 1, Lemma 2, Theorem 1, the corollaries and Examples 1-3 and I believe they are correct. The proofs are complete and the appendix makes clear which step uses which assumption.
  • The authors make a good job in isolating each term of the bound with a small example. Example 2 in particular is the most interesting part of the paper in my opinion: value moves from one opponent to another while the resolver's payoff does not change, which shows why one has to sum the margins over all opponents.
  • Prop. 5 could be of independent interest for people that implement multiplayer search.
Critical weaknesses
  • The choice of Vul\mathrm{Vul} as the measure is not well justified. The proof of Theorem 1 essentially follows from ΔAp=ΔBRvalp−gp\Delta A_p = \Delta \mathrm{BRval}_p - g_p (where gpg_p is the change in the payoff of pp), together with ΔBRvali=0\Delta\mathrm{BRval}_i=0 and ΔBRvalj≤Mj\Delta\mathrm{BRval}_j\le M_j.

If one sums over the players instead of taking the max, i.e., considers NashConv=∑pAp\mathrm{NashConv}=\sum_p A_p which is the standard measure in multiplayer games (e.g., in OpenSpiel [1]), the same steps give Δ NashConv≤∑q∈OMq+Θ,\Delta\,\mathrm{NashConv}\le\textstyle\sum_{q\in O}M_q+\Theta, without the activation and the solve error terms. For constant-sum games this means that a margin-certified update does not increase NashConv, which would be the natural multiplayer version of safe resolving. In Example 1, AiA_i goes down by 1 and AjA_j goes up by 1 so NashConv stays the same. So, if I am not missing something, the activation term appears only because of the max. Further, the claim in Section 3 that multiplayer exploitability "has no canonical definition" is not accurate.

  • It is not clear what "safe" means for the resolver when n>2n>2. In two-player zero-sum games, an increase of AjA_j is exactly the loss of the resolver. In Example 2 though, the loss of jj is the gain of kk and the payoff of the resolver does not change. Also, Vul\mathrm{Vul} includes the resolver's own AiA_i. I would expect a notion that measures how much the resolver itself can be exploited (e.g., the vulnerability of MacQueen and Wright [2]). Note also that [2] uses the word "vulnerability" for a different quantity which can be confusing.

  • The paper provides a certificate but not a resolving algorithm that is safe. In the two-player case, the Terminate option of the gadget guarantees nonnegative margins. Here, there is no procedure that guarantees this and Prop. 5 shows that the standard gadget does not. The only safe way to use the result is to resolve, compute the bound and then accept or reject the update. But the bound rarely accepts: at tolerance 0, the forms of Theorem 1 accept none of the 143 safe updates and BdirB_{\text{dir}} accepts 2. Would it be possible to design a resolving objective that directly optimizes the certifcate?

  • The technical contribution is rather limited. Once the identity above is written down, Theorem 1 takes a few lines and the main step (S4) is the argument of Burch et al. (2014) with the correct weights. Moreover, the proof only uses that the total utility is (nearly) constant. δ∞\delta_\infty only appears through a looser upper bound that is also more expensive to compute (381x the cost of exact evaluation vs 28x for Θ\Theta), and it is ≥1\ge 1 for poker (Prop. 2) where Θ=0\Theta=0 anyway. I am afraid that a big part of the paper (Lemma 3, Prop. 1, Prop. 2 and Appendices D-E) is about δ∞\delta_\infty and not really about resolving. Lemma 1 could also be stated for constant-sum games directly.

  • The theorem needs exact subgame best responses up to the terminals of SS. This does not cover depth-limited search with leaf values [3], which is what DeepStack, Libratus and Pluribus actually use. Hence, the claim in the conclusion that multiplayer resolving "now rests on conditions an implementer can check" is too strong. Similarly, the claim that "current resolving implementations also misreport their margins" refers to the authors' own implementation (Appendix J).

  • The experiments are limited. They are carried over on random trees of depth at most 3 with n=3n=3, and on all 162 instances computing the exact ΔVul\Delta\mathrm{Vul} from cached values is faster than computing the bound. Searching for counterexamples of a proven theorem only checks the code. The two-term fits and the nn-sweep do not seem to support a clear conclusion either. It would be interesting to see experiments on 3-player Kuhn or Leduc poker, and a comparison with maxmargin or the resolving gadget in terms of the resolver's payoff (see also [4]).

  • The text is very dense and hard to follow. A lot of internal vocabulary is used without definition in the main text ("caliber", "arm", "gid78", "kill filter", "pilot constants") and there are many versions of the bound. It took me a while to see the the simple identity behind the main theorem. Minor: Vul\mathrm{Vul} is the maximum best-response gap (i.e., the ε\varepsilon of an ε\varepsilon-Nash equilibrium), while "vulnerability" in [2] is the utility a strategy loses when the other players change their strategies, so I would suggest to rename it or state the difference explicitly; players are indexed from 1 in Section 3 and from 0 in Appendix B; the conclusion lists "1.5x a cached exact evaluation" as an advantage; [4] is now published at IJCAI 2026; there is no code.

In conclusion, I believe that the paper addresses an interesting open problem and the results are correct. Nevertheless, the main theorem follows from a rather simple argument, the measure that is used makes the bound look more complicated than it needs to be, and the experiments do not show that the certificate is useful in practice. I would be willing to raise my score if the authors (i) discuss NashConv or justify the use of Vul\mathrm{Vul}, (ii) move most of the δ∞\delta_\infty material to the appendix, and (iii) show that the certificate is useful in a actual multiplayer game.


[1] Lanctot, M., Lockhart, E., Lespiau, J.B., Zambaldi, V., Upadhyay, S., Pérolat, J., et al., 2019. OpenSpiel: A framework for reinforcement learning in games.

[2] MacQueen, R. and Wright, J.R., 2023. Guarantees for self-play in multiplayer games via polymatrix decomposability.

[3] Brown, N., Sandholm, T. and Amos, B., 2018. Depth-limited solving for imperfect-information games.

[4] Kubíček, O., Lisý, V. and Sandholm, T., 2026. Equilibrium refinements improve subgame solving in imperfect-information games. IJCAI 2026.

Questions for authors
  • What does an increase of Vul\mathrm{Vul} imply for the payoff of the resolver when n>2n>2?

  • Do you think there is a resolving procedure that guarantees nonnegative BR-certified margins for n>2n>2, similar to the Terminate option in two-player gadgets?

  • What would be the main challenge in extending your results to depth-limited subgames with leaf values?

  • Can you include experiments on 3-player Kuhn or Leduc poker? It would help your claims in my opinion.

6 comments

Thank you for carefully verifying our proofs, for your valuable comments, and for stating the three conditions that would raise your score. We have completed all three requests in the revised paper. Specifically, the NashConv\mathrm{NashConv} bound is now Corollary 4 while Section 3 justifies our use of the maximum gap, the δ∞\delta_\infty material is moved to Appendix E so Theorem 1 uses the structural tax alone, and Section 6 evaluates the certificate on three-player Kuhn and Leduc poker as well as Kuhn poker with up to six players. In the revised PDF, modified text appears in red, and the general response lists all revisions.

===

W1. Choice of measure (NashConv\mathrm{NashConv} versus the maximum) and "no canonical definition"

Thank you for pointing out the NashConv\mathrm{NashConv} derivation, which we have added to Section 4 as Corollary 4 (proved in Appendix C.5). Let ApA_p be player pp's best-response gain, BRvalp\mathrm{BRval}_p be player pp's best-response value, and gpg_p be player pp's payoff change from the update. Summing the identity ΔAp=ΔBRvalp−gp\Delta A_p = \Delta\mathrm{BRval}_p - g_p across all players, using ΔBRvali=0\Delta\mathrm{BRval}_i = 0 for the resolver ii and ΔBRvalq≤Mq\Delta\mathrm{BRval}_q \le M_q for each opponent qq's margin deficit MqM_q, yields ΔNashConv≤∑q∈OMq+Λ≤∑q∈OMq+Θ\Delta\mathrm{NashConv} \le \sum_{q\in O} M_q + \Lambda \le \sum_{q\in O} M_q + \Theta, where OO is the set of opponents, Λ=−∑pgp\Lambda = -\sum_p g_p is the realized total-utility leak, and Θ\Theta is the structural tax. In a constant-sum game, a margin-certified update never increases NashConv\mathrm{NashConv}. We replayed the 162 random-game updates from the submission under Corollary 4.

NashConv replay of the 162 random-game updates

Quantitycount
replayed updates162
violations of ΔNashConv ≤ Σ_q M_q + Λ0
violations of ΔNashConv ≤ Σ_q M_q + Θ0
updates with ΔGap ≤ 053
updates with ΔNashConv ≤ 0119
ΔGap ≤ 0 but ΔNashConv > 00
ΔNashConv ≤ 0 but ΔGap > 066
harmful, ΔGap > 0.0219
harmful, ΔNashConv > 0.0215

Column legend. ΔGap\Delta\mathrm{Gap} is the change in the profile's maximum best-response gain, and ΔNashConv\Delta\mathrm{NashConv} is the change in the sum of best-response gains across all players. MqM_q is opponent qq's margin deficit, Λ\Lambda is the realized total-utility leak, and Θ\Theta is the structural tax.

Across all 162162 tested updates, our bound on NashConv\mathrm{NashConv}, the sum of single-player best-response gains, holds with 00 violations. Moreover, 6666 of those 162162 updates keep NashConv\mathrm{NashConv} non-increasing while raising the maximum best-response gap GapG\mathrm{Gap}_G. These results show that our theoretical guarantee covers both evaluation measures used beyond two players, allowing a practitioner to apply the certificate under either criterion.

We kept the maximum gap GapG\mathrm{Gap}_G as the headline measure because the maximum and the sum certify different properties, as Section 3 now explains. The maximum GapG(σ)=max⁡pAp(σ)\mathrm{Gap}_G(\sigma) = \max_p A_p(\sigma) for a strategy profile σ\sigma is the ε\varepsilon of an ε\varepsilon-Nash equilibrium, so bounding it guarantees that no single player becomes more exploitable. The sum can remain unchanged while a single opponent's incentive to deviate doubles. In Example 1, the resolver's gain AiA_i drops from 1 to 0 while opponent jj's gain AjA_j rises from 1 to 2, leaving NashConv\mathrm{NashConv} constant at 2 while doubling opponent jj's deviation gain. The activation term and the solve error are the price of a per-player guarantee.

We apologise for the inaccurate sentence claiming that multiplayer exploitability has "no canonical definition." We removed that sentence, and Section 3 now discusses both NashConv\mathrm{NashConv} (citing OpenSpiel) and the best-response gap GapG\mathrm{Gap}_G.

W2 and Q1. What "safe" means for the resolver when n>2n > 2, and terminology

Theorem 1(i) states the guarantee for the resolver ii when moving from the blueprint profile σ0\sigma^0 to the updated profile σ1\sigma^1 in subgame SS: Ai(σ1)−Ai(σ0)=εi−AiS(σ0)≤εiA_i(\sigma^1) - A_i(\sigma^0) = \varepsilon_i - A_i^S(\sigma^0) \le \varepsilon_i, where εi\varepsilon_i is the solve error and AiS(σ0)A_i^S(\sigma^0) is the activation term. At the same time, the resolver's expected payoff against the blueprint opponents increases by AiS(σ0)−εiA_i^S(\sigma^0) - \varepsilon_i. Thus, the resolver's own deviation gain never grows by more than its solve error εi\varepsilon_i. Any increase in the profile's gap GapG\mathrm{Gap}_G beyond εi\varepsilon_i means an opponent became more able to profit by deviating, as happens in Example 2. Because subgame resolving modifies the joint profile that the system deploys, safety is a property of that deployed profile, just as two-player exploitability is a property of the pair of strategies. Two-player resolving bounds the resolver's own loss directly only because one player's gain equals the other's loss when the number of players is n=2n = 2, an identity that breaks for n>2n > 2. We added this explanation right after Theorem 1.

Following your suggestion, we renamed the measure from "vulnerability" to the best-response gap GapG\mathrm{Gap}_G (Definition 3). Section 3 explicitly notes that GapG\mathrm{Gap}_G differs from the vulnerability defined by MacQueen and Wright (2023), which tracks the payoff a player loses when other players alter their strategies.


W3 and Q2. Certificate versus a safe resolving algorithm, acceptance rates, and nonnegative margins

In short: Gating with BcacheB_{\mathrm{cache}} accepts up to 87%87\% of three-player Leduc updates with zero harmful updates, and shrinking updates by λ=0.25\lambda = 0.25 removes almost all harm. Because opponent counterfactual measures conflict when n>2n > 2, no single gadget root measure guarantees nonnegative margins simultaneously.

Although acceptance at tolerance t=0t = 0 was rare on the small random trees in the submission, acceptance on standard poker subgames is high (Section 6). Using the baseline-aware certificate BcacheB_{\mathrm{cache}}, we implement gated resolving: the solver plays the updated strategy when Bcache≤0.02B_{\mathrm{cache}} \le 0.02 antes, and keeps the blueprint strategy σ0\sigma^0 otherwise.

Three-player Kuhn and Leduc poker, pooled over blueprints

GameResolverMedian ΔGapHarmful updatesAccepted at 0Accepted at 0.02Resolver gainMax ΔGap after gating
Kuhnbest response+0.062080%0%5%+0.0164+0.0068
Kuhnstandard gadget+0.009629%0%41%+0.0082+0.0182
Kuhnbelief-corrected gadget+0.001620%0%43%+0.0087+0.0170
Leducbest response+0.000012%53%80%+0.0063+0.0094
Leducstandard gadget+0.00002%47%86%+0.0031+0.0135
Leducbelief-corrected gadget-0.00002%52%87%+0.0034+0.0083

Column legend. ΔGap\Delta\mathrm{Gap} is the change in the best-response gap in antes, "Harmful updates" is the share of updates with ΔGap>0.02\Delta\mathrm{Gap} > 0.02, and "Accepted at tt" is the share of updates with certificate Bcache≤tB_{\mathrm{cache}} \le t. "Resolver gain" is the resolver's mean realized payoff gain, and "Max ΔGap\Delta\mathrm{Gap} after gating" is the worst gap increase when keeping the blueprint whenever Bcache>0.02B_{\mathrm{cache}} > 0.02.

We evaluated the certificate BcacheB_{\mathrm{cache}} across 1,620 updates on three-player Leduc. For the standard gadget, gating with BcacheB_{\mathrm{cache}} accepts 47%47\% of updates at a tolerance of 00 antes and 86%86\% of updates at a tolerance of 0.020.02 antes. For the belief-corrected gadget, gating accepts 52%52\% of updates at a tolerance of 00 antes and 87%87\% of updates at a tolerance of 0.020.02 antes. Across all 168168 Kuhn updates and 1,620 Leduc updates, gating accepts zero harmful updates. It keeps the worst post-gating best-response gap change ΔGap\Delta\mathrm{Gap} for the standard gadget below the 0.020.02 ante tolerance, reaching at most +0.0182+0.0182 antes on Kuhn and +0.0135+0.0135 antes on Leduc. The gated resolver keeps a positive mean payoff gain with both gadgets. We conclude that the method provides clear practical value: ungated multiplayer resolving is unsafe, whereas gating with our certificate eliminates harmful updates and preserves a positive payoff gain. Because the certificate evaluates any delivered update using only best responses inside the subgame, it attaches directly as a safety check to real-time multiplayer solvers that refine a blueprint (our third contribution).

A second way to use the framework is shrinking the update toward the blueprint by a step size λ∈(0,1]\lambda \in (0, 1] (Appendix J).

Shrinking the standard-gadget update toward the blueprint

Gameλ#matchedmean ΔGapharmfulmean g_i
Kuhn0.2556+0.00012%+0.0020
Kuhn0.5056+0.00389%+0.0040
Kuhn0.7556+0.009218%+0.0061
Kuhn1.0056+0.015929%+0.0082
Leduc0.25540-0.00070%+0.0007
Leduc0.50540-0.00101%+0.0015
Leduc0.75540-0.00121%+0.0023
Leduc1.00540-0.00092%+0.0031

Column legend. λ\lambda is the interpolation fraction from the blueprint to the standard-gadget update across #matched updates. The remaining columns report the mean ΔGap\Delta\mathrm{Gap} in antes, the share of harmful updates (ΔGap>0.02\Delta\mathrm{Gap} > 0.02), and the resolver's mean payoff gain gig_i.

Setting the step size λ=0.25\lambda = 0.25 shrinks the subgame update toward the blueprint. This change cuts the share of harmful updates for the standard gadget from 29%29\% to 2%2\% on Kuhn and from 2%2\% to 0%0\% on Leduc. At the same time, the resolver maintains a positive mean payoff gain of +0.0020+0.0020 antes on Kuhn and +0.0007+0.0007 antes on Leduc. These findings show that a simple modification of an existing resolver removes almost all harm while preserving a positive payoff gain, making our framework simple to deploy in practice.

Regarding Q2, no single gadget root measure can guarantee nonnegative best-response-certified margins for all opponents when n>2n > 2 (end of Section 5). In a two-player game, the Terminate action works because the gadget's root probability weights each entry node ee by ceπ−j(e)c_e \pi_{-j}(e), where cec_e is the chance reach probability and π−j(e)\pi_{-j}(e) is the reach probability of the players other than jj. When n>2n > 2, opponent jj requires the weight ceπ−j(e)c_e \pi_{-j}(e) while opponent kk requires ceπ−k(e)c_e \pi_{-k}(e). Because π−j\pi_{-j} and π−k\pi_{-k} omit different players, a single gadget tree cannot apply both counterfactual measures at once.

Minimum gadget margin of the two opponents under four root measures (three-player Kuhn)

blueprintpubresolverc_e·π_ic_e·Π_p π_pc_e·π_{-q}, opp. 1c_e·π_{-q}, opp. 2
cfr200b2-0.432 / -1.097-0.386 / -0.102-0.432 / -1.097-0.386 / -0.102
cfr200b3-0.433 / -0.688-0.404 / -0.032-0.433 / -0.688-0.404 / -0.032
cfr200k1-0.025 / -0.016-0.025 / -0.016-0.025 / -0.016-0.025 / -0.016
cfr200k2-0.023 / -0.027-0.037 / -0.006-0.023 / -0.027-0.037 / -0.006
cfr200k3+0.004 / -0.014+0.004 / -0.016+0.004 / -0.014+0.004 / -0.016
cfr1000b2-0.422 / -0.991-0.015 / -0.029-0.422 / -0.991-0.015 / -0.029
cfr1000b3-0.423 / -0.669-0.040 / -0.016-0.423 / -0.669-0.040 / -0.016
cfr1000k1-0.026 / -0.011-0.026 / -0.011-0.026 / -0.011-0.026 / -0.011
cfr1000k2-0.034 / -0.072-0.011 / -0.076-0.034 / -0.072-0.011 / -0.076
cfr1000k3-0.021 / -0.007-0.002 / -0.004-0.021 / -0.007-0.002 / -0.004

Column legend. For each blueprint (cfr200 or cfr1000), public subgame (pub), and resolver index, each cell lists the minimum gadget margin for opponent 1 followed by opponent 2 under four root measures: the standard measure ce⋅πic_e \cdot \pi_i, the belief-corrected measure ce⋅∏pπpc_e \cdot \prod_p \pi_p, and each opponent's own counterfactual measure ce⋅π−qc_e \cdot \pi_{-q}.

Across all 40 cells of this three-player Kuhn table, no root measure makes both opponents' minimum margins nonnegative simultaneously. A resolving objective that optimizes the certificate directly would have to combine all opponents' margins under these conflicting measures. We see it as the natural next step.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.