Solving Nash Equilibrium Scalably via Deep-Learning-Augmented Iterative Algorithms

Thank you for your valuable feedback and constructive comments. Below are our responses to your concerns.

Weaknesses

1. We apologize for the confusion. We will revise both the abstract and the paper in the future to provide a more explicit description of the iterative algorithm.
2. Thank you for your constructive comment. We will provide more detailed description of our motivation, model and experiments in our future version.
3. Thank you for your constructive comment. We will revise the Related Work and Methodology sections to improve the clarity.
4. Please see Questions.

Questions

In the current version of the paper, we mainly compared the computational costs of different methods through asymptotic complexity. Our model achieves exponential improvement in both time and space requirements in terms of the dependence on the number of players $N$ and actions $T$, which significantly enhances the scalability by addressing the curse of dimensionality. We will empirically compare the running time in the future versions.

Here we provide a quantitative discussion. When $N$ is above 100, the inference of existing methods become absolutely infeasible even on hypercomputers, as their time and space complexity are at least $T^N\geq 2^N>10^{30}$. In comparison, our model remains feasible on standard computers in such cases. For example, if we select $K=30$ as number of iterations and $D=100$ as hidden dimensionality, when $N=100,T=100$, our model’s inference requires about $KNT^2D^2\approx 3*10^{11}$ floating point operations, which can be computed in about $300$ seconds by a $10^9$ flops CPU core, or much less time on GPUs.

Thanks for your valuable review and constructive comments. We will incorporate them to improve this work in the future. Below are our responses to some of your questions:

Q1 Some properties of the network, such as permutation equivariance, and transformer layers are contributions of prior work (Duan, Marris, Liu), and this paper borderline claims these as contributions.

A1 We apologize for the confusion. Our intention was to highlight the advantages of our proposed model, including the permutation equivariance property and the expressiveness from transformer structure, instead of claiming the two concepts as our contributions. Still when incorporating them into our model, we make improvements compared with prior works: We generalize the permutation equivariance concept to randomized output distribution, to avoid restriction on equilibrium selection, which may harm the social welfare. We design an efficient attention structure with $O(NT^2+N^2)$ time complexity, while NfgTransformer takes $O(T^{2N})$ time since it performs self-attention operation on all $T^N$ joint actions.

Q2 I worry that the authors have made an error in their comparison to Nfg resulting in a factor of 3 discrepancy between the reported results.

[Experimental Results] I noticed that the code for NfgTransformer did not run, so reported results from the NfgTransformer paper were used. The dataset that NfgTransformer was evaluated on is different to the one DINES evaluated on. In particular, Nfg uses a particular distribution of payoffs with variance of 1 for each element, while DINES uses U[-1, +1], which has variance 1/3. Napkin math means that we approximately expect the scale of the payoffs used in DINES to be 1/3 of that in Nfg. Which will result in 1/3 of the expected exploitability. Therefore I believe the paper is underreporting the performance of the competitor model by about 1/3. Aside: I think all these types of papers should report expected exploitability under a uniform distribution for the datasets they sample from to avoid these types of comparison errors. Can you add a row that shows this?

A2 Thank you for your insightful comment. We apologize for the oversight. You are correct that the discrepancy arises from the different payoff distributions used in the NfgTransformer and DINES models. Comparing the variance of payoff distribution, The scale of the payoffs for DINES is approximately $\frac{1}{\sqrt{3}}\approx 0.58$ of that for NfgTransformer, so the loss of NfgTransformer should be scaled with factor $\sqrt{\frac{1}{3}}$. We appreciate your suggestion to align the datasets by the exploitability of a uniform strategy. We will take this into consideration in future versions of the paper and will incorporate it in future versions of our paper. We will also continue to refine the accuracy of DINES in future work.

Q3 [Training] The exact training procedure is under-explained. L382 says that NashAppr is minimized. I think the confusion has arisen because the paper introduces the algorithm as an iterative procedure, but I think I am meant to interpret it as a DNN for the purposes of training? I have made some guesses that should be made explicit in the writing: a) the network is trained over a distribution of games from U[-1,+1] b) at test time it is evaluated on any game from U[-1,+1] c) the parameters are trained by backpropping through all the layers. Questions: Do you use the same network for different sized games? It seems that the parameters are independent for the size of the game. I would like to see a training curve. How long does this network take to train?

A3 You are right that our model is essentially a single DNN in training, which consists of $K$ networks with the same structure but different parameters.
a) b) The model is both trained and tested over the distribution of normal form games with payoff distribution U[-1,+1].
c) You are right that the model is trained by backpropping through all the $K$ networks.
Thank you for your questions, we will present more detailed descriptions about our model and experiment in the future versions. Currently we are using a fixed model size for different sized games, but the parameters are independently trained for different game distributions.

Q4 [Architecture] On the emphasis on “iterative” in the algorithm. Sure, I get the inspiration from iterative methods, but I think the writing over-emphasizes the iterative properties. The model is essentially a DNN with multiple layers, with the layers being iterations. I think the emphasis would make more sense if the weights of each layer were shared, which made me wonder if you explored this?

A4 Thank you for your thoughtful comment. We have tried sharing the network parameters across all iterations, but the initial results are not very promising. However, we recognize the potential of this approach and may revisit it in future work.

I have read and appreciate the replies of the authors. Unfortunately, I still think the paper is not strong enough in its current form to be accepted at ICLR, so I will not be changing my recommendation.

Thanks for your constructive comments and suggestions, we will incorporate them to improve our paper. Below are our responses to some of your questions.

1. Thanks for your valuable suggestions, we will present more detailed explanation of network architecture with figures in our future version. In the current version of the abstract, we primarily emphasized the exponential improvement in the computational efficiency achieved by our algorithm, which significantly enhances the scalability by addressing the curse of dimensionality. We will thoroughly revise it to improve the clarity.
2. You are right that it is unlikely to theoretically guarantee convergence for any efficient algorithm, given the PPAD-hardness of Nash equilibrium computation. The claim of “improved convergence” is empirical, supported by the fact that the number of iterations is improved from $10^5$ to $30$ compared with traditional learning dynamics, while achieving improved accuracy.
3. Compared to the baselines, especially (Liu et al, 2024), our novelty is threefold:
   1. Our model takes polynomial number of query accesses to the utility functions, instead of inputting the whole utility table. This reduces the asymptotic running time from exponential to polynomial in the number of players and actions, and allows our framework to be applied in any normal-form games as long as the utility function can be efficiently computed.
   2. In terms of the model structure, compared to (Liu et al, 2024), we design a decomposed attention operation among player embeddings and action embeddings, which also contributes to the exponential improvement of time efficiency, as the transformer operation is the bottleneck of time cost.
   3. Our model produces an updated strategy profile in every iteration, which can be interpreted as a process approaching equilibrium through repeated interaction. This approach combines adaptability and interpretability, similar to traditional learning dynamics, which are lacking in previous learning-based methods.
4. Significance: Our model achieves exponential improvement of both time and space efficiency in terms of the dependence on the number of players $N$ and actions $T$, even for succinct games. Existing deep-learning methods require at least $\Theta(NT^N)$ memory usage even for succinct games, since they must compute the whole utility table. This also results in a $\Theta(NT^N)$ time usage, and $\Theta(T^{2N})$ for (Liu et al., 2024)’s model. In contrast, given that the utility function is efficently computable, our model requires only $\Theta(NT)$ space and $\Theta(N^2+NT^2)$ time. Existing methods become absolutely infeasible even on hypercomputers when $N$ is above 50 or 100, while our model remains feasible on standard CPUs. For example, if we select $K=30$ as number of iterations and $D=100$ as hidden dimensionality, when $N=100,T=100$, our model’s inference can be computed in an estimated time of $300$ seconds by a $10^9$ flops CPU core, or much less time on GPUs.
5. Thanks for your constructive suggestions, we will incorporate them and present more experimental details in our future version.

Thanks for your thorough investigation and constructive comments on our paper. We will incorporate your comments to improve the future versions of our paper, especially the sufficiency of experiments. Below are our responses to your questions.

Weaknesses

1. We appreciate your constructive suggestions about the experiment, we will incorporate them and present more comprehensive experiment results in the future version of our paper.
2. You are right that we have generalized the concept of permutation equivariance to the output distribution. Our purpose is to avoid the restriction of equilibrium selection posed by permutation equivariance (which may significantly harm social welfare, as mentioned in Duan et al, 2023b), while taking advantage of the inherent symmetricity of the problem.

Questions

1. We apologize for the confusion. A round means the algorithm queries the utility under a strategy profile and generate an updated strategy profile accordingly. For the traditional learning dynamics, a common implementation is to set a fixed number K of rounds instead of repeating the iteration until convergence, and typically K=100000. Our model’s hyper parameter K similarly indicates the number of rounds, and we actually learn K networks, representing each round’s updating operation of strategies and inner states. By experiments, we find that taking K=30 is enough for good accuracy, meaning that the updating rule learned by our model can recover equilibrium more efficiently than traditional methods. It is true that Liu et al. only require K=2-8 iterations, but their model accesses the whole utility table in each iteration, and performs attention operation on all pure strategy profiles, so their computational cost in each iteration is exponentially larger than ours. Therefore, our algorithm have a significant advantage in efficiency.
2. Thank you for the suggestion, we will present training curves in future versions.
3. The metric of accuracy is Nash Approximation defined in section 2.
4. Thank you for your suggestion, we will present comparison on social welfare in future versions.
5. Our proposed framework (Algorithm 2) follows the common interaction-and-update structure of traditional learning dynamics (Algorithm 1), where players repeatedly update their strategy based on the utility in the interaction with all other players in each round. This is motivated by the heuristic idea that players will reach Nash equilibrium through repeated interactions in many scenarios. We can expect the model to learn the updating rules no worse than the tradtional learning dynamics during training, which provides an evidence for its reliability .
6. We apologize for missing the description of the residual update of strategy. In each round, we actually compute $\mathbf{x}\_p^{(k)}=(1-\gamma\_p^{(k)})\mathbf{x}\_p^{(k-1)}+\gamma_p^{(k)}\Phi(y\_{p}^{(k-1)};\theta\_{\Phi}^{(k)})$
   where $\gamma\_p^{(k)}$ is an adaptive ratio calculated from the player embedding $\beta\_{p}^{(k-1)}$ by an FFN.