- Rating
- 3
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper constructs explicit zero-sum games on which Double Oracle requires exactly strategy expansions from a specified initialization, regardless of equilibrium or best-response selection. This matches the standard upper bound.
Critical strengths
- The construction establishes a tight worst-case bound for arbitrary matrix dimensions.
- Independence from selection rules strengthens the result beyond examples relying on adversarial tie-breaking.
- The analysis explicitly quantifies robustness to oracle errors.
Critical weaknesses
- Preserving the full worst-case path in highly rectangular games requires exponentially accurate best responses, limiting its relevance to practical PSRO.
- The bound concerns exact termination. On this construction, a fixed-tolerance approximate equilibrium can be reached substantially earlier, so the result does not establish comparable difficulty for approximate solution.
- A more explicit account of the trade-off between oracle accuracy, target exploitability, and required strategy expansions would strengthen the practical interpretation.
Questions for authors
please see the weaknesses
We thank the reviewers. All three agree that, from the first row and column, our matrix forces the trivial bound of M+N−2 iterations, for every shape and every selection rule. None raises a concern about soundness.
Fixed accuracy (XANY, 5k8T). Our results give a dichotomy. It is also the main conceptual advance that mo2A asks about. At exact termination, DO's worst case is M+N−2 (Theorem 1). If DO instead stops once the duality gap is at most a fixed τ, its worst case does not grow with the larger dimension, yet still reaches the trivial bound when M=N. Propositions 1 and 2 in Appendix B, which we have moved into the body and extended, show this.
Whether the full count survives a fixed tolerance for M<N≤(1+2/τ)M is open (Open Problem 2). Our main matrix needs exponentially small tolerances there.
Full support (XANY). For M=N, our main matrix has a unique, fully mixed equilibrium, and its strategies still enter one at a time. Full support alone gives much less. It does not force one new strategy per iteration. At fixed accuracy τ, it forces at most O(log(MN)/τ2) strategies (Lipton and Young, 1994). For M<N, our main matrix makes DO add N−M columns that its unique equilibrium never uses.
Prior work (XANY, mo2A). Zhang and Sandholm (2024) have two bounds that hold under every selection rule. One follows from support alone, since every equilibrium there has support exponential in the game's size (their Theorem 3.1). The other reaches at most half the trivial bound, at a constant gap (their Theorem 3.2). For M=N, the matrix of our Proposition 2 forces all 2M−2 iterations at a constant gap. Our main matrix forces the trivial bound under every rule, for every shape, and so does every nearby matrix (our Corollary 2).
Revision. We have uploaded a new version of the paper that uses the extra page for the new statements, with proofs in the appendix. The main theorem and its statement in Lean are unchanged.
We checked the new claims on Proposition 2's matrix exactly, over every equilibrium and best response, for small M. We have included these checks in the supplement.