- 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
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.
We thank the reviewer for the generous reading of the motivation and of the two fidelities. We answer the weakness and the questions.
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:
None of the three follows from the generic statement.
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.
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.