We thank the reviewer for recognising the significance and innovation presented in our work. We hope our significant revision to the main text and figures following several of your suggestions will further improve clarity.

Q1: clarity of presentation in the method section as well as Figure 3 We fully agree with your assessment and we took on board several of your suggestions in our revision (see updated PDF, with major changes highlighted in blue). We have fully reworked Figure 1 and Figure 2 as well.

Specifically,

• We introduced precise mathematical notations where possible in describing our method (in Figures and in text).
• We renamed “player-to-coplayer self-attention” to “action-to-joint-action self-attention”. This is slightly different from your suggestion but it reflects the fact that in the self-attention module, queries are the action of each player, and the key-values attended over are the joint-action (and their respective payoffs).

Regarding Figure 3, we tried to provide thorough ablation results here as they differ based on the nature of the tasks, the game sizes and the model hyperparameters. We are actively trying out other ways of presenting these results and perhaps a table would indeed work best. We could still provide the learning curves (showing the rate of convergence) in an appendix section for interested readers. We will update with revision when ready.

Q2: How are these invalid joint-actions masked out? We unfortunately glossed over this detail in our initial submission. We have now included the precise implementation of this operation in Equation 4.

Indeed, the implementation amounts to enforcing invalid combinations of query-key-values to have negative infinity in their pre-softmax logits, effectively removing their contribution in the outputs.

Q3: how are the DISC games sampled? And how is the model trained?

We provided technical details in how the DISC games are generated in Appendix B.2. but we failed to signpost it in the main text clearly. We do so in our revision now.

In short, we sample latent vectors (with different dimension Z) underlying a DISC game from a standard normal distribution and add to them a noise vector sampled from a uniform distribution.

For each sampled instance of the DISC game, we additionally sample a mask (such that each joint-action is kept with probability $p$) and we pass both the sampled game payoff tensor and the sampled mask to the NfgTransformer model, which returns a set of action embeddings, without observing the outcomes of invalid joint-actions (we ensure this via Equation 4). We then decode from action embeddings predicted payoff values for every joint-action and simply minimize the reconstruction loss given the ground truth full-payoff (as described in Figure 2 (Right)). The loss is minimised end-to-end via gradient descent.

We have added a description of the above training procedure in Appendix B to clarify our settings for future readers.

Thank you for your quick response and for reconfirming your positive assessment of our work. A few quick responses below:

Q1. choice of primary area

We have indeed hesitated between the two choices. As we study the representation learning for a novel data modality previously under discussed, we tried to be non-committal in our choice. The "representation learning" category indeed seems more appropriate. "Algorithmic game theory" perhaps hints at solving specific game theory tasks which is a secondary effect of our paper not a primary goal.

We can't seem to make the change now to "representation learning", but we will follow up with ICLR to make the switch if possible if/when the paper gets accepted.

Q2/Q3: explicit vs. implicit representation learning

This is an excellent remark and we will rephrase this comparison in our introductory paragraphs to make this comparison stand out more.

A few quick remarks on this point:

It is true that prior works implicitly relied on representation learning, however, they are either lossy (e.g. Feng et al., 2021; Marris et al., 2022) due to the use of order-invariant pooling functions (see Marris et al., 2022 Appendix C.1 for a list of candidate pooling functions) or inefficient (e.g. Duan et al., 2023a;b), using MLPs which do not exploit the permutation equivariance properties of NFGs.

In fact, for the specialist pooling-based architectures, one could simply handcraft pooling functions for some tasks such that no representation learning is needed at all. For max-deviation-gain prediction, one could imagine designing pooling function that directly extract max-deviation-gain from the payoff tensor and expose them in the penultimate layer of the network (indeed, without such customisation, NES seemed to struggle in the max-deviation-gain prediction task more than it struggled in the NE-solving task). This would not in our view qualify as representation learning. However, the boundary is blurred across tasks: for equilibrium-solving, design of such pooling functions wouldn't be possible and representation learning would be implicit indeed as noted in your comment.

We thank the reviewers for pointing out potential sources of confusion in our presentation. We hope our revision to the main text would help clarify our arguments.

Q1: Is permutation equivariance inherent to normal-form games?

By “inherent equivariance of NFGs” we mean that action or player permutations applied to the payoff tensor of an NFG do not fundamentally “change” the game. Note that this general property of NFGs has been observed and formally characterised in [1-2].

This is not an assumption that we make, or a property discovered in our work but a general observation that holds for all NFGs and this is why we can leverage this property in our design without loss of generality.

As a simple example, consider $G$, a payoff matrix that describes a prisoner’s dilemma. I could permute the two actions for the row-player and obtain $G’$, which is “strategically equivalent” or strongly isomorphic to $G$.

If I were to encode G1 and G2 using NfgTransformer, I would expect the following identity in the action embeddings: $\mathbf{a’}^2_1 = \mathbf{a}^1_1$. If I were to use a MLP network then I would not have this guarantee.

Q2: how does NfgTransformer differ from vanilla transformer?

We have significantly reworked our method description as well as Figure 1 and Figure 2 that describe the model architecture in specifics. The only commonality between our proposed model and vanilla transformer is that both architectures use self-/cross-attention operations as fundamental building blocks. The NfgTransformer is otherwise distinct from vanilla Transformer in how these components are applied and used.

We hope our revision to the main text and figures could help verify the novelty of our model design.

Q3: Is permutation equivariance guaranteed?

The permutation equivariance property is guaranteed by construction. In our revision, we have slightly expanded on the background section on the attention mechanism which is equivariant with respect to queries (and order-invariant with respect to key-values). In the revised Figure 1 (Bottom), we make clear what are the queries and key-values to each attention operation, and show how permutation equivariance is guaranteed by careful design.

Empirically, our interpretability results (Figure 5, action embedding visualisation) also confirm that Proposition 3.2 holds, which is a property for any permutation equivariant encoding function (which we proved in Appendix A).

Q4: Are there any theoretical guarantees to the proposed architecture?

We do not have any bounds on the rate of convergence of our model as it’s based on deep learning neural networks architecture and such guarantees are difficult to prove in general. However, we do show significantly better empirical results than several comparable baseline methods, and our Figure 3 thoroughly ablates different model hyper-parameters, showing which parameters affect the rate of convergence in different tasks at each game size.

In terms of theoretical guarantees, we did prove (in Appendix A) the precise conditions under which one could expect identities in the action embeddings, for any deterministic and equivariant embedding function. NfgTransformer is deterministic and equivariant and these identities must hold. Two straightforward corollaries of this theorem are stated in Section 3.

Q5: are the empirical results sufficient in making the generality claim?

We think the best way to demonstrate the generality of any representation learning technique is to demonstrate that the same representation learning approach can enable strong results in a number of downstream tasks. In domains such as computer vision one would be expected to provide results on reconstruction, classification among other benchmark tasks.

Here, we showed strong empirical results in key tasks such as equilibrium-solving, deviation gain estimation and payoff prediction. We chose these tasks because they operate at different decoding granularities (see our updated Figure 2), and cover many of the interesting use-cases of normal-form game theory. We believe these support our claim on the generality of our approach to representing NFGs.

[1] J. C. C. McKinsey.11. ISOMORPHISM OF GAMES, AND STRATEGIC EQUIVALENCE, pp. 117–130. Princeton University Press, Princeton, 1951.

[2] Joaquim Gabarŕo, Alina Garcıa, and Maria Serna. The complexity of game isomorphism. Theoreti- cal Computer Science, 412(48):6675–6695, 2011.

Q1: choice of citations in the introduction and motivations behind the work.

You are right (and not being pedantic) to point out the issues with the initial motivations and citations used. We regret the boilerplate sentences used and have reworked the entire introduction to have a clearer motivation and have updated citations to not omit important work in the field.

We hope our revision and more relevant citations would help clarify the motivation behind our work.

Q2: Lack of clarity of the method description.

We took on board these constructive criticisms and have revised Figure 1 and Figure 2 entirely, with precise notations throughout. We have also updated our method description in text accordingly, preferring precise notations where possible. In particular, the three downstream applications that we studied are now clearly described, with specific loss functions shown in Figure 2 and in text.

We hope our revision brings clarity to our method descriptions.

Q3: The “how” and “why” behind the experiments.

We hope our earlier responses and our revision to the main paper provides sufficient clarity now. All three empirical experiments are now described more precisely in Figure 2. We train these models end-to-end via gradient descent, minimising the loss functions described in Figure 2 (Top) and in text. Equation 4 now describes precisely how masking is implemented in our experiment.

Q4: regular isomorphism vs strong isomorphism for NFGs.

[1] offers more precision definition of isomorphic games and strongly isomorphic NFGs. In short, isomorphic games would preserve the “preference ranking” of actions when players and actions are permuted. Strongly isomorphic games preserve the exact payoff value before and after the permutation.

For example, rock-paper-scissors and paper-scissors-rock are strongly isomorphic because I can permute the former to recover the exact payoff matrix of the latter (i.e. payoff values match, not just in the preference ranking of the actions).

We provide additional details in Appendix A, Figure 6 on the notion of strong isomorphism.

[1] Joaquim Gabarŕo, Alina Garcıa, and Maria Serna. The complexity of game isomorphism. Theoreti- cal Computer Science, 412(48):6675–6695, 2011.

Another quick comment regarding our analogy to RGB pixels and the fact that one could solve for NE to reasonable approximation in zero-sum NFGs:

In our experiments, we showed empirical results on solving for NE in 2 and 3-player general-sum NFGs. The latter being more difficult but we could nonetheless approximate an NE solution to acceptable accuracy with our larger models. We can trivially extend our model to work with 4 player games too perhaps with further architectural innovations. Using classical solvers, with each generalisation of the game class (2-player 0-sum --> 2 player general-sum ---> 3 player zero-sum ...) we might need specialised tools and innovations, we think our results provide another promising approach to tackle such approximate equilibrium solving problems in a rather general fashion.

NN-based solvers also have other practical benefits such as their differentiability and ease to parallelise taking advantage of accelerators to solve a large number of games in short amount of time.

We think our analogy to RGB remains apt: before deep representation learning techniques revolutionised computer vision, many representation techniques have been developed too, even for tasks like segmentation or classification (e.g. Laplacian Pyramid, wavelet transform). Granted they do not achieve similar levels of performance as we can do today. Similarly, a) no off-the-shelf classical NE solver can solve thousands or millions of 3-player general-sum NFGs to reasonable accuracy in seconds; and b) we show better results on equilibrium solving than NES which relied on handcrafted feature vectors (not dissimilar to how learned representation surpassed the performance offered by laplacian pyramid/wavelet transform).

Our work is only the first (principled) representation learning technique for NFGs too and our hope is that even better performance will follow with further architectural innovation as is the tradition of this conference.

We thank the reviewer for their constructive feedback and we preface our responses by stating that our initial submission has not been clear which could have added to the confusion in reviewer’s questions. We hope our revision will bring clarity to many of these questions.

Q1: permutation equivariance follows directly from the transformer architecture, please clarify your contribution.

We define permutation equivariance to be: permutation in the strategies and players of the input, results in identical permutation of the output (with no change to network parameters). This definition is made precise in our background section.

Traditional language transformers do NOT have this property: they are causal and position aware, with appropriate masking and position embeddings. The representation after seeing the first token “dog” in “dog bites man” should be very different from the representation after seeing the last token “dog” in “man bites dog” even though we simply permuted “dog” and “man” in the input.

The word "transformer" is used in NfgTransformer due to the use of self-attention and cross-attention operations, which have been popularised by the Transformer architecture. The attention operation treats key-value inputs as an unordered set; they are additionally equivariant with respect to the queries. These are the properties NfgTransformer leverages in its architecture. We now call them out explicitly in the background section on Multi-headed Attention in our revision.

In short, the equivariance property of NfgTransformer is through careful design of our novel architecture proposal that is catered to the structure of NFGs, not a direct result of existing transformer architecture.

Q2: the contribution and motivation of the method should be clarified.

We agree with the reviewer that our initial introduction paragraphs were not clear and we have significantly revised our introduction paragraphs to better reflect our motivation.

Q3: presentation of the method is not clear (e.g. Fig1 and Fig2).

We recognise these issues as a major source of confusion and have revised these two figures significantly with precise notations. We have updated our description of the architecture in the text too. Please do let us know if there are other changes that would improve the presentation upon reviewing our changes.

Q4: broken links. We have verified that links are working as intended in our revised PDF. Please let us know if this is not the case.

Q5: evaluation domains are toy’ish. We evaluate our model on synthetic games that cover the entire equilibrium-invariant space of NFGs in Figure 3. Games sampled from this space have the property that they cover all interesting strategic interactions that could change the equilibrium solution of the NFGs at a specific game size. This is consistent with earlier work such as NES [1]. For ranking, we studied DISC games which are consistent with prior works in the ranking literature [2-3]. Finally, our interpretability results are done in GAMUT, which is the standard set of NFGs that capture relevant strategic dynamics in the economics/game theory literature.

We believe our choice of test domains is principled and well-grounded in the literature targeting normal-form game theory.

The normal-form payoff matrix of Go and Chess are known to be highly transitive [4] and we would expect them to tend to have dominant actions (players) and therefore make for less comprehensive evaluation.

[1] Marris, Luke, et al. "Turbocharging solution concepts: Solving NEs, CEs and CCEs with neural equilibrium solvers." Advances in Neural Information Processing Systems 35 (2022): 5586-5600.

[2] Bertrand, Quentin, Wojciech Marian Czarnecki, and Gauthier Gidel. "On the Limitations of the Elo, Real-World Games are Transitive, not Additive." International Conference on Artificial Intelligence and Statistics. PMLR, 2023.

[3] Vadori, Nelson, and Rahul Savani. "Ordinal Potential-based Player Rating." arXiv preprint arXiv:2306.05366 (2023).

[4] Czarnecki, Wojciech M., et al. "Real world games look like spinning tops." Advances in Neural Information Processing Systems 33 (2020): 17443-17454.