Thank you for your review!

Regarding the weaknesses you mention.

• A clash in macro definitions seems to have caused the title to be missing from the paper, this will be fixed for the camera-ready version.
• We will make sure to include a discussion on equilibrium selection, but we note that a strength of our method is that it does not require practitioners to have to select an equilibrium selection criteria which might be hard to decide.
• We will make sure to include graphics which are clearer.

Regarding your questions.

• On the effectiveness in approximating the best response. As we show in additional experiments in Appendix G.1., the accuracy of the discriminator directly impacts the accuracy of the generator, however these two architectures can be tuned independently. We find it interesting to see that 3 of the 5 games can be solved accurately, even when the discriminator is not optimized. This seems to suggest that the accuracy needed for the discriminator depends on the equilibrium structure induced by the payoff structure of the pseudo-game, a direction which future work can explore.

• On generalizing GAES for correlated equilibria. Yes, GAES can be directly extended to compute correlated equilibria, and in fact to any equilibrium notion which can be expressed as a $\Phi$-equilibrium [1] where $\Phi$ is a set of action deviations. To do so, one can replace the cumulative regret with the $\Phi$-cumulative regret, i.e., the sum of unilateral improvements by deviations within a set $\Phi$-action deviations. In this more general setting, the discriminator would then simply output action deviations within $\Phi$.

References

[1] Greenwald, Amy, and Amir Jafari. "A general class of no-regret learning algorithms and game-theoretic equilibria." Learning Theory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings. Berlin, Heidelberg: Springer Berlin Heidelberg, 2003.

Thank you so much for your quick answer!

I believe that for such discrete action pseudo-games, we still need the discriminator to output mixed actions to better approximate the best response. This is because the discrete best response is discontinuous and could change differently with a slight modification of the payoffs.

Prior work seems to corroborate to our point. Namely, Duan et al. [1] show that expected exploitability in normal-form games (i.e., when the discriminator in our setting outputs the exact best-response) can be effectively minimized. This is because while the best-response might be discontinuous (assuming it is unique) in the candidate equilibrium, the exploitability itself is still continuous in the candidate equilibrium.

It is counterintuitive that the generator is more robust with respect to the discriminator in pseudo-games than in normal-form games. As far as I know, pseudo-games are generalized versions of normal-form games; thus, they are more difficult to solve. Do you mean that when the best response is smooth, the generator would be robust to the discriminator?

Our statement was only regarding regarding pseudo-games with discrete action spaces which also includes normal-form games. The intuition for our answer is that if a mixed action best-response always exists, then it is more likely that the players' best-responses change smoothly as a function of the other players' actions. Once again, these claims are empirical anecdotes and not theoretical claims, since in general, without strong concavity and Lipschitz-smoothness of payoffs it is not possible to guarantee a connection between the best-response of each player and their opponents' actions (e.g., Lipschitz-continuity of the best-responses w.r.t. the opponents' actions). Beyond this, we prefer to refrain ourselves from speculating a theory.

I still haven't seen the title of this reference, and I also cannot find it in the references of your paper. Are you referring to the paper Duan, Zhijian, et al. "Is Nash Equilibrium Approximator Learnable?." Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems. 2023. ?

Thank you for noticing this! You can find the correct ACM citation in [1]. The version of the paper cited in our paper is [2]. We consulted [2] while writing our paper, however, the contents align with the most recent version [1].

[1] Zhijian Duan, Wenhan Huang, Dinghuai Zhang, Yali Du, Jun Wang, Yaodong Yang, and Xiaotie Deng. 2023. Is Nash Equilibrium Approximator Learnable? In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS '23). International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 233–241.

[2] Zhijian Duan, Dinghuai Zhang, Wenhan Huang, Yali Du, Jun Wang, Yaodong Yang, and Xiaotie Deng. Towards the pac learnability of nash equilibrium, 2021b. URL https://arxiv.org/abs/2108.07472.

Thank you for your review!

Regarding the weaknesses you mention.

On stationary points of the exploitability. Stationary points of exploitability do not always coincide with GNE, however, our convergence result to stationary points of the expected exploitability is still in line with known theoretical results, since the computation of GNE under Assumption 1 is PPAD-complete [1] and converging to a GNE would imply polynomial-time computation for problems in PPAD. That said, stationary points of the exploitability correspond to $\varepsilon$-GNE, where $\varepsilon$ is equal to the exploitability at the stationary point, and as at a stationary point the exploitability cannot be decreased via first-order information, this Theorem 4.1 suggests that our approach is sound to learn equilibrium mappings via first-order methods, the most prevalent training methods in deep learning.

On the strong concavity assumption. Our theorems directly generalize to payoff functions that only satisfy concavity. This extension follows from the discussion at lines 235-239 and is obtained by regularizing the exploitability. Note that this regularization does not modify the optimal solutions of the optimization problem. However, while running our experiments for exchange economies we have tried adding this regularization to the cumulative regret, but we observed that this regularized cumulative regret performed worse than the original cumulative regret most likely due to the fact that although regularization makes the cumulative regret strongly concave, it also increases the non-convexity of the exploitability. As such, we have decided to present the experiments without regularization. We will make sure to include a more extensive discussion to our paper on this issue.

On the differences between our paper and Goktas and Greenwald’s “Exploitability Minimization in Games and Beyond”. While Goktas and Greenwald observe that the exploitability minimization problem for only one pseudo-game can be expressed as a min-max optimization, it is not obviously true that one can minimize the expected exploitability via a min-max optimization problem. The novelty in our method lies in noticing that we can compute the expected exploitability after computing the expected cumulative regret, by optimizing over the space of best-response functions from pseudo-games to actions, rather than the space of actions individually for every pseudo-game.

On convergence complexity. Thank you for pointing out these papers to us, especially "Doubly smoothed GDA for constrained nonconvex-nonconcave minimax optimization." which seems to going to appear at NeurIPS seems very relevant and we were not aware of them. At a high-level, in all three papers, ignoring acceleration-type methods–-which are rarely used in the training of neural networks in practice due to their complexity—the best convergence complexity achieved is $O(\varepsilon^{-4})$ (see for instance [2]), while our algorithm—which makes use of no acceleration techniques—achieves a complexity of $O(\varepsilon^{-3})$. As a result, in the light of these more recent (and some unpublished) results, our algorithm still achieves a faster convergence rate than single-loop algorithms with no-acceleration.

Regarding your questions.

1. A clash in macro definitions seems to have caused the title to be missing from the paper, this will be fixed for the camera-ready version.
2. We chose to cite the Arxiv versions of the paper to allude to the most recent version of the papers. That said, to address your concern we will cite the published versions of the papers when the Arxiv versions we have consulted match the published versions.
3. We will fix these equation formatting issues for the camera-ready.
4. Thank you for pointing this citation out. It seems that we accidentally cited the wrong paper from Daskalakis et al., while we sought to cite [2].
5. Once again, we will fix these equation formatting issues for the camera-ready.

References

[1] Yang, Junchi, et al. "Faster single-loop algorithms for minimax optimization without strong concavity." International Conference on Artificial Intelligence and Statistics. PMLR, 2022.

[2] Daskalakis, Constantinos, Dylan J. Foster, and Noah Golowich. "Independent policy gradient methods for competitive reinforcement learning." Advances in neural information processing systems 33 (2020): 5527-5540.

I thank the authors for their time and their response. I have no further questions at the moment.

Thank you for your review!

Regarding the weaknesses you mention.

1. Our theorems directly generalize to the concave game settings and as such apply to Arrow-Debreu markets as well; see part 3) of the below answer to your questions and the discussion in lines 235-240 for more information.
2. Our results provide computational complexity guarantees on the training dataset (Theorem 4.1), whose average exploitability achieved on the training set generalizes to the test set with a sample complexity result (Theorem 4.2). Even though Theorem 4.1 does not provide a bound on the value of the average exploitability of the training set, it tells us that average exploitability on the training set, cannot be minimized via first-order deviations, hence suggesting the correctness of the algorithm we use. We note that lack of a full characterization of the average exploitability on the training set is a common occurrence in the literature for learning equilibrium mappings (see for instance [4] and [5]).
3. Just like any neural network, GAES also faces an architecture search problem, and for it to solve the task at hand a search over optimal architectures has to be done. However, this does not affect the generality of GAES. To give a theoretical explanation, according to our sample complexity bounds, the accuracy of GAES depends on the choice of the generator and discriminator hypothesis classes which appear as a "bias" term corresponding to the difference in performance between the optimal generator and discriminator in the class of all possible functions and the optimal ones in the hypothesis class. That is, the choice of a hypothesis class will affect the bias term in performance. As the selection of a neural network architecture effectively determines the hypothesis space we chose, if the architecture of the network is not well-chosen, then the bias of GAES will go up, hence degrading accuracy. This, however, does not take away the fact that with an appropriate neural network architecture GAES is guaranteed to be ``general’’ as the bias term will go down to 0.

Regarding your questions.

1. Pseudo-games were introduced by Kenneth Arrow and Gerard Debreu in 1954 [1] under the name of Abstract Economies, who studied GNE under the name of “equilibrium points”. More recently, Francisco Facchinei and Christian Kanzow’s works has re-popularized Arrow and Debreu’s model under the name of pseudo-games, calling equilibrium points GNE [2]. To the best of our knowledge the first use of the term GNE is due to Harker [3].

2. The distance between the candidate equilibrium actions outputted by GAES and any GNE is measured in payoff space in terms of the exploitability. As such the phrasing “is on average better than at least 99% of the action profiles” means that the GAES achieves an exploitability lower than 99% of all other action profiles in the feasible action space.

3. Yes, our theoretical guarantees apply more broadly to any concave game—that is we can drop the strong concavity condition. As mentioned in lines 235-240, our theorems generalize to the concave game settings by replacing the exploitability with the regularized exploitability, however for consistency and simplicity we chose to present our results under these stronger assumptions, since in experiments non-regularized exploitability performed better.

4. The paper is called “Generative Adversarial Equilibrium Solvers”, a clash in macro definitions seems to have caused the title to be missing from the paper.

References

[1] Arrow, Kenneth J., and Gerard Debreu. "Existence of an equilibrium for a competitive economy." Econometrica: Journal of the Econometric Society (1954): 265-290.

[2] Facchinei, Francisco, and Christian Kanzow. "Generalized Nash equilibrium problems." Annals of Operations Research 175.1 (2010): 177-211.

[3] Harker, P. T. (1991). Generalized Nash games and quasi-variational inequalities. European Journal of Operational Research, 54, 81–94.

[4] Marris, Luke, et al. "Turbocharging Solution Concepts: Solving NEs, CEs and CCEs with Neural Equilibrium Solvers." Advances in Neural Information Processing Systems.

[5] Zhijian Duan, Wenhan Huang, Dinghuai Zhang, Yali Du, Jun Wang, Yaodong Yang, Xiaotie Deng. International Conference on Autonomous Agents and Multi-Agent Systems 2023

Thank you so much for your encouraging and thorough review! It means a lot for us!

Regarding your question. GAES extends directly to games $\mathcal{G} \in \Gamma$ in which players are $n \in \mathbb{N}$ “neural players” with each player $i \in \mathbb{N}$ “choosing” an action (i.e., network weights) from an action space (i.e., a subset of $\mathbb{R}^d$ where $d$ is the number of parameters) which maximizes some desired payoff function $u_i^{\mathcal{G}}$. In such settings, GAES can be seen a meta-learning method, where any game $\mathcal{G} \in \Gamma$ is described as parameters of the problem.

For instance, for generative adversarial neural networks for image classification, we have two neural players consisting of a generator and a discriminator for whom the payoff functions are respectively given as the expected negated cross-entropy and expected cross-entropy over a data set of images. As such, each game is characterized by the data set of images, and GAES can be trained over distributions of image datasets, so as to output optimal network weights for the generator and discriminator for a given image dataset.