acceptodds
Under review as a conference paper at ICLR 2027

When Low-Rank Payoff Compression Changes Equilibrium Structure

Abstract

Low-rank compression is a common way to shrink the payoff matrix of a large zero-sum game, and the best rank- spectral approximation is the default compressor. Spectral accuracy measures how faithfully payoffs are reproduced, so it leaves open whether the equilibrium set survives. We show that it can fail at any accuracy: the equilibrium sets of a game and of its best rank- approximation can stay a constant distance apart while the spectral error tends to zero. The same failure appears in the sequence form of Leduc poker and in three structurally different matrix-game families, at spectral errors down to . The mechanism is selection. When a perturbation of scale breaks a tie among equilibria, a compression residual is amplified by on the equilibrium face once global support containment holds, and an explicit family attains the displacement . Two guarantees separate the two questions. Set fidelity is local and conditional: face exactness, a uniform separation of outside actions, and a local gap-to-distance bound jointly identify the equilibrium set near a selected face. Output fidelity is pointwise: best responses on the original matrix certify the exploitability of the returned strategy whatever face generated it, and the certificate lifts from actions to strategy populations. The experiments reproduce the failure at finite spectral error on four testbeds, measure the cost of discovering the protected face without an oracle, and run the certificate inside double-oracle loops on three OpenSpiel games. The certified meta-solver returns the exact meta-solution's support in all 396 rounds, with numerically evaluated exploitability below on the perturbed current meta-game, while a blind meta-game truncation distorts the support and leaves exploitability at the payoff scale.

Primary area:
reinforcement learning
Keywords:
game theory, low-rank compression, policy-space response oracles, abstraction, multi-agent reinforcement learning

Reviews

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

SVD is a classical theory in linear algebra for matrix approximation: It first mathematically express a matrix A as a sum of rank one matrices, ordered by the singular values of A. Thus, like Taylor series in calculus, this sum can also be truncated to produce a sequence of best low-rank approximations of the original matrix, as measured in spectral norm. This paper considers the following robustness question. To what degree does low rank approximation of zero-sum game matrices alter the game's equilibria?

The main discovery of the paper, established both in theory and in experiments, is that even in the case when low-rank compression of game matrix can sufficiently approximate a game matrix, the low-rank reduction can drastically change its equilibria. One of the main reasons identified by the paper is the fact that  a small perturbation can break a tie between equilibria and cause the selected equilibrium to shift substantially. From optimization perspective, there is a fundamental distinction between approximating the payoff values and preserving which strategies are optimal for selection.

Critical strengths

The structural robustness studies of game equilibria from the lens of matrix approximation is a well motivated, both as an interesting theoretical problem, and as a computational problem. The optimization and game theoretical problem that one needs to solve in practice becomes increasingly large, thus approximation becomes necessary for practical efficiency (in this particular case, as discussed by the author(s), as the size of meta-game grows, whose payoff matrix for example describes interactions among the strategies discovered so far, solving the meta-game becomes increasingly expensive, motivating matrix compression.) Thus, characterization on the impact of approximation to the robustness of solution concept (in this case equilibria of zero-sum games) is fundamental. Technically, I like the two different aspects of fidelities analyzed in the paper: The more combinatorial and structural based set fidelity and the objective based output fidelity, and techniques for ensuring robust solutions for both under game matrix approximation.

Critical weaknesses

While I believe the research direction and results are meaningful, maybe due to my limited background, I found these discoveries are as expected. It have been widely known in the field of convex optimization and numerical analysis that high quality numerical approximation of certain objectives may lead to significant change to the structure of the optimal solutions. In addition, the zero-sum games are very special games in game theory. Unlike Nash equilibria for non-cooperative games, equilibria computation of zero-sum game is essential an (convex) optimization problem.

Questions for authors

It might be beneficial the present have a more comprehensive comparison with existing equilibrium sensitivity results, explaining precisely which new insight comes from the interaction between spectral truncation, support changes, and tie-breaking. In addition, concrete algorithmic impact for efficiently computing structurally-sound approximation of equilibria based on the theoretical insight developed in this paper would also meaningful.

3 comments

We thank the reviewer for the generous reading of the motivation and of the two fidelities. We answer the weakness and the questions.

While I believe the research direction and results are meaningful, maybe due to my limited background, I found these discoveries are as expected. It have been widely known in the field of convex optimization and numerical analysis that high quality numerical approximation of certain objectives may lead to significant change to the structure of the optimal solutions.

The paper does not claim the known general statement. What the paper supplies is which quantity, which direction and which threshold. Quantity: displacement is governed by eta/epsilon (Theorem 4.3, p.5, line 261; attained by Proposition 4.4, p.6, line 270), the residual relative to the tie-breaking scale, so residuals far below the payoff scale still flip selection. Direction: only face-direction residual eta_F matters; in new Table 11 (p.31, line 164), compressors matching blind truncation's Frobenius residual norm give displacement 0 in 8/8 cells when residuals avoid the face, even at a 1.43 full payoff perturbation above the 0.962 margin, versus 2.0 to 3.0 otherwise. Threshold: eta_F < gamma (Theorem 4.5, p.6, line 300); in new Table 12 (p.32, line 167), excerpted below, crossing eta_F/gamma = 1 moves set-inclusion error from 9.5e-15 to 5.0e-2 with the face found in both cases:

ksupportfacedim Q_xstorageeta_F/gammamax-inc<=10^-6<=10^-5
4QRE path6/6160.1321.625.0e-20/60/6
8QRE path6/6200.1660.741.5e-62/66/6
16QRE path6/6280.2371.1e-139.5e-156/66/6

None of the three follows from the generic statement.

In addition, the zero-sum games are very special games in game theory. Unlike Nash equilibria for non-cooperative games, equilibria computation of zero-sum game is essential an (convex) optimization problem.

They are, making the question answerable. Because zero-sum equilibria form an LP solution polytope, the equilibrium set has the faces, margins, and tie-breaking scale that Theorems 4.3 and 4.5 use. In general-sum games, even constant-rank bimatrix games are PPAD-hard (Mehta, 2014, now cited at p.2, line 106), precluding such set-level statements. Zero-sum games are also where low-rank compression is used: meta-games in double oracle and PSRO (§1; Table 7, p.26, line 135), rating matrices, and empirical game evaluation (§2, p.2, lines 101–107). The restriction is the result's scope, not a limitation.

It might be beneficial the present have a more comprehensive comparison with existing equilibrium sensitivity results, explaining precisely which new insight comes from the interaction between spectral truncation, support changes, and tie-breaking.

resultwhat it boundswhat it says about compression
Hoffman-type error bounds (Hoffman 2003; Facchinei and Pang 2003)distance from a point to the solution set of a fixed LP under data errorthe set of the fixed game; silent on whether the compressed game has the same set
failure of lower hemicontinuityexistence of a vanishing perturbation that moves a degenerate set by a constantqualitative; no rate, no direction
strategic stability (Kohlberg and Mertens 1986; van Damme 1991)which equilibria survive a class of perturbationsselects among equilibria; does not say which perturbations a compressor produces
this paper, Theorems 4.3 and 4.5displacement <= 2 kappa eta/epsilon; set equality under face exactness, uniform margin, eta_F < gammaspectral truncation puts its residual in the direction the selection is sensitive to; the face component, not the norm, decides (Table 11)

The interaction's new insight is that truncation discards the lowest-energy direction (the tie-breaking direction on a flat face), so the discarded residual competes with epsilon, not the payoffs. Correct support protects the face (FACE, Proposition 5.1, p.7, line 324) only if the outside margin survives, which Table 12 shows decides the k = 4 versus 16 outcome. Related Work (§2, p.3, lines 153–157) now contains this contrast.

In addition, concrete algorithmic impact for efficiently computing structurally-sound approximation of equilibria based on the theoretical insight developed in this paper would also meaningful.

Three consequences, all in the revision. (a) A compressed representation that provably keeps the whole equilibrium set: FACE at k = 16 with a support from the QRE path or from Algorithm 1 itself preserves the set to inclusion error 9.5e-15 at storage ratio 0.237 (Table 12), and the diagnostic eta_F < gamma says beforehand whether this holds. (b) A certified compressed solve where the dense LP is out of reach: at n = 32000 the dense LP needs about 142 GiB against a 64 GiB limit and is killed on 4/4 runs, while the compressed paths certify on 8/8 runs within 15.3 GiB; at n = 16000 they are 17.5 times faster than the dense LP (Table 13, p.32, line 169; §6, p.10, lines 503–515). (c) A one-round certification rule: choosing the restricted equilibrium nearest to the reference pair cuts the Leduc loop from 8 rounds to 1 on 24/24 instances (Table 10, p.31, line 163).


We thank the reviewer again and are glad to clarify anything that remains. If the concerns are resolved, we would be grateful if the reviewer would reconsider the rating.

Thanks for the expanded explanation which helped me to gain a better understanding of the paper. However, for now I will stay with my overall evaluation.

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

The paper tackles an important problem: whether compressing a zero-sum game's payoff matrix with a low-rank approximation (truncated SVD) preserves its equilibria.

The paper shows that spectral proximity doesn't guarantee this. (It can stay a constant distance apart even as the spectral error decreases, due to small perturbations breaking ties.) This is shown on matrix game families as well as Leduc poker in sequence form.

Instead, it proposes certifying solutions against the original matrix.

Critical strengths

One strength of the paper is that it clearly distinguishes between set fidelity and output fidelity (cf. line 024 in the abstract and line 059 on page 2). It shows that preserving the equilibrium set and certifying the returned strategy are different questions with different guarantees.

A second strength is that the paper reproduces the failure on different OpenSpiel games, and this reproduction is described in detail. It also includes negative findings.

Critical weaknesses

The novelty seems a bit limited in light of known perturbation results and standard practice. That small perturbations can move the equilibrium set of a degenerate game by a constant amount is already known (failure of lower hemicontinuity). The certificate is the standard exploitability check, and Algorithm 1 is essentially double oracle. The paper does not show what its amplification bound adds beyond known perturbation results.

Secondly, the paper lacks citations to existing pipelines that compress payoff matrices this way. Also, the testbeds are small enough to solve exactly. It doesn't offer an improvement, as far as I can tell, over solving exactly.

Questions for authors
  1. What does the selection-amplification bound (cf. line 231) show that doesn't already follow from the failure of lower hemicontinuity of the equilibrium correspondence? This would clarify the novelty of the contribution.

  2. Can you give some examples of existing methods or systems that compress payoff matrices with low-rank approximations for equilibrium computation, to make it clear what the negative result is addressing in practice (and warning against)?

  3. Is there a setting (like games to large for exact LP solving) where the compress-and-certify path is cheaper than solving exactly? If not, what practical recommendation follows other than "solve exactly"?

Clarification:

  1. Why does a face from an equilibrium to the original game require 6 to 10 expansions (line 415) to certify (cf. Proposition 5.5), instead of immediately? Is it because of solver degeneracy, the 10^-6 relaxation (line 1374), the 10^-9 support threshold (line 1375), or non-uniqueness of the restricted equilibrium?

Suggestion: Evaluating on games where exact solving is infeasible would test how much value certified compression has in practice.

9 comments

We thank the reviewer for the precise questions and for noting the set-versus-output distinction and the negative findings. We answer each point in order.

The novelty seems a bit limited in light of known perturbation results and standard practice. That small perturbations can move the equilibrium set of a degenerate game by a constant amount is already known (failure of lower hemicontinuity). The certificate is the standard exploitability check, and Algorithm 1 is essentially double oracle. The paper does not show what its amplification bound adds beyond known perturbation results.

Q1: What does the selection-amplification bound (cf. line 231) show that doesn't already follow from the failure of lower hemicontinuity of the equilibrium correspondence? This would clarify the novelty of the contribution.

Failure of lower hemicontinuity is a qualitative existence statement: for a degenerate game, some vanishing perturbation moves the equilibrium set by a constant. Theorem 4.3 (p.5, line 261) adds the rate, direction, and a checkable sufficient condition, none following from the existence statement.

The rate: displacement is controlled by eta/epsilon (compression residual relative to tie-breaking scale), which Proposition 4.4 (p.6, line 270) attains, so the residual must be small relative to epsilon, not the payoffs.

Direction: only the face-direction residual eta_F enters. New Table 11 (p.31, line 164) tests this on the 3 by 3 flat family (margin 0.962) with five compressors sharing blind truncation's Frobenius residual norm at the same (epsilon, k) and differing only in residual location; entries give the equilibrium's product-l1 displacement from that of M + epsilon Delta ("oo": residual confined to outside-by-outside block, eta_F = 0; "block": outside face block; "inface": face block only; †: non-singleton compressed equilibrium set, vertex choice):

epskblindooblockinfacerandom
10^-412.1609^†0.00002.0001^†0.07362.0000
10^-422.00000.00000.00002.00000.3980
10^-313.00000.00002.00090.07372.0000
10^-322.00000.00000.00002.00000.5306
10^-213.00000.00002.00920.07462.0000
10^-222.00000.00000.00002.00001.0824
10^-113.00000.00002.00530.08702.0000
10^-122.00000.00000.00002.00000.7530

A face-avoiding residual leaves the equilibrium unchanged in 8/8 cells, even when the full payoff perturbation reaches 1.43 (above the margin), whereas equal-norm blind truncation displaces it by 2.0 to 3.0: the residual's face component, not its norm, predicts displacement.

Theorem 4.5 (p.6, line 300) gives the sufficient condition (face exactness, uniform margin, eta_F < gamma) for set equality, and Table 12 (p.32, line 167) shows it correctly predicts preservation and failure across k = 4, 8 and 16. Related Work (§2, p.3, lines 153–157) now states this contrast and §4 (p.6, lines 287–293) adds the knock-out reading.

The certificate and Algorithm 1 are standard by design (§2, p.2, lines 101–107; §5, p.7, line 365). The contribution is the separation in Theorem 5.3 (p.7, line 348) between certificate correctness, holding for any seed, and cost, set by the seed; Proposition 5.5 (p.8, line 391) gives the one-round regime and Table 10 the other regime's cause (Q4 below).

Secondly, the paper lacks citations to existing pipelines that compress payoff matrices this way.

Q2: Can you give some examples of existing methods or systems that compress payoff matrices with low-rank approximations for equilibrium computation, to make it clear what the negative result is addressing in practice (and warning against)?

The revised Related Work (§2, p.2, lines 101–107) names three deployed pipelines with low-rank payoff or win-rate matrices: paired-comparison rating (Bradley-Terry, Elo) fits a rank-one win-rate matrix (Bradley and Terry, 1952); meta-game evaluation ranks agents on an empirically estimated payoff matrix (Balduzzi et al., 2018), with approximation bounds for estimated meta-games (Tuyls et al., 2020); learned low-dimensional strategy representations compress the game before solving (Fu et al., 2026). Low rank is a structural assumption, not a stability guarantee: constant-rank bimatrix games are already PPAD-hard (Mehta, 2014). The negative result warns the first two settings in particular: ranking or selecting on a low-rank fit can change which strategies are in the equilibrium support even when the fit is spectrally accurate.

Also, the testbeds are small enough to solve exactly. It doesn't offer an improvement, as far as I can tell, over solving exactly.

Q3: Is there a setting (like games too large for exact LP solving) where the compress-and-certify path is cheaper than solving exactly? If not, what practical recommendation follows other than "solve exactly"?

Suggestion: Evaluating on games where exact solving is infeasible would test how much value certified compression has in practice.

New paragraph "Scale" (§6, p.10, lines 503–515) and Table 13 (p.32, line 169) run the same instance through the dense LP (full-matrix HiGHS) and two compressed paths certified on the original matrix with Algorithm 1 (P1: truncated-SVD seed; P2: FACE) on exact low-rank family F1 (rank at most 22, 12 by 12 carrier face) and F2b (F1 plus a scale-1e-3 dense residual). Times (s), median over seeds (min-max if seeds differ by more than 2x), [certified/total]; TO: 4 h limit; OOM: killed at 64 GiB limit; ratio: same-seed dense-LP/compressed-path time; RSS: peak memory (GiB).

familyndense LPP1P2dense/P1dense/P2RSS denseRSS P1
F140007.4 [1/1]0.6 [1/1]0.7 [1/1]12.811.12.30.3
F1800026.5 [1/1]1.7 [1/1]2.1 [1/1]15.612.88.91.0
F116000119.2 [3/3]6.9 [3/3]8.0 [3/3]17.514.935.43.9
F132000OOM [0/2]27.1 [2/2]35.0 [2/2]---15.3
F2b400027.9 [1/1]1.8 [1/1]2.2 [1/1]15.412.92.30.3
F2b16000525-4969 [2/3] (TO 1)44.6 [3/3]47.7 [3/3]12.8-110.8, >32312.8-88.1, >30235.43.9
F2b32000OOM [0/2]202.0 [2/2]226.5 [2/2]---15.3

At n = 32000 the dense LP is infeasible on this machine and both compressed paths certify: the dense LP needs about 142 GiB (its measured peak is 18.5 to 19.3 times the 7.6 GiB matrix) against a 64 GiB limit and is killed on 4/4 runs, while P1 and P2 certify on 8/8 runs within 15.3 GiB with certified gap at most 4.3e-14. At n = 16000 on F1 the dense LP takes 119 s against 6.9 s for P1 (4.9 s SVD, 0.10 s certificate), 17.5x on all three seeds, up from 15.6x at n = 8000. On F2b at n = 16000 the dense LP takes 525, 4969 and more than 14400 s on the three seeds while P1 takes 41 to 45 s, so the compressed path's cost is predictable where the dense LP's is not. Two scope statements: the comparison is against the dense LP, and both compressed paths hold the full matrix for the certificate, so they save time, not memory. The recommendation is therefore not "solve exactly" but "compress, solve, certify on M": the certificate costs one best-response pass and makes a compressed solve safe to use, whereas an uncertified compressed solve is what Tables 1, 2 and 7 (p.9, line 432; p.10, line 486; p.26, line 135) show failing. Contribution 3 (p.2, lines 88–91) states both regimes.

Q4: Why does a face from an equilibrium to the original game require 6 to 10 expansions (line 415) to certify (cf. Proposition 5.5), instead of immediately? Is it because of solver degeneracy, the 10^-6 relaxation (line 1374), the 10^-9 support threshold (line 1375), or non-uniqueness of the restricted equilibrium?

We tested the four candidates on the 24 Leduc instances (Table 10, p.31, line 163); rounds are median [min, max] of restricted solves, "cert." counts instances certified at eps_cert = 1e-8:

armseed and selectorroundscert.
A0oracle support, threshold 10^-9 (paper protocol)8 [6, 10]24/24
A1oracle support, threshold 10^-68 [6, 10]24/24
A0pprecise KMvS support, default LP corner7.5 [5, 11]24/24
A2carrier face seed6.5 [5, 10]24/24
A4anearest-seed selector, target = paper oracle pair2 [2, 6]0/24
A4bnearest-seed selector, target = precise KMvS pair1 [1, 1]24/24

The cause is restricted-equilibrium non-uniqueness, not the two thresholds. The 1e-6 relaxation and 1e-9 support threshold leave the expansion trace bit-identical on 24/24 instances (A0 vs A1). The restricted-equilibrium polytope is non-singleton on 24/24 instances; the LP returns a corner with 0.73 median full-game gap and moves to another corner each round, constituting "solver degeneracy" here. Precise-support seeding alone does not help (A0p, median 7.5 rounds). Replacing the corner with the restricted equilibrium nearest the precise reference pair (A4b) certifies in 1 round on 24/24 instances with gap below 3e-13, the Proposition 5.5 regime (p.8, line 391). §6 (p.8, lines 423–426) now states this attribution.


We thank the reviewer again. The paper now concretely answers all four questions. We will gladly address anything remaining and, if these answers resolve the concerns, would appreciate the reviewer raising the rating.

Thank you for the detailed answers, the four new experiments and the revised PDF. Line numbers below refer to the revised PDF.

Q1. Novelty.

I agree that the rate η/ϵ\eta/\epsilon, attained by Proposition 4.4, does not follow from the failure of lower hemicontinuity. However, lines 155-156 and your response say that Theorem 4.3 also adds "the direction", because "only the face-direction residual ηF\eta_F enters". Theorem 4.3 assumes a bound on the full residual, ∥M+ϵΔ−W^∥max⁡≤η\Vert M + \epsilon\Delta - \widehat{W} \Vert_{\max} \leq \eta (lines 262-263). Its statement and proof never mention ηF\eta_F (lines 261-266 and 760-767). Instead, ηF\eta_F enters through condition (iii) of Theorem 4.5, as lines 874-876 note. The "oo" arm of Table 11 illustrates condition (iii) of Theorem 4.5, not Theorem 4.3. Its residual reaches η=1.43\eta = 1.43 (line 291), which violates the hypothesis 4(ϵ+η)(γ+∥M∥max⁡)<γ24(\epsilon + \eta)(\gamma + \Vert M \Vert_{\max}) < \gamma^2 of Theorem 4.3. With γ=0.962\gamma = 0.962, this hypothesis requires η<γ/4≈0.24\eta < \gamma/4 \approx 0.24, since its left side is at least 4ηγ4\eta\gamma. The "oo" arm is exact on the face with ηF=0\eta_F = 0, and M+ϵΔM + \epsilon\Delta keeps a positive margin. So conditions (i) to (iii) of Theorem 4.5 hold, and the theorem implies that the equilibrium does not move (line 310). Could you either restate and prove Theorem 4.3 in terms of ηF\eta_F, or revise lines 155-157 and 288-293 to attribute the role of ηF\eta_F to Theorem 4.5?

Lines 292-293 also say: "The residual norm does not predict the displacement; its face-direction component does." Yet the "inface" arm, whose residual lies entirely on the face block, displaces the equilibrium by 0.07 to 0.09 at k=1k = 1 but by 2.00 at k=2k = 2. By the Table 11 caption, its residual has the same Frobenius norm as the blind residual, which is smaller at k=2k = 2 than at k=1k = 1. The Frobenius norm of the face-direction residual thus does not predict the displacement either. To check whether ηF\eta_F predicts the displacement, please report η\eta and ηF\eta_F for each cell of Table 11. Please also describe how each arm's residual is built, including the "random" arm, which the caption does not define.

Your response also says that, in Table 12, the sufficient condition of Theorem 4.5 "correctly predicts preservation and failure across k = 4, 8 and 16". Line 466 likewise says that condition (iii) "decides preservation". But Theorem 4.5 gives a sufficient condition, not a necessary one, so it makes no prediction when condition (iii) fails. At k=8k = 8 with the oracle support, the median ηF/γ\eta_F/\gamma is 0.74, so at least three of the six seeds satisfy condition (iii). Conditions (i) and (ii) also hold with the oracle support, so Theorem 4.5 gives NE(M^)=NE(M)\mathrm{NE}(\widehat{M}) = \mathrm{NE}(M) for these seeds (line 310). Yet only 2/6 seeds have an inclusion error of at most 10−610^{-6}, and the median error is 1.5×10−61.5 \times 10^{-6}. By comparison, with the same support, the median error at k=16k = 16 is 9.5×10−159.5 \times 10^{-15}. All six seeds at k=8k = 8 do have an error of at most 10−510^{-5}, and lines 465-466 call k=8k = 8 "the boundary". How is the inclusion error computed, and what causes the errors above 10−610^{-6} at k=8k = 8? Per-seed values of ηF/γ\eta_F/\gamma and of the inclusion error at k=8k = 8 would help.

Your response says that the certificate and Algorithm 1 are "standard by design". It says the contribution is instead the separation in Theorem 5.3 between correctness, which holds for any seed, and cost, which depends on the seed. Theorem 5.3 follows directly from the decomposition GapM=gS+rx+ry\mathrm{Gap}_M = g_S + r_x + r_y (Appendix A.8). So I see this separation as a property of the standard best-response check.

Q2. Pipelines that compress payoff matrices.

Thank you for the new citations (lines 101-107). As described there, the pipelines you name fit "rank-one win-rate matrices", rank agents on "empirically estimated payoffs", or use learned low-dimensional representations that "compress games before solving". Your response says that the negative result "warns the first two settings in particular". Which of these pipelines computes an equilibrium of a rank-kk approximation of a payoff matrix, as blind truncation does in your experiments? The abstract calls the best rank-kk approximation "the default compressor" (lines 012-013). If no deployed pipeline computes an equilibrium of such an approximation, please soften that sentence. Lines 105-107 also cite the PPAD-hardness of constant-rank bimatrix games (Mehta, 2014) to argue that low rank is not a stability guarantee. In that paper, the rank of a bimatrix game (A,B)(A, B) is defined as rank(A+B)\mathrm{rank}(A + B). Under this definition, every zero-sum game has rank 0, and its equilibria are computable by linear programming. So this hardness result does not apply to zero-sum games, whatever the rank of their payoff matrix. Please revise or drop this citation.

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

The paper shows that even errors that are small from a low rank compression of the payoff matrix can largely affect the Nash equilibrium sets in zero sum games. The paper also establishes theoretical conditions for the preservation of equilibrium and introduces FACE, which is a compression method that is combined with best response certification, which then achieves a low exploitability. Experiments on synthetic games, Leduc poker, and also double oracle settings validate their findings, but the proposed approach is a lot slower than solving the original game directly.

Critical strengths

The theory in the paper is strong. The impossibility result, selection-sensitivity analysis, and conditional stability theorem show clearly why the spectral accuracy alone cannot guarantee preservation of equilibrium. Also, the paper has broad and very transparent experimental validation, which ranges from Leduc poker to synthetic games to double-oracle training.

Critical weaknesses

There is limited algorithmic novelty and also limited practical benefit. The procedure selected for certification is the standard double-oracle best-response expansion, and FACE requires the identification of relevant supports. The tested compression pipeline is about 12-27x slower than the LP exact baseline, which means that there might not be as much of a practical benefit to the tested compression pipeline. Also, there is limited valuation of the equilibrium-set preservation without the oracle knowledge. A lot of the FACE analysis uses supports that are derived from the oracles. The experiments without oracles certify individual equilibrium, rather than recovery, or preservation, of the full equilibrium set, which is the main motivation of this paper.

Questions for authors

Can you demonstrate a setting where FACE provides a measurable advantage over standard support-restricted double-oracle solving, beyond its diagnostic value? Can you evaluate equilibrium-set preservation with non-oracle support estimates, rather than only pointwise exploitability, to establish whether the theoretical set-level guarantees are practically attainable?

2 comments

We thank the reviewer for the careful reading and for highlighting the theory and the transparent experiments. Below we answer each point.

There is limited algorithmic novelty and also limited practical benefit. The procedure selected for certification is the standard double-oracle best-response expansion, and FACE requires the identification of relevant supports.

The expansion step is standard by design (§2, p.2, lines 101–107; §5, p.7, line 365). What the paper adds is when the step is needed and what it costs. Theorem 5.3 (p.7, line 348) separates certificate correctness (holding for any seed) from cost (set by the seed). New Table 10 (p.31, line 163) shows the oracle-seeded Leduc loop's 8 rounds (6 to 10) stem from a non-singleton restricted equilibrium set on 24/24 instances, not thresholds (24/24 bit-identical traces at 1e-9 and 1e-6), while selecting the restricted equilibrium nearest the reference pair certifies in 1 round on 24/24 instances. Certification cost is thus a property of equilibrium selection inside the face, the paper's subject.

On support identification, two non-oracle estimators already in the paper produce the support input: the anchored QRE temperature path (§6) and Algorithm 1's terminal working set (p.8, line 378). In Table 12 (p.32, line 167), the QRE path recovers the oracle carrier face on 6/6 seeds at k = 4, 8, 16, and Algorithm 1's output on 5/6 at k = 8 and 6/6 at k = 16. If an estimate errs, Lemma 5.4 (p.7, line 371) bounds the cost at m + n rounds and Theorem 5.3 keeps the output certified.

The tested compression pipeline is about 12-27x slower than the LP exact baseline, which means that there might not be as much of a practical benefit to the tested compression pipeline.

That figure is the 337 by 337 Leduc sequence form, where the dense LP with certificate takes 0.036 s; as the paper notes, nothing beats the dense LP at that size. The new "Scale" paragraph (§6, p.10, lines 503–515) and Table 13 (p.32, line 169) run the same instance through the dense LP (HiGHS, full matrix) and two compressed paths certified on the original matrix via Algorithm 1 (P1: truncated-SVD seed; P2: FACE), on exact low-rank family F1 and F2b (F1 plus a dense residual of scale 1e-3). Times (s), median over seeds, [certified/total]; TO: 4 h limit; OOM: killed at 64 GiB limit; RSS: peak memory (GiB).

familyndense LPP1P2dense/P1dense/P2RSS denseRSS P1
F140007.4 [1/1]0.6 [1/1]0.7 [1/1]12.811.12.30.3
F1800026.5 [1/1]1.7 [1/1]2.1 [1/1]15.612.88.91.0
F116000119.2 [3/3]6.9 [3/3]8.0 [3/3]17.514.935.43.9
F132000OOM [0/2]27.1 [2/2]35.0 [2/2]---15.3
F2b400027.9 [1/1]1.8 [1/1]2.2 [1/1]15.412.92.30.3
F2b16000525-4969 [2/3] (TO 1)44.6 [3/3]47.7 [3/3]12.8-110.8, >32312.8-88.1, >30235.43.9
F2b32000OOM [0/2]202.0 [2/2]226.5 [2/2]---15.3

At n = 16000, the compressed path is 17.5 times faster than the dense LP on all three seeds; at n = 32000, the dense LP is infeasible on this machine while both compressed paths certify 8/8 runs within 15.3 GiB (certified gap at most 4.3e-14). The n = 32000 dense LP needs about 142 GiB, as measured peak memory is 18.5 to 19.3 times the 7.6 GiB matrix. Two scope notes: the comparison is against the dense LP, and compressed paths hold the full matrix for certification, saving time, not memory. Contribution 3 (p.2, lines 88–91) now states both regimes.

Also, there is limited valuation of the equilibrium-set preservation without the oracle knowledge. A lot of the FACE analysis uses supports that are derived from the oracles. The experiments without oracles certify individual equilibrium, rather than recovery, or preservation, of the full equilibrium set, which is the main motivation of this paper.

The new experiment measures the set, not a point. For six support estimators on an exact low-rank 250 by 250 family (rank at most 22, margin gamma = 0.0167, six seeds), we compute the product-l1 two-sided inclusion error ("max-inc") between NE(M) and NE(M_hat), zero exactly when the two equilibrium sets coincide; Table 12 excerpt (p.32, line 167), six-seed medians, "face" = seeds whose estimate equals the oracle face:

ksupportfacedim Q_xstorageeta_F/gammamax-inc<=10^-6<=10^-5
4QRE path6/6160.1321.625.0e-20/60/6
8QRE path6/6200.1660.741.5e-62/66/6
16QRE path6/6280.2371.1e-139.5e-156/66/6
16Alg. 1 output6/6280.2371.1e-139.5e-156/66/6
16blind0/6180.1492.7e-132.5e-10/60/6

At k = 16, a 28-dimensional anchored projector (storage ratio 0.237) preserves the whole equilibrium set at machine precision (inclusion error 9.5e-15) using supports from the QRE path and Algorithm 1 on 6/6 seeds each. At k = 4, the same path finds the face, but eta_F/gamma is 1.52 to 2.24 and no seed preserves the set, making condition (iii) of Theorem 4.5 (p.6, line 300), eta_F < gamma, decisive. Blind truncation at k = 16 yields machine-zero eta_F on the wrong face (inclusion error 0.248), so conditions (i) and (ii) cannot be dropped. §6 (p.9, lines 458–467) summarizes this.

Can you demonstrate a setting where FACE provides a measurable advantage over standard support-restricted double-oracle solving, beyond its diagnostic value?

On the same support, restricted games under FACE and plain restriction coincide (Propositions 5.1 and 5.2, p.7, line 324 and p.7, line 330) with identical solve cost (wall-clock ratio 1.02 on 24 Leduc instances), so we claim no speed advantage. The advantage is what is certified: support-restricted double oracle certifies one returned strategy (Theorem 5.3), whereas FACE with the margin condition certifies the whole equilibrium set and yields a compressed game where that set lives. Table 12 shows this at k = 16: inclusion error 9.5e-15 at storage ratio 0.237 using supports from the QRE path or Algorithm 1. A point certificate cannot make that statement; the setting is any application where the set is the deliverable, such as auditing all equilibria of a compressed meta-game rather than one.

Can you evaluate equilibrium-set preservation with non-oracle support estimates, rather than only pointwise exploitability, to establish whether the theoretical set-level guarantees are practically attainable?

Table 12 above is that evaluation. The guarantee is attainable where the conditions are satisfiable, and the diagnostic says in advance where they are not. On that family, eta_F and gamma are computable before any solve, and the eta_F < gamma prediction matches outcomes at k = 4, 8, and 16. In Table 2's column-noise family (p.10, line 486), the uniform margin is on the order of the LP tolerance (about 1e-6), precluding condition (iii) for any compressor; at k = 4 and 16, no compression arm preserved the set, as the diagnostic flags before the solve.


We thank the reviewer again and are glad to run any further check they consider useful.

Comments on the paper

3 comments

We thank all three reviewers. The revised PDF marks every changed or added word in red.

  • Introduction, contribution 3 (p.2, lines 91–96): the certificate provides no speedup at n=337n = 337, while on exact low-rank families the compressed path is 15.6 to 17.5 times faster than the dense LP at n=8000n = 8000 to 16000 and still certifies at n=32000n = 32000, where the dense LP exceeds memory.
  • Related Work, §2 (p.2, line 107 to p.3, line 151): deployed pipelines with low-rank payoff or win-rate matrices (Bradley and Terry, 1952; Balduzzi et al., 2018; Tuyls et al., 2020; Fu et al., 2026; Mehta, 2014). [Reviewer C84W W2/Q2]
  • Related Work, §2 (p.3, lines 156–161): what Theorems 4.3 and 4.5 add beyond the failure of lower hemicontinuity and strategic stability. [C84W W1/Q1, iZZF W1/Q1]
  • §4 (p.6, lines 286–299): knock-out reading of the amplification bound, new Table 11. [C84W Q1, iZZF Q1]
  • §6, Leduc paragraph (p.8, lines 425–429): the cause of the 6 to 10 oracle-seeded rounds, new Table 10. [C84W Q4]
  • §6, non-oracle paragraph (p.9, lines 458–468): set-level preservation with non-oracle supports, new Table 12. [s4yj W4/W5/Q2, iZZF Q2]
  • §6, new paragraph "Scale" (p.10, lines 500–513): dense LP versus compressed path at n=8000n = 8000 to 32000, new Table 13. [s4yj W2, C84W W2/Q3/Suggestion, iZZF Q2]
  • Appendix B.11 (p.31, line 1638 to p.31, line 1673): Tables 10 to 15 with their protocols.
  • Eight long sentences in §1, §3, §4, §5 and §6 were split for readability.

We thank the reviewer for checking the new proofs line by line and for rebuilding our games. Every point below is adopted in the revision

Theorem 4.3

Theorem 4.3's hypothesis can be weakened to drop η\eta and ∥M∥max\Vert M\Vert_{max} ... Theorem 4.3 should hold under ε>0,2(ε+ηF)<γ\varepsilon>0, 2(\varepsilon+\eta_F)<\gamma and 2ηF/ε≤r△2\eta_F / \varepsilon \leq r_{\triangle}, and Lemma 4.2 under 2ρF<γ2\rho_F<\gamma ... Please consider the weaker hypotheses, under which the theorem depends on the residual only through ηF\eta_F.

Thank you for this strengthening, which we adopt in full. Lemma 4.2 now assumes only 2ρF<γ2\rho_F<\gamma, and Theorem 4.3 assumes ϵ>0\epsilon>0, 2(ϵ+ηF)<γ2(\epsilon+\eta_F)<\gamma and 2ηF/ϵ≤rΔ2\eta_F/\epsilon\le r_\Delta (statements at p.5, line 261 and p.5, line 264). Neither η\eta nor ∥M∥max⁡\lVert M\rVert_{\max} appears any more, so the hypothesis and the bound depend on the residual through ηF\eta_F alone, as the text after the theorem now says (p.6, line 270 to p.6, line 272).

The new proof of Lemma 4.2 follows the argument in your comment (p.14, line 746). Every entry of W′[Sx,Sy]W'[S_x,S_y] lies in [v−ρF, v+ρF][v-\rho_F,\,v+\rho_F], so the restricted value vF′v'_F is within ρF\rho_F of vv. Against a restricted equilibrium, every outside row earns at most v−γ+ρF≤vF′−(γ−2ρF)v-\gamma+\rho_F\le v'_F-(\gamma-2\rho_F), so the restricted equilibrium is an equilibrium of W′W'. Pairing any equilibrium of W′W' with it then forces zero outside mass. The outside-by-outside block is never evaluated. The proof of Theorem 4.3 applies the lemma to M+ϵΔM+\epsilon\Delta and to W^\widehat W and is otherwise unchanged (p.15, line 768).

We repeated your numerical check independently. On 400 random flat-face games with 5 to 11 actions per player, ρF\rho_F up to 0.49γ0.49\gamma and outside-by-outside changes up to 100γ100\gamma, an LP maximizing the outside mass over all equilibria returns at most 9.4×10−89.4\times10^{-8}. The condition ∣v(W′)−v∣≤ρF\lvert v(W')-v\rvert\le\rho_F holds in every game. A control with ρF=0.7γ\rho_F=0.7\gamma breaks containment in 103 of 200 games, so the test can detect a failure.

The "hyp." column of Table 11 is recomputed for the new hypothesis (p.32, line 1699). It holds in 24 of 40 cells, including all 8 "oo" cells, against 19 before, and in each of the 24 the displacement is at most 2ηF/ϵ2\eta_F/\epsilon. Appendix B.11 states this count (p.31, line 1661).

Cost and benefit of compression

One correction: lines 508-509 call uncompressed double oracle "the cheapest path at every size". On F1 at n=8000n=8000 (one seed), Table 13 reports 2.5 s for double oracle, against 1.7 s for P1 and 2.3 s for P2 at k=24k=24.

Thank you for catching this. The sentence now reads: "Uncompressed double oracle is the cheapest certified path in six of the seven family-and-size settings. The exception is F1 at n=8000n=8000, where one seed gives 2.5 s against 1.7 s for P1 and 2.3 s for P2 at k=24k=24." (p.10, line 518)

What does FACE add, as a representation of the exact equilibrium set, beyond the face rows and columns of MM? ... If FACE is meant to represent these sets instead, please say so in Section 6.

Thank you for this question, which sharpens contribution 4. For the exact equilibrium set, the face rows and columns of MM suffice, and the paper now says so. We added this representation as the last row of Table 12 (p.33, line 1728): on all six seeds of F1(250, 12) it has ηF=0\eta_F=0, storage ratio 0.094, and inclusion error at most 6.3×10−146.3\times10^{-14} at both ϵ=10−6\epsilon=10^{-6} and ϵ=0\epsilon=0.

What FACE adds is an approximation of the payoffs off the face. The full residual η\eta measures that approximation, and it enters Theorem 4.5 through the Hausdorff bound 2κ(ϵ+η)2\kappa(\epsilon+\eta) on the approximate sets. The face rows and columns leave η=0.20\eta=0.20 on F1. FACE on the oracle face has η=0.21\eta=0.21 at k=4k=4, 0.150.15 at k=8k=8, and rounding at k=16k=16, where it stores the whole game at ratio 0.237. Section 6 now states this reading (p.9, line 474 to p.9, line 477). Contribution 4 is reworded to match: "compression buys no runtime. The face rows and columns of the original matrix carry the exact equilibrium set, and FACE adds a low-rank approximation of off-face payoffs" (p.2, line 97). The closing sentence of the Scale paragraph is aligned with it (p.10, line 524).

Set-level preservation (Table 12)

In every draw, FACE on the oracle face reproduces MM of rounding at k=16k=16 (largest entry error of order 10−1510^{-15}) but not at k=8k=8 (above 0.1). If the same holds for your instances, the k=16k=16 rows of Table 12 that use the oracle face do not test compression error ... If the k=16k=16 projection on the oracle face is exact, please say so at lines 460-463.

Thank you for the reconstruction. The same holds on our six instances, and Table 12 now reports the full residual η=∥M−M^∥max⁡\eta=\lVert M-\widehat M\rVert_{\max} in a new column (p.33, line 1728). On the oracle face, η\eta is at most 2.2×10−152.2\times10^{-15} at k=16k=16, between 0.13 and 0.17 at k=8k=8, and between 0.20 and 0.26 at k=4k=4. Section 6 now says that the k=16k=16 rows on the oracle face reproduce MM to rounding and do not test compression error, unlike k=4k=4 and k=8k=8 (p.9, line 468). The blind row at k=16k=16 has η=0.40\eta=0.40 and remains a test.

The updated table (medians over six seeds):

kksupportfacedim⁡Qx\dim Q_xstorageη\etaηF/γ\eta_F/\gammamax-incmax-inc ≤10−6\le10^{-6}max-inc ≤10−5\le10^{-5}
4oracle6/6160.1320.211.625.0×10−25.0\times10^{-2}0/60/6
4QRE path6/6160.1320.211.625.0×10−25.0\times10^{-2}0/60/6
4Alg. 1 output0/6170.1410.218.133.3×10−23.3\times10^{-2}0/60/6
4blind0/650.0490.7544.764.2×10−14.2\times10^{-1}0/60/6
8oracle6/6200.1660.150.741.5×10−61.5\times10^{-6}2/66/6
8QRE path6/6200.1660.150.741.5×10−61.5\times10^{-6}2/66/6
8Alg. 1 output5/6200.1660.150.821.5×10−61.5\times10^{-6}2/66/6
8blind0/6100.0820.7322.764.0×10−14.0\times10^{-1}0/60/6
16oracle6/6280.2371.8×10−151.8\times10^{-15}1.1×10−131.1\times10^{-13}9.5×10−159.5\times10^{-15}6/66/6
16QRE path6/6280.2371.8×10−151.8\times10^{-15}1.1×10−131.1\times10^{-13}9.5×10−159.5\times10^{-15}6/66/6
16Alg. 1 output6/6280.2371.8×10−151.8\times10^{-15}1.1×10−131.1\times10^{-13}9.5×10−159.5\times10^{-15}6/66/6
16blind0/6180.1490.402.7×10−132.7\times10^{-13}2.5×10−12.5\times10^{-1}0/60/6
face rows and columns6/60.0940.2001.8×10−141.8\times10^{-14}6/66/6

Knock-out arms (Table 11)

Lines 296-297 say that a residual of the same norm on the face block moves the equilibrium "by up to 3.0". In Table 11, the "inface" arm moves it by at most 2.000, and every entry of 3.000 belongs to the blind arm.

Thank you, corrected. The sentence now attributes each number to its arm: a residual of the same norm on the face block moves the equilibrium by up to 2.0, and blind truncation by up to 3.0 (p.6, line 297).

In the rebuild, at every ε\varepsilon, the k=1k=1 "inface" residual M+ε△−W^M+\varepsilon\triangle-\widehat{W} has cosine similarity 0.997 with △F\triangle_F and 0.012 with the all-ones face block. The compressed face game is thus close to (ε−0.71)△F(\varepsilon-0.71)\triangle_F,a sign-reversed matching pennies with the same saddle point.

Thank you for the rebuild. It provides the right reading and replaces the constant-shift description in our previous reply. Our instance reproduces both cosines, 0.997 and 0.012, at all four ϵ\epsilon. The least-squares fit of the compressed face game to c ΔFc\,\Delta_F gives cc from −0.71-0.71 at ϵ=10−4\epsilon=10^{-4} to −0.61-0.61 at ϵ=10−1\epsilon=10^{-1}, which is ϵ−0.71\epsilon-0.71. As you note, this matches the sentence in the paper, which we leave unchanged.

Theorem 5.3

Please reword both passages to present the seed property as "the property of the standard check that the experiments rely on", as your reply puts it.

Thank you, both passages are reworded. Contribution 3 now reads: "Algorithm 1 pairs support-restricted solving with the standard double-oracle best-response check on the original matrix to return a strategy with bounded exploitability from any initial seed. This check is correct for any seed, a property of the standard check that our experiments rely on." (p.2, line 88) Related Work now reads: "Best-response certification is standard in double oracle. Its correctness holds for any seed, a property of the standard check that our experiments rely on when measuring the cost of a compressed seed." (p.4, line 164)

Reproducibility

The supplementary package uploaded with this reply adds the entry point rb_cross and its recorded output, which produce the η\eta column and the last row of Table 12.


We thank the reviewer again for three rounds of constructive reading. The weaker hypotheses, the face rows-and-columns baseline, and the corrected attributions make the paper sharper. If these changes resolve the remaining points, we would be grateful if the reviewer would consider raising the score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.